3
$\begingroup$

I have tried to understand the method of relaxing an integer program. I am in the process of implementing and solving a MIP for the FJSSP. For this I use the python-MIP package to solve it. From my understanding, one does relax an integer program, solve it through a branch and bound algorithm which branches on specific fractional variables and possibly get an integer solution. I have tried to do this by relaxing my original integer model and solving it, which gives me an optimal solution with fractional values for my decision variable.

But how do I get the integer values from my fractional solution now?

Do I need to perform a Branch and Bound algorithm on the fractional solution?

I am a little bit confused because in the description of python-MIP, it said that the solver already uses an Branch and Cut Algorithm to solve it, so I thought the relaxed model would give me an integer solution by branching through the tree.

$\endgroup$

1 Answer 1

4
$\begingroup$

First off, the term "relaxation" is a bit ambiguous. You can relax a MIP model either by relaxing the integrality constraints (at which point it becomes a linear program) or by relaxing some of the constraints (essentially allowing infeasible solutions to be considered). I suspect you are interested in relaxing integrality.

If you relax integrality, the problem is solved as a linear program (using some variant of the simplex method), not by branch-and-bound. The main reason for doing this is to get a bound on the optimal objective value. The solution you get from the LP is "superoptimal", meaning the optimal solution to the original problem cannot have a better objective value (and may have a worse objective value). There is no "easy" way to recover the true optimum from the relaxed solution. You can try rounding variables, which may produce a "good" solution but often will produce an infeasible one. You can try sequential rounding: round one variable and fix its value; solve the updated LP; rinse and repeat. Again, there is no guarantee you end up with a feasible solution, let alone an optimal one.

The branch-and-cut algorithm used by the solver when you solve the original MIP model does in fact solve an LP relaxation at each node of the search tree, both to establish that there is some hope the node harbors a feasible solution and to detect whether there is any chance it harbors a better solution than what you currently have. If the answer to either question is no, the node is pruned. This is done automatically within the solver, so you do not need to do any explicit relaxation yourself.

$\endgroup$
3
  • $\begingroup$ Thank you very much for your answer. I was in fact talking about integrality constraints. So since the solver already relaxes my problem automatically, is there any way I can add constraints to my mip model at specific nodes if a certain condition is true? I've read about the term "callback" but I don't fully understand it yet. $\endgroup$ May 13 at 18:53
  • 1
    $\begingroup$ Some (not all) solvers support callbacks when you are using a programming API (such as writing code in Python that calls the solver). A callback is a mechanism that lets the solver pause operation at certain key points (for instance, when it thinks it might have a new incumbent solution, or when it is solving the LP relaxation at a node and adding cuts). When it pauses, it calls a function in the user's code, passing some information about the current solver status and letting the user send some instructions back to the solver). ... $\endgroup$
    – prubin
    May 13 at 22:02
  • $\begingroup$ ... The value returned by the user function might tell the solver to add a cut, or to reject a candidate solution (and perhaps add a cut the candidate violates), or possibly something else. $\endgroup$
    – prubin
    May 13 at 22:03

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.