Skip to main content

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

Answered

Comments

4 comments

  • Official comment
    Simranjit Kaur
    Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Jaromił Najman
    Gurobi Staff 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ł

    0
  • Luca Wrabetz
    Gurobi-versary
    First Comment

    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
  • Jaromił Najman
    Gurobi Staff 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ł

    0

Post is closed for comments.