Mfcttrf

Are these intended activities legal to do in the USA under the VWP?

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

How can a valley surrounded by mountains be fertile and rainy?

Lifting a probability measure to the power set

What game is this character in the Pixels movie from?

Adjective for 'made of pus' or 'corrupted by pus' or something of something of pus

Do launching rockets produce a sonic boom?

Could the Q destroy the universe?

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

Donkey as Democratic Party symbolic animal

Different budgets within roommate group

Why do we use a cylinder as a Gaussian surface for infinitely long charged wire?

Chords behaving as a melody

How did Lefschetz do mathematics without hands?

Who are these Discworld wizards from this picture?

Most important new papers in computational complexity

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

Why does the same classical piece sound like it's in a different key in different recordings?

Is there a legal way for US presidents to extend their terms beyond four years?

Should I share with a new service provider a bill from its competitor?

Why is Japan trying to have a better relationship with Iran?

Put my student loan in parents’ second mortgage - help?

One folder having two different locations on Ubuntu 18.04

Is it okay to fade a human face just to create some space to place important content over it?

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,14366 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,14366 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,14366 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,14366 silver badges4747 bronze badges

$endgroup$

share|improve this answer

answered 8 hours ago

LarrySnyder610LarrySnyder610

3,14366 silver badges4747 bronze badges

answered 8 hours ago

LarrySnyder610LarrySnyder610

3,14366 silver badges4747 bronze badges

answered 8 hours ago

LarrySnyder610LarrySnyder610

3,14366 silver badges4747 bronze badges