Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.

 View Only
Back to discussions
Expand all | Collapse all

Terminal Condition of Self-implementing Cutting Plane for Pure IP

  • 1.  Terminal Condition of Self-implementing Cutting Plane for Pure IP

    Posted Mon March 05, 2012 04:29 AM

    Originally posted by: waldstein


    Hi all,
    here is an simple IP:
    min -7x1-9x2
    s.t. -x1+3x2<=6
    7x1+x2<=35
    x1,x2 is integer

    It's solution is x1=4,x2=3,and optimum = -55

    But when I use my own cutting plane(Gomory cut and primal(dual) simplex) to solve it,
    after 2 cuts are generated, I obtain a solution of: x1=0000000000000009,x2 =3, optimum= 55.000000000000007

    Since x1 is not treated as integer, a new cut on x1 is generated again. And again, and again...

    So it is obvious that the algorithm should terminate after two cuts has been generated.

    My quesions are:
    1 why Gomory cut can not generate "exact" integer solution?
    2 What difference can we accept? I also tested other problems and the same situation appeared

    Thanks!
    #CPLEXOptimizers
    #DecisionOptimization


Related Content