•  Gurobi Staff

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ł

•   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

•  Gurobi Staff

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ł