Decision Optimization

Decision Optimization

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


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only
Expand all | Collapse all

Does Column Generation give the optimal solution? Why is it called an e-optimal method?

  • 1.  Does Column Generation give the optimal solution? Why is it called an e-optimal method?

    Posted 03/25/17 06:10 PM

    Originally posted by: abhzap


    Hi All,

    I have been working on a column-generation scheme for quite a while now.

    The e-optimality: (ILPvalue - LPvalue)/LPvalue, seems to be an indicator of how good a solution is.

    But, I have a trouble understanding how that can be?

    I mean LP value is the lower bound for the optimal solution and e-optimal tells how far away I am from it. 

    I am having trouble relating this to the quality of the solution.

    Morever, CG is sophisticated which requires many hours to formulate, develop and run.

    But if at the very end you are getting bad e-optimal solution, it is really anti-climatic.

    Would it have been  better to go ahead with meta heuristics or some other technique? 

    Any insight on this will be really appreciated.

    Thanks,

    -abhzap

     

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: Does Column Generation give the optimal solution? Why is it called an e-optimal method?

    Posted 04/05/17 03:37 PM

    I'll assume a min problem here for concreteness.

    "Column generation" covers a multitude of sins. Some instances of CG are exact (guaranteed optimal solution, barring numerical misadventures). Dantzig-Wolfe decomposition of an LP fits here. Others are heuristic, such as the famous Gilmore-Gomory cutting stock heuristic. I suspect you are thinking along the lines of the latter.

    The phrase "quality of the solution" usually is used to mean how close the solution is to optimal. For a MILP, you'd like to compute (your ILP result - best ILP result)/(best ILP result), but you don't typically know the optimal objective value. The best you can do is substitute the LP lower bound and hope that the lower bound is not excessively loose. (The looser it is, the less meaningful the quality measure is.)

    If you end up getting bad results from CG (and this is of course possible), then possibly you would have been better off using a good heuristic or metaheuristic. Heuristics and metaheuristics typically do not provide lower bounds, so you won't have a quality estimate, but if that's important you can always set up a MILP model, relax it to an LP, solve that and get a bound. That's probably fairly easy. On the other hand, suppose you go straight to a heuristic, spend time coding that and get results that are less than satisfying. Meanwhile, CG might have done better, and perhaps much better (but perhaps much worse). My point is that unless you know in advance that a particular method will do well on your problem (perhaps from past experience, or from credible published results), you will always face the possibility of unsatisfactory return on your investment of effort. Such is life in the optimization arena.

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 3.  Re: Does Column Generation give the optimal solution? Why is it called an e-optimal method?

    Posted 04/05/17 04:12 PM

    Originally posted by: abhzap


    Thank you, that was really helpful!


    #CPLEXOptimizers
    #DecisionOptimization