Is non-integer part of a MIP solution an extreme point?
Answered
Hi there, I had a small question about Gurobi's behavior when solving mixed-integer programs. In particular, suppose that the constraints look like
Ax + Bz <= b
x >= 0, continuous
z integer
After formulating this problem, and solving it, Gurobi returns a solution (x*, z*), where z* is integer. My question here is about the x* part of the solution. Is x* guaranteed to be an extreme point of the "restricted" polyhedron P = { x >= 0 | Ax <= b - Bz*} ?
The reason I ask is because my co-author and I are encountering a situation where we are solving a MIP with some of the binary variables fixed, and are obtaining solutions where the continuous part of the solution is not an extreme point of the restricted polyhedron.
My intuition for why the answer should be "yes" to my question would be that with default parameters, each node's relaxation is solved using dual simplex, so at least as far as the solutions to the relaxation at each node are concerned, the x part should be extreme. In addition, if one runs a heuristic to get a candidate for the integer part z, it seems it would be easiest to find x by solving the LP with z restricted.
My guess for why the answer could be no would be due to the behavior of heuristics.
Thank you for reading this -- any information you can provide would be greatly appreciated!
Best,
Velibor
-
Hi Velibor,
The statement is definitely not true for solutions with >0% gap. Since a heuristic solution can come from anywhere, we do not guarantee that the solution w.r.t. integer fixing is an extreme point of the polyhedron P you described.
What one can say is:
Statement: Let \((x^*,z^*)\) the unique optimal solution (0% MIPGap) of
\[\begin{align} \max\, &c^T x + d^T z \\
\text{s.t. } & Ax + B z \leq b \quad (1)\\
&x \geq 0 \\
& z \in \mathbb{Z}_{\geq 0} \end{align}\]
Then \(x^*\) is an extreme point of the polyhedron \(P=\{ x \mid x \geq 0, Ax + Bz^* \leq b\}\).Proof: We know that \(x^*\) is an extreme point of \(P\) if there exists a vector \(f\) and \(x^*\) is the unique optimal solution of
\[\begin{align} \max\, & f^T x \\
\text{s.t. } & x \in P \end{align}\]Now use \(f = c\) from \((1)\) to get
\[\begin{align} \max\, & c^T x \\
\text{s.t. } &Ax + Bz^* \leq b\quad (2) \\
&x\geq 0 \end{align}\]
Assume for contradiction that there exists a \(x'\) with \(x^* \neq x'\) and \(x'\) is an optimal solution to \((2)\). Then \((x',z^*)\) is feasible to \((1)\) with objective value \(c^Tx' + d^T z^* \geq c^T x^* + d^T z^*\) contradicting \((x^*,z^*)\) being the unique maximizer to \((1)\). Thus, \(x^*\) is the unique optimal solution of \((2)\), and is therefore an extreme point of \(P\). \(\square\)For the behavior you see, i.e., \(x^*\) not being an extreme point of \(P\), I see multiple explanations.
- the optimal solution is not unique
- the MIPGap is >0%
- there may be some numerical issues
Best regards,
Jaromił0 -
Hello, I am encountering some similar behavior, however I know from solving this small instance of my problem that exhibits the behavior, that the reason for the fractional values I am obtaining is that the solution is not unique. Is there a way to attempt to search for the integer extreme point when the MIP search returns a fractional optimal solution in this case?
Thanks
0 -
Hi Luca,
After optimization is finished, you could fix all integer-valued variables and then make all non-integer valued variables actual integer variables and finally re-optimize. Through the fixing, you make the solution space way smaller and the problem (hopefully) way smaller as well such that the re-optimization can be performed faster than the original run.
Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
3 comments