Ttdfjt

Why did moving the mouse cursor cause Windows 95 to run more quickly?

Data normalization before or after train-test split?

Is conquering your neighbors to fight a greater enemy a valid strategy?

How to calculate a conditional PDF in mathematica?

Does a multiclassed wizard start with a spellbook?

My players like to search everything. What do they find?

What is this arch-and-tower near a road?

Can 4 Joy cons connect to the same Switch?

What is the name of the technique when an element is repeated at different scales?

Do the 26 richest billionaires own as much wealth as the poorest 3.8 billion people?

Speeding up thousands of string parses

How serious is plagiarism in a master’s thesis?

In the Seventh Seal why does Death let the chess game happen?

How to deal with a Murder Hobo Paladin?

How can solar sailed ships be protected from space debris?

Should I warn my boss I might take sick leave

Bypass with wrong cvv of debit card and getting OTP

What is the addition in the re-released version of Avengers: Endgame?

Can a Time Lord survive with just one heart?

How would an Amulet of Proof Against Detection and Location interact with the Comprehend Languages spell?

How to iterate equal values with the standard library?

Does Evolution Sage proliferate Blast Zone when played?

How can I effectively map a multi-level dungeon?

Interview Question - Card betting

Graph problems as integer programs

Neigbourhoods in Large Neighbourhood Search (LNS) algorithmsSolver rounding precision vs programming language rounding precisionWhat are the tradeoffs between “exact” and Reinforcement Learning methods for solving optimization problemsDoes the API affect the time Gurobi requires to find an optimum?When to use indicator constraints versus big-M approaches in solving (mixed-)integer programsOn what kind of problems a local search may perform better than MIP / CP techniques?Connectivity of two nodes in an arbitrary undirected graphHow to select a Constraint Programming SolverHeuristics for mixed integer linear and nonlinear programs

7

$begingroup$

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?

solver graphs heuristics

share|improve this question

edited Jun 25 at 19:52

E. Tucker

73811 silver badge1616 bronze badges

asked Jun 25 at 16:53

Sriram SankaranarayananSriram Sankaranarayanan

3601212 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Are you asking specifically about stable set/vertex cover/coloring, or are those just illustrative examples?
  $endgroup$
  – LarrySnyder610
  Jun 25 at 17:02
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  They are illustrative examples.
  $endgroup$
  – Sriram Sankaranarayanan
  Jun 25 at 17:04
  

  
  
  
  

add a comment | 

7

$begingroup$

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?

solver graphs heuristics

share|improve this question

edited Jun 25 at 19:52

E. Tucker

73811 silver badge1616 bronze badges

asked Jun 25 at 16:53

Sriram SankaranarayananSriram Sankaranarayanan

3601212 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Are you asking specifically about stable set/vertex cover/coloring, or are those just illustrative examples?
  $endgroup$
  – LarrySnyder610
  Jun 25 at 17:02
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  They are illustrative examples.
  $endgroup$
  – Sriram Sankaranarayanan
  Jun 25 at 17:04
  

  
  
  
  

add a comment | 

$begingroup$

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?

solver graphs heuristics

share|improve this question

edited Jun 25 at 19:52

E. Tucker

73811 silver badge1616 bronze badges

asked Jun 25 at 16:53

Sriram SankaranarayananSriram Sankaranarayanan

3601212 bronze badges

$endgroup$

share|improve this question

edited Jun 25 at 19:52

E. Tucker

73811 silver badge1616 bronze badges

asked Jun 25 at 16:53

Sriram SankaranarayananSriram Sankaranarayanan

3601212 bronze badges

share|improve this question

edited Jun 25 at 19:52

E. Tucker

73811 silver badge1616 bronze badges

asked Jun 25 at 16:53

Sriram SankaranarayananSriram Sankaranarayanan

3601212 bronze badges

edited Jun 25 at 19:52

E. Tucker

73811 silver badge1616 bronze badges

edited Jun 25 at 19:52

E. Tucker

73811 silver badge1616 bronze badges

asked Jun 25 at 16:53

Sriram SankaranarayananSriram Sankaranarayanan

3601212 bronze badges

asked Jun 25 at 16:53

Sriram SankaranarayananSriram Sankaranarayanan

3601212 bronze badges

3 Answers
3

active

oldest

votes

3

$begingroup$

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.

share|improve this answer

answered Jun 25 at 17:12

LarrySnyder610LarrySnyder610

3,60677 silver badges5050 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  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.
  $endgroup$
  – Matthew Galati
  Jun 25 at 20:27
  
  

  
  
  
  

add a comment | 

7

$begingroup$

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.

share|improve this answer

answered Jun 25 at 18:06

prubinprubin

1,33133 silver badges1212 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  SAS automatically detects the network structure and issues a log message that suggests using network simplex.
  $endgroup$
  – Rob Pratt
  Jun 25 at 19:29
  

  
  
  
  

add a comment | 

6

$begingroup$

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.

share|improve this answer

answered Jun 25 at 19:59

Rob PrattRob Pratt

75788 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I talked briefly about the design for this in SAS/OR here. See slides 22-28 for some examples.
  $endgroup$
  – Matthew Galati
  Jun 25 at 20:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  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...
  $endgroup$
  – Marco Lübbecke
  Jun 25 at 22:05
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  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.
  $endgroup$
  – Matthew Galati
  Jun 25 at 22:43
  
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "700"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2for.stackexchange.com%2fquestions%2f735%2fgraph-problems-as-integer-programs%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

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.

share|improve this answer

answered Jun 25 at 17:12

LarrySnyder610LarrySnyder610

3,60677 silver badges5050 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  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.
  $endgroup$
  – Matthew Galati
  Jun 25 at 20:27
  
  

  
  
  
  

add a comment | 

3

$begingroup$

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.

share|improve this answer

answered Jun 25 at 17:12

LarrySnyder610LarrySnyder610

3,60677 silver badges5050 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  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.
  $endgroup$
  – Matthew Galati
  Jun 25 at 20:27
  
  

  
  
  
  

add a comment | 

$begingroup$

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.

share|improve this answer

answered Jun 25 at 17:12

LarrySnyder610LarrySnyder610

3,60677 silver badges5050 bronze badges

$endgroup$

share|improve this answer

answered Jun 25 at 17:12

LarrySnyder610LarrySnyder610

3,60677 silver badges5050 bronze badges

answered Jun 25 at 17:12

LarrySnyder610LarrySnyder610

3,60677 silver badges5050 bronze badges

answered Jun 25 at 17:12

LarrySnyder610LarrySnyder610

3,60677 silver badges5050 bronze badges

7

$begingroup$

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.

share|improve this answer

answered Jun 25 at 18:06

prubinprubin

1,33133 silver badges1212 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  SAS automatically detects the network structure and issues a log message that suggests using network simplex.
  $endgroup$
  – Rob Pratt
  Jun 25 at 19:29
  

  
  
  
  

add a comment | 

7

$begingroup$

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.

share|improve this answer

answered Jun 25 at 18:06

prubinprubin

1,33133 silver badges1212 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  SAS automatically detects the network structure and issues a log message that suggests using network simplex.
  $endgroup$
  – Rob Pratt
  Jun 25 at 19:29
  

  
  
  
  

add a comment | 

$begingroup$

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.

share|improve this answer

answered Jun 25 at 18:06

prubinprubin

1,33133 silver badges1212 bronze badges

$endgroup$

share|improve this answer

answered Jun 25 at 18:06

prubinprubin

1,33133 silver badges1212 bronze badges

answered Jun 25 at 18:06

prubinprubin

1,33133 silver badges1212 bronze badges

answered Jun 25 at 18:06

prubinprubin

1,33133 silver badges1212 bronze badges

6

$begingroup$

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.

share|improve this answer

answered Jun 25 at 19:59

Rob PrattRob Pratt

75788 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I talked briefly about the design for this in SAS/OR here. See slides 22-28 for some examples.
  $endgroup$
  – Matthew Galati
  Jun 25 at 20:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  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...
  $endgroup$
  – Marco Lübbecke
  Jun 25 at 22:05
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  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.
  $endgroup$
  – Matthew Galati
  Jun 25 at 22:43
  
  

  
  
  
  

add a comment | 

6

$begingroup$

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.

share|improve this answer

answered Jun 25 at 19:59

Rob PrattRob Pratt

75788 bronze badges

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I talked briefly about the design for this in SAS/OR here. See slides 22-28 for some examples.
  $endgroup$
  – Matthew Galati
  Jun 25 at 20:15
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  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...
  $endgroup$
  – Marco Lübbecke
  Jun 25 at 22:05
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  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.
  $endgroup$
  – Matthew Galati
  Jun 25 at 22:43
  
  

  
  
  
  

add a comment | 

$begingroup$

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.

share|improve this answer

answered Jun 25 at 19:59

Rob PrattRob Pratt

75788 bronze badges

$endgroup$

share|improve this answer

answered Jun 25 at 19:59

Rob PrattRob Pratt

75788 bronze badges

answered Jun 25 at 19:59

Rob PrattRob Pratt

75788 bronze badges

answered Jun 25 at 19:59

Rob PrattRob Pratt

75788 bronze badges