Solving a MIP by Relaxation

Question

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.

Answer 1

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.