Is non-integer part of a MIP solution an extreme point?




  • Jaromił Najman

    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,

    Comment actions Permalink
  • Luca Wrabetz

    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? 


    Comment actions Permalink
  • Jaromił Najman

    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,

    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk