Xjyuk

Was it really unprofessional of me to leave without asking for a raise first?

How is this practical and very old scene shot?

What is the purpose of putting a capacitor on the primary side of a step-down transformer?

Does any Greek word have a geminate consonant after a long vowel?

Sharing referee/AE report online to point out a grievous error in refereeing

My colleague is constantly blaming me for his errors

I'm reinstalling my Linux desktop, how do I keep SSH logins working?

Details of video memory access arbitration in Space Invaders

Why won't the ground take my seed?

Buliding a larger matrix from a smaller one

Just graduated with a master’s degree, but I internalised nothing

Can a function nowhere continuous have a connected graph?

Why was Mal so quick to drop Bester in favour of Kaylee?

Donkey as Democratic Party symbolic animal

How does Resilient sphere (cast via contingency) interact with an existing Silence spell?

How to describe POV characters?

Is the location of an aircraft spoiler really that vital?

Most elegant way to write a one shot IF

Are all commands with an optional argument fragile?

How did installing this RPM create a file?

Using a concentration spell on top of another spell from another spell list?

Security Patch SUPEE-11155 - Possible issues?

What's the rule for a natural 20 on a Perception check?

What does the phrase "building hopping chop" mean here?

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

5

$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 5 hours ago

E. Tucker

69211 silver badge1515 bronze badges

asked 8 hours ago

Sriram SankaranarayananSriram Sankaranarayanan

6944 bronze badges

New contributor

Sriram Sankaranarayanan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Are you asking specifically about stable set/vertex cover/coloring, or are those just illustrative examples?
  $endgroup$
  – LarrySnyder610
  8 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  They are illustrative examples.
  $endgroup$
  – Sriram Sankaranarayanan
  8 hours ago
  

  
  
  
  

add a comment | 

5

$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 5 hours ago

E. Tucker

69211 silver badge1515 bronze badges

asked 8 hours ago

Sriram SankaranarayananSriram Sankaranarayanan

6944 bronze badges

New contributor

Sriram Sankaranarayanan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Are you asking specifically about stable set/vertex cover/coloring, or are those just illustrative examples?
  $endgroup$
  – LarrySnyder610
  8 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  They are illustrative examples.
  $endgroup$
  – Sriram Sankaranarayanan
  8 hours ago
  

  
  
  
  

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 5 hours ago

E. Tucker

69211 silver badge1515 bronze badges

asked 8 hours ago

Sriram SankaranarayananSriram Sankaranarayanan

6944 bronze badges

New contributor

Sriram Sankaranarayanan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|improve this question

edited 5 hours ago

E. Tucker

69211 silver badge1515 bronze badges

asked 8 hours ago

Sriram SankaranarayananSriram Sankaranarayanan

6944 bronze badges

New contributor

Sriram Sankaranarayanan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|improve this question

edited 5 hours ago

E. Tucker

69211 silver badge1515 bronze badges

asked 8 hours ago

Sriram SankaranarayananSriram Sankaranarayanan

6944 bronze badges

New contributor

Sriram Sankaranarayanan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

edited 5 hours ago

E. Tucker

69211 silver badge1515 bronze badges

edited 5 hours ago

E. Tucker

69211 silver badge1515 bronze badges

asked 8 hours ago

Sriram SankaranarayananSriram Sankaranarayanan

6944 bronze badges

New contributor

Sriram Sankaranarayanan is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 8 hours ago

Sriram SankaranarayananSriram Sankaranarayanan

6944 bronze badges

3 Answers
3

active

oldest

votes

3

$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 7 hours ago

prubinprubin

1,17133 silver badges1111 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  SAS automatically detects the network structure and issues a log message that suggests using network simplex.
  $endgroup$
  – Rob Pratt
  6 hours ago
  

  
  
  
  

add a comment | 

2

$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 5 hours ago

Rob PrattRob Pratt

50777 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
  5 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  2 hours ago
  
  

  
  
  
  

add a comment | 

1

$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 8 hours ago

LarrySnyder610LarrySnyder610

3,15366 silver badges4747 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
  5 hours ago
  
  

  
  
  
  

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
);



);

Sriram Sankaranarayanan is a new contributor. Be nice, and check out our Code of Conduct.

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$

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 7 hours ago

prubinprubin

1,17133 silver badges1111 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  SAS automatically detects the network structure and issues a log message that suggests using network simplex.
  $endgroup$
  – Rob Pratt
  6 hours ago
  

  
  
  
  

add a comment | 

3

$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 7 hours ago

prubinprubin

1,17133 silver badges1111 bronze badges

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  SAS automatically detects the network structure and issues a log message that suggests using network simplex.
  $endgroup$
  – Rob Pratt
  6 hours ago
  

  
  
  
  

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 7 hours ago

prubinprubin

1,17133 silver badges1111 bronze badges

$endgroup$

share|improve this answer

answered 7 hours ago

prubinprubin

1,17133 silver badges1111 bronze badges

answered 7 hours ago

prubinprubin

1,17133 silver badges1111 bronze badges

answered 7 hours ago

prubinprubin

1,17133 silver badges1111 bronze badges

2

$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 5 hours ago

Rob PrattRob Pratt

50777 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
  5 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  2 hours ago
  
  

  
  
  
  

add a comment | 

2

$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 5 hours ago

Rob PrattRob Pratt

50777 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
  5 hours ago
  

  
  
  
  


• 
  
  
  

  
  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
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $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
  2 hours ago
  
  

  
  
  
  

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 5 hours ago

Rob PrattRob Pratt

50777 bronze badges

$endgroup$

share|improve this answer

answered 5 hours ago

Rob PrattRob Pratt

50777 bronze badges

answered 5 hours ago

Rob PrattRob Pratt

50777 bronze badges

answered 5 hours ago

Rob PrattRob Pratt

50777 bronze badges

1

$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 8 hours ago

LarrySnyder610LarrySnyder610

3,15366 silver badges4747 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
  5 hours ago
  
  

  
  
  
  

add a comment | 

1

$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 8 hours ago

LarrySnyder610LarrySnyder610

3,15366 silver badges4747 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
  5 hours ago
  
  

  
  
  
  

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 8 hours ago

LarrySnyder610LarrySnyder610

3,15366 silver badges4747 bronze badges

$endgroup$

share|improve this answer

answered 8 hours ago

LarrySnyder610LarrySnyder610

3,15366 silver badges4747 bronze badges

answered 8 hours ago

LarrySnyder610LarrySnyder610

3,15366 silver badges4747 bronze badges

answered 8 hours ago

LarrySnyder610LarrySnyder610

3,15366 silver badges4747 bronze badges