[OFF-TOPIC] State of the art (mixed) integer optimization algorithm

29 views
Skip to first unread message

G

unread,
Mar 12, 2015, 6:43:34 AM3/12/15
to yal...@googlegroups.com
Hello,

I was wondering what are the algorithm implemented in the best solvers? Branch and bound, Gomory's cut, what else?
What are the best reference can I find about that?

P.S. Sorry for this very general and off-topic question. I ask in this group to have some opinion, I am afraid that asking on some solver's group I won't get any answer :)

Cheers

Johan Löfberg

unread,
Mar 12, 2015, 7:17:11 AM3/12/15
to yal...@googlegroups.com
They all use branch&bound + cuts.

You can see the vast number of cuts available by simply looking in the options structures. Here is an excerpt from gurobi options
 Cuts: -1
           
CliqueCuts: -1
           
CoverCuts: -1
       
FlowCoverCuts: -1
         
FlowPathCuts: -1
         
GUBCoverCuts: -1
         
ImpliedCuts: -1
           
MIPSepCuts: -1
             
MIRCuts: -1
             
ModKCuts: -1
         
NetworkCuts: -1
           
SubMIPCuts: -1
         
ZeroHalfCuts: -1
         
CutAggPasses: -1
           
CutPasses: -1
         
GomoryPasses: -1

gurobi displays the number of cuts (and which ones) it used after it finishes

There are numerous presentations and papers to read. Just google mixed integer linear programming bixby, and you will find interesting stuff by cplex developers, or mixed integer linear programming rothberg to find equally interesting stuff from gurobi, etc


Reply all
Reply to author
Forward
0 new messages