10
$\begingroup$

I have an MILP model to which I get an integer feasible solution as a result of a heuristic search. In this particular example, the initial solution turns out to be the optimal solution, which I prove through B&B after solving 3000 LPs (20 Minutes of solution time), which is frustrating.

I can use the value of the initial solution as a lower bound on the optimisation problem (maximization case).

Can I derive anything else other than a lower bound from that solution?

$\endgroup$
8
$\begingroup$

Many solvers have an option to control the "emphasis" (feasibility versus optimality) of the tree search. If you suspect that your initial solution is already optimal, set this option to emphasize optimality, which will make cut generation more aggressive and do some other similar things.

Another approach is to explicitly apply reduced-cost fixing to fix the values of variables, without loss of optimality. Many solvers do this automatically, but maybe not as aggressively as you could do yourself.

A natural idea that has come up many times before is to add an explicit objective cut of the form $\sum_j c_j x_j \ge \hat{z}$, where $\hat{z}$ is the objective value of your initial solution. The conventional wisdom is that doing this is usually a bad idea, in part because it often adds a dense constraint that causes numerical difficulty for the underlying LP solves. But it is easy to try.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Re Rob's last point: if you want to do this, it is usually better to create a variable $z$ to represent the objective function, set $z=\sum_j c_j x_j$ as a constraint, maximize $z$ and set $\hat{z}$ as a lower bound for $z$. This does not avoid the addition of a dense constraint, but I believe it avoids/reduces problems with dual degeneracy. $\endgroup$ – prubin Mar 28 at 19:06
  • $\begingroup$ I am still in the phase of solving my problem with GAMS. GAMS requires to model the objective function the way you propose it (z=∑jcjxj). Now setting z.lo to the initial solution (z.lo is the gams notation for lower bound) implements your idea. An experiment shows that it helps for this particular instance of the problem. As for the density of the objective function, it must not always be true. The objective function need not involve all the variables of the problem. Or is there anything I misunderstand here? $\endgroup$ – Clement Mar 28 at 22:16
  • $\begingroup$ Right, the density of the objective depends on your problem. Beyond density, a potential pitfall is that it creates ties in node bounds, as discussed here. But I'm glad this simple idea worked in your case. $\endgroup$ – RobPratt Mar 28 at 22:22
  • $\begingroup$ Hi Rob! I had a look in the link you provided. It seems that the idea of adding the constraint is not considered to be useful. That contradicts my experience so far. My feeling was that cutting a part of the feasible region of an LP without excluding the optimum is always helpful. $\endgroup$ – Clement Mar 28 at 23:04
  • $\begingroup$ With MILP, you can hardly ever say always or never. :) $\endgroup$ – RobPratt Mar 29 at 0:05
3
$\begingroup$

You can also submit the solution to the MILP solver. The solver should then use the bound from it automatically. Further, it might use the solution values for various improvement heuristics (e.g. neighborhood searches).

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thank you for making this explicit. I had assumed @Clement was already doing that, but maybe not. Some solvers even allow you to input multiple solutions. $\endgroup$ – RobPratt Mar 29 at 15:17
  • $\begingroup$ Yes, it was also my first thought that OP has already submitted the solution (candidate). But then, there is no need to also set the primal bound, right? $\endgroup$ – Robert Schwarz Mar 30 at 11:32

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.