# Graph problems as integer programs

Suppose I give a solver (CPLEX, Gurobi, SCIP or anything else) an IP which is a reformulation of a stable set problem (or vertex cover problem or coloring problem) of some graph, is there a way I can tell the solver that it is a stable set or vertex cover instance? Will that enhance the heuristics used by the solver?

• Are you asking specifically about stable set/vertex cover/coloring, or are those just illustrative examples? – LarrySnyder610 Jun 25 '19 at 17:02
• They are illustrative examples. – Sriram Sankaranarayanan Jun 25 '19 at 17:04

I suspect there are a few specific problems for which the answer is "yes," and I hope others will answer to provide examples of those.

But in general I believe the answer is "no." For example, if you formulate the minimum-spanning tree problem as an IP and try to solve it with a general-purpose solver, it will be much slower than just using Prim's or Kruskal's algorithm. If there were some option you could set that says "hey, this is an MST!", then the solver would basically have to have a ton of separate graph algorithms (Prim's for MST, Dijkstra's for shortest path, etc.) built into it, which is not really what general-purpose solvers are designed to do.

• Better would be if the solver could deduce that it was an MST, SP, etc. and use the specialized solver under the hood. But, that is not easy. Deducing a network flow (MCF) model is also "hard", but is based on work from back in the 80s - Bixby, Fourer. – Matthew Galati Jun 25 '19 at 20:27

CPLEX has a parameter (RootAlgorithm) that lets you select the method for solving an LP (or for solving the root node relaxation of an ILP). The default setting is to let CPLEX choose, which usually (but not always) results in it using dual simplex. One of the choices is "network simplex", which you might try for a graph problem. I don't know whether CPLEX would detect the graph structure and automatically try network simplex if left on the default setting.

• SAS automatically detects the network structure and issues a log message that suggests using network simplex. – RobPratt Jun 25 '19 at 19:29

Often such problems have side constraints, and this patent covers that more general case, using Dantzig-Wolfe decomposition with the network subproblem (MST, TSP, etc.) expressed compactly (not algebraically) and solved with a specialized solver. This functionality is implemented in SAS but currently undocumented. Please contact me if you are interested in using it.

• I talked briefly about the design for this in SAS/OR here. See slides 22-28 for some examples. – Matthew Galati Jun 25 '19 at 20:15
• this is patented??!? I guess, GCG then violates this, as eg we detect when the subproblem is a stable set problem and apply a specialzed pricing solver then... – Marco Lübbecke Jun 25 '19 at 22:05
• The "automated" part in the patent title is actually not the problem recognition. The "automated" part is just the implementation of DW. The patent is related to the mapping between the graph subproblem and the math programming model ("using minimal syntax") - in the context of the modeling language. The "idea" from the patent standpoint is just the ease of conveyance for the user (I think - I am not a lawyer, just an OR guy). The automated detection stuff GCG and DECOMP do is a different - and, in my opinion, much more important area of research. – Matthew Galati Jun 25 '19 at 22:43