How to find a feasible solution that are most close to given starting values

Answered

Yifeng Mao

• September 04, 2024 17:05

Hi there, I am running the following piece of code. In the code, I already initialized the two variables, and the objective function was set as 0.
What I expect is the solver outputting two initial values. However, the solver outputs x=25 y=0.
I am wondering why this happens? Is it possible to make the returned solutions more close to initial values, without changing the target function?

The code that I run:

import gurobipy as gp
from gurobipy import GRB
model = gp.Model()
x = model.addVar(lb=0, ub=30, name="x")
y = model.addVar(lb=0, ub=10, name="y")
x.start = 20
y.start = 5
model.addConstr(x + y == 25, "c1")

model.setObjective(0, GRB.MINIMIZE)

model.optimize()
print(f"Value of x: {x.x}")
print(f"Value of y: {y.x}")

Related to

• MIPStart

0

• 

  Ryuta Tamura

  Gurobi Staff

  • September 05, 2024 00:18
  • Edited

  Hi Yifeng,

  Start attribute only affects MIP model. Your model is continuous now. If the variable is an integer as follows:

  x = model.addVar(vtype="I", lb=0, ub=30, name="x")
  y = model.addVar(vtype="I", lb=0, ub=10, name="y")

  the solution will be x=20, y=5.

  Thanks,
  Ryuta

  0
• 

  Yifeng Mao

  • September 06, 2024 09:28

  

  

  

  Hi Ryuta,
  
    Thanks for your prompt reply. Your solution works well on this simple toy case.
  
    What I am trying to solve is a more complex MIP problem with initialization of several unknown variables. There might be a few numbers of initialization conflicts (a unknown variable ranging from 0-10, however the initial value is 15).
  
     However, the first feasible solution that the solver returned with / without variable initialization are identical. I am wondering if initialization does not matter to solver on complex MIP problems?

  0
• 

  Ryuta Tamura

  Gurobi Staff

  • September 06, 2024 10:14
  • Edited

  Hi Yifeng,

  a unknown variable ranging from 0-10, however the initial value is 15

  Does this mean that setting x.start = 15 for a variable 0<=x <=10? In such cases, the initial solution is judged to be infeasible and will not be accepted.

  However, the first feasible solution that the solver returned with / without variable initialization are identical. I am wondering if initialization does not matter to solver on complex MIP problems?

  This is not to say that initial solution is meaningless. However, the initial solution is just treated as the first incumbent solution. Gurobi compares solutions based solely on the quality of their objective function values. It does not consider how close the solution is to the initial solution. The solution is updated when a solution with a better objective function value than the initial solution is found.

  Thanks,
  Ryuta

  0
• 

  Ryuta Tamura

  Gurobi Staff

  • September 06, 2024 10:28
  • Edited

  Hi

  However, the first feasible solution that the solver returned with / without variable initialization are identical.

  I mistakenly understood this to be about optimal solutions not first feasible solution. If the first solution obtained is different from the initial solution given, then it is likely that the initial solution has not been accepted. Do you see the output in your logs like:

  Loaded user MIP start with objective xxx

  This means that the initial solution has been accepted. If you see logs like the following:

  User MIP start did not produce a new incumbent solution

  User MIP start violates constraint c1 by xxxx

  this means that the initial solution you gave has not been accepted.

  Thanks,
  Ryuta

  0

Please sign in to leave a comment.