Decision Optimization

Decision Optimization

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


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only
Back to discussions
Expand all | Collapse all

is branch and cut algorithm exact or approximate?

  • 1.  is branch and cut algorithm exact or approximate?

    Posted 12/28/08 04:23 AM

    Originally posted by: SystemAdmin


    [cplex_ma said:]

    Hi,

    We know that Binary Linear programs are NP-hard but they can be solved using branch and cut algorithm. So, does that mean branch and cut algorithm are approximate algorithms not exact one?

    Thanks
    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: is branch and cut algorithm exact or approximate?

    Posted 12/28/08 01:40 PM

    Originally posted by: SystemAdmin


    [anahana said:]

    Being NP-hard or NP-complete has nothing to do with the problem being binary or not.

    Branch and Bound, Branch and Cut, Branch and Price, Cutting planes, and Lagrangian relaxation are all exact methods for optimization, if any is applied to an NP-hard problem, with small instances, optimal solutions are found; however, practical problems are large and optimal solutions can not be found in polynomial time.
    #CPLEXOptimizers
    #DecisionOptimization


Related Content