2
$\begingroup$

I'm trying to solve a MILP model iteratively, and at each iteration a few constraints are added to the problem that cut off the previous optimal solution. I'm trying to figure out ways to implement a warm-starting type algorithm instead of resolving the problem from scratch. I would appreciate any helps/ideas/recent researches etc that help me start devising a smart warm start (beyond the idea of only using dual simplex) for this problem.

$\endgroup$
4
  • 4
    $\begingroup$ Welcome to ORSE. Do you need to solve to optimality in each iteration, or can you stop and generate constraints when an integer-feasible (but not necessarily optimal) solution is produced? Also, which solver are you using? $\endgroup$
    – prubin
    Apr 12, 2022 at 18:50
  • $\begingroup$ Thanks. I need so solve to optimality in each iteration. Regarding the solver, I’m open to suggestions. I guess I will need to use an open source solver for this type of warm starting. $\endgroup$
    – jackson
    Apr 13, 2022 at 0:42
  • $\begingroup$ Solvers are unlikely to allow a warm start in this context (other than maybe warm starting the solution of the root node LP relaxation) because they cannot trust most of the previous node tree. So the node tree has to be rebuilt from scratch. $\endgroup$
    – prubin
    Apr 13, 2022 at 15:20
  • $\begingroup$ I’m open to using open source solvers like symphony. I’m just looking for an idea on how to use the previous tree. $\endgroup$
    – jackson
    Apr 13, 2022 at 17:10

3 Answers 3

4
$\begingroup$

Here's a Gurobi implementation of the TSP using lazy constraints that are added iteratively throughout the solving process: tsp.py

In general, this type of approach is done using callbacks and most solvers support this.

$\endgroup$
3
  • $\begingroup$ Thanks, but lazy constraints are added while solving the problem. What I'm looking for is an approach to fully solve the problem to optimality first, then add a set of constraints, then fully solve it to optimality again, then add new constraints again, so on so forth. $\endgroup$
    – jackson
    Apr 13, 2022 at 14:56
  • $\begingroup$ Then you should probably define what "the problem" actually is. SCIP has a mode to reuse the existing tree (re-optimization) for a modified model but AFAIK you can only restrict the feasible domain. $\endgroup$
    – mattmilten
    Apr 13, 2022 at 21:57
  • $\begingroup$ @jackson, do you try solving the problem iteratively, as you mentioned, and adding a warm-start in each stage? What the result was? $\endgroup$
    – A.Omidi
    Apr 14, 2022 at 18:54
3
$\begingroup$

A couple of ideas, but which require to understand a bit how a MILP solver works internally, are not particularly easy to implement and are not guaranteed of success:

  • Use a branching strategy relying on pseudo-costs. Keep the pseudo-costs of the variables between the consecutive solves, or use the values of the pseudo-costs of the previous solve to initialize the pseudo-costs of the next solve or to set priorities to the variables

  • Run a local branching heuristic using the solution of the previous solve as reference point. Finding a good solution quickly might speed up the resolution

  • Favor the type and intensiveness of cuts which worked well in the previous solve

Basically, for every component which is learned dynamically by the solver, you can try to re-use the learned knowledge for the next solve

$\endgroup$
2
$\begingroup$

I doubt it's possible to recycle the previous tree. Nodes that were pruned as infeasible before would still be infeasible, but nodes pruned on bound might have been pruned based on a "feasible" solution that is now infeasible. Also, bounds on old nodes might very well change given the new constraints. It would be theoretically possible to retain all that info and revisit the old tree, revising bounds, resuscitating (perhaps temporarily) nodes and so on, but my guess is that it would amount to more work than just starting from scratch would ... plus it would mean a lot of developer time and added code to handle and "edge case" that likely would not arise very often.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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