6
$\begingroup$

(For Linear Programming) I am aware of CPLEX's reoptimize methods. If I am not wrong, if you solve a problem and after that you add a new constraint, then you can call the reoptimize method for not to start a whole solution from the beginning.

These kind of methods select the dual simplex method as solution algorithm and the Branch & Bound methods usually follow this method.

Now, is there such a feature in GUROBI. If yes, could you please provide links with me? An implementation example in C++ would be awesome.

$\endgroup$
  • $\begingroup$ Search for: warm start $\endgroup$ – Mark L. Stone Jan 11 at 19:27
  • $\begingroup$ Thanks for that. However, warm start uses the last solution right? But if we reoptimize dual simplex, then this will add new dual variables for each infeasible constraints and the solution will be faster than warm start. Or not? $\endgroup$ – independentvariable Jan 11 at 19:36
  • 3
    $\begingroup$ This is from gurobi documentation: "The model is re-solved simply by calling the optimize method again. For a continuous model, this starts the optimization from the previous solution." $\endgroup$ – EhsanK Jan 11 at 20:03
  • $\begingroup$ Thanks @EhsanK ! Anything about LP? Because for LP dual simplex really makes it faster. If they are using interior point methods by default then starting from the last solution won't help it too much $\endgroup$ – independentvariable Jan 11 at 20:06
  • 3
    $\begingroup$ I guess as they said in the link above, this is for a continuous model. Although you may find some more detail in their support portal or the old gurobi google groups $\endgroup$ – EhsanK Jan 11 at 20:16
3
$\begingroup$

The link that @EhsanK posted already covers the question pretty well.

In such a case, Gurobi should choose the best suited algorithm on its own. Check out this little example, where I read and optimize a linear model, add a new constraint, and optimize again:

In [20]: m = gp.read('C:/gurobi900/win64/examples/data/afiro.mps')
Read MPS format model from file C:/gurobi900/win64/examples/data/afiro.mps
Reading time = 0.01 seconds
AFIRO: 27 rows, 32 columns, 83 nonzeros

In [21]: m.optimize()
Gurobi Optimizer version 9.0.0 build v9.0.0rc2 (win64)
Optimize a model with 27 rows, 32 columns and 83 nonzeros
Model fingerprint: 0x0e972b37
Coefficient statistics:
  Matrix range     [1e-01, 2e+00]
  Objective range  [3e-01, 1e+01]
  Bounds range     [0e+00, 0e+00]
  RHS range        [4e+01, 5e+02]
Presolve removed 18 rows and 20 columns
Presolve time: 0.01s
Presolved: 9 rows, 12 columns, 32 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -5.9751945e+02   5.541356e+01   0.000000e+00      0s
       6   -4.6475314e+02   0.000000e+00   0.000000e+00      0s

Solved in 6 iterations and 0.01 seconds
Optimal objective -4.647531429e+02

In [22]: obj = m.getObjective()

In [23]: m.addConstr(obj >= -460)
Out[23]: <gurobi.Constr *Awaiting Model Update*>

In [24]: m.optimize()
Gurobi Optimizer version 9.0.0 build v9.0.0rc2 (win64)
Optimize a model with 28 rows, 32 columns and 88 nonzeros
Coefficient statistics:
  Matrix range     [1e-01, 1e+01]
  Objective range  [3e-01, 1e+01]
  Bounds range     [0e+00, 0e+00]
  RHS range        [4e+01, 5e+02]
Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0   -4.6475314e+02   5.941429e-01   0.000000e+00      0s
       1   -4.6000000e+02   0.000000e+00   0.000000e+00      0s

Solved in 1 iterations and 0.01 seconds
Optimal objective -4.600000000e+02

As you can see, the second model is solved almost immediately within one iteration, by re-using the previous solution.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.