2
$\begingroup$

In general, I can compute an MILP using a solver of my choice (Gurobi, ...) and stop it at any time, change parameters/constraints add variables. Take the so far best solution computed based on the last run and model as initial guess for the variables and start again.

Is it also possible to do those (or some of those) changes during computation and dynamically add changed parameters, does it have advantages?

E.g. computing some partitioning on a graph and adding or removing edges during computation, fixing variables to desired variables without stopping the optimization process.

$\endgroup$
3
  • 1
    $\begingroup$ - For the addition of variables, common cases in which it is applied for, are the Column Generation algorithms (check chapter twelve jstor.org/stable/j.ctt7s8xg?turn_away=true, and arxiv.org/pdf/1806.00831.pdf): In these situations better dual bounds "may" be obtained, and sometimes, depending of the instance size, the only way to initialize an MILP algorithm is through CG. A CG algorithm may also detach variables. to continue... $\endgroup$ Commented Feb 23 at 11:49
  • 1
    $\begingroup$ - For the addition of constraints, we have the classical branch and cut algorithm (en.wikipedia.org/wiki/Branch_and_cut), which is a single tree algorithm. As for the case you mentioned, when you iteratively run MILP problems, you have a multi-tree scheme, which is also applied for NLPs (link.springer.com/chapter/10.1007/978-3-030-22788-3_2). For the removal of constraints, SHOT solver applies such technique for dealing with stagnation when solving nonconvex NLPs (link.springer.com/article/10.1007/s10898-021-01006-1). $\endgroup$ Commented Feb 23 at 11:49
  • 1
    $\begingroup$ Using Gurobi you can make changes to parameters and add constraints without needing to restart the solve. You can call optimize() and the solve will resume from where it left off. In this way you could use Gurobi callbacks to define custom termination criteria, after which you make these sorts of changes, then resume. Presumably you would embed this approach in a loop. Adding variables or changing existing constraints or objective function will throw out the tree and the solve won't resume from where it was stopped, but you could still provide a "MIP start" and maybe it would be valid. $\endgroup$
    – Riley
    Commented Feb 23 at 15:31

1 Answer 1

1
$\begingroup$

Some solvers will allow you to add constraints on the fly, possibly with some restrictions. I don't think any would allow you to add variables mid-solve. Column generation techniques allow you to add variables, but between solves, not during a solve.

A key limitation to what you have in mind is that the solver would require that any change you made not invalidate decisions made earlier in the solution process. In your graph partitioning example, if you remove an edge then a previously encountered feasible solution might become infeasible. If that solution was used to prune nodes, then it would be possible some of those nodes were pruned in error, and in fact might contain the true optimum. If you add a variable, conceivably a node previously pruned for infeasibility would now become feasible (and, again, potentially contain the optimum).

If a solver lets you add constraints via a callback, reducing the feasible region, then it in effect binds you "contractually" to add those constraints as soon as it encounters a candidate solution that violates them. In other words, it is on you to ensure that a solution feasible in the current problem but violating a constraint you have not yet added is not accepted as an incumbent, because accepting it could result in pruning portions of the tree that should not be pruned.

$\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.