Constraint violation in finding the extreme ray.

Answered

Comments

7 comments

  • Jaromił Najman

    Hi Chao,

    The constraint corresponding to 9.39 and the extreme ray you produced are

    0 1 0 0    0    1 0 0 1   0 0 0 0 1 0 0 1   0 0 0 0    0 1 0   1 0 0 1 0 0 1 1 0 0
    0 0 0 0 -500 -500 0 0 0 500 0 0 0 0 0 0 0 500 0 0 0 -500 0 0 500 0 0 0 0 0 0 0 0 0 

    The HPC extreme ray adds up to 0, because you have \( (- 500 + 500)\) as these are the only variables participating with a \(1\) coefficient. Thus, the constraint is satisfied.

    It is normal to see different solutions provided by Gurobi when executed on different machines. For more information, see [Is Gurobi Optimizer deterministic?](https://support.gurobi.com/hc/en-us/articles/360031636051-Is-Gurobi-Optimizer-deterministic-)

    Best regards,
    Jaromił

    0
    Comment actions Permalink
  • Zhengchao Wang

    Hi Jaromil,

    Thank you for your help. I agree that this constraint is satisfied. However, there is another constraint (the 11th line in A matrix)  that is not satisfied.

    0 0 0 0 -500 -500 0 0 0 500 0 0 0 0 0 0 0 500 0 0 0 -500 0 0 500 0 0 0 0 0 0 0 0 0
    0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0

    Thank you very much if you could have a look at this one.

    Best wishes,

    Chao

     

    0
    Comment actions Permalink
  • Jaromił Najman

    Hi Chao,

    This is correct. However, please note that the original solution point satisfies the constraint. You are, correct that you can scale the objective function, but you also have to scale the constraints properly. As an example take

    \[\begin{align} \min_x &-x \\ \text{s.t.} &x \leq 1 \end{align}\]

    The optimal solution point is \(x=1\). Now, when you multiply \(x\) with \(1000\) the constraint \(x \leq 1\) is no longer satisfied, because \(1000\not\leq 1\). In this case you have to scale the constraint by \(1000\) as well.

    Best regards,
    Jaromił

    0
    Comment actions Permalink
  • Zhengchao Wang

    Hi Jaromil,

    I agree with your example. However, in your example, the problem is bounded so the solution you proposed is not an extreme ray.

    On the contrary, in my case, I am trying to obtain an extreme ray from GUROBI as my problem is unbounded. As I said, for an extreme ray, we can multiply any large positive factor without violate the constraint. So my example above  show that GUROBI on the HPC does not give me a correct extreme ray.

    Thank you!

    Best wishes,

    Chao

    0
    Comment actions Permalink
  • Jaromił Najman

    Hi Chao,

    Correct, I will open a ticket for this to discuss this internally.

    Best regards,
    Jaromił

    0
    Comment actions Permalink
  • Zhengchao Wang

    Hi Jaromil,

    Thank you! I am looking forward to knowing how to solve the issue. 

    Best wishes,

    Chao

    0
    Comment actions Permalink
  • Jaromił Najman

    This issue has been resolved in the 9.1 release.

    0
    Comment actions Permalink

Please sign in to leave a comment.

Powered by Zendesk