Graph problems as integer programsNeigbourhoods 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
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
$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
edited 5 hours ago
E. Tucker
6921 silver badge15 bronze badges
asked 8 hours ago
Sriram SankaranarayananSriram Sankaranarayanan
694 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$
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
edited 5 hours ago
E. Tucker
6921 silver badge15 bronze badges
asked 8 hours ago
Sriram SankaranarayananSriram Sankaranarayanan
694 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
edited 5 hours ago
E. Tucker
6921 silver badge15 bronze badges
asked 8 hours ago
Sriram SankaranarayananSriram Sankaranarayanan
694 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$
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
solver graphs heuristics
edited 5 hours ago
E. Tucker
6921 silver badge15 bronze badges
asked 8 hours ago
Sriram SankaranarayananSriram Sankaranarayanan
694 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
6921 silver badge15 bronze badges
asked 8 hours ago
Sriram SankaranarayananSriram Sankaranarayanan
694 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
6921 silver badge15 bronze badges
edited 5 hours ago
E. Tucker
6921 silver badge15 bronze badges
edited 5 hours ago
E. Tucker
6921 silver badge15 bronze badges
6921 silver badge15 bronze badges
asked 8 hours ago
Sriram SankaranarayananSriram Sankaranarayanan
694 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
694 bronze badges
asked 8 hours ago
Sriram SankaranarayananSriram Sankaranarayanan
694 bronze badges
694 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.
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.
$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$
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
$begingroup$
Are you asking specifically about stable set/vertex cover/coloring, or are those just illustrative examples?
$endgroup$
– LarrySnyder610
8 hours ago
$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
$begingroup$
They are illustrative examples.
$endgroup$
– Sriram Sankaranarayanan
8 hours ago
add a comment |
3 Answers
3
active
oldest
votes
$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.
answered 7 hours ago
prubinprubin
1,1713 silver badges11 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$
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.
answered 5 hours ago
Rob PrattRob Pratt
5077 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$
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.
answered 8 hours ago
LarrySnyder610LarrySnyder610
3,1436 silver badges47 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.
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
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
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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.
answered 7 hours ago
prubinprubin
1,1713 silver badges11 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.
answered 7 hours ago
prubinprubin
1,1713 silver badges11 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.
answered 7 hours ago
prubinprubin
1,1713 silver badges11 bronze badges
$endgroup$
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.
answered 7 hours ago
prubinprubin
1,1713 silver badges11 bronze badges
answered 7 hours ago
prubinprubin
1,1713 silver badges11 bronze badges
answered 7 hours ago
prubinprubin
1,1713 silver badges11 bronze badges
answered 7 hours ago
prubinprubin
1,1713 silver badges11 bronze badges
1,1713 silver badges11 bronze badges
$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$
SAS automatically detects the network structure and issues a log message that suggests using network simplex.
$endgroup$
– Rob Pratt
6 hours ago
$begingroup$
SAS automatically detects the network structure and issues a log message that suggests using network simplex.
$endgroup$
– Rob Pratt
6 hours ago
$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$
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.
answered 5 hours ago
Rob PrattRob Pratt
5077 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.
answered 5 hours ago
Rob PrattRob Pratt
5077 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.
answered 5 hours ago
Rob PrattRob Pratt
5077 bronze badges
$endgroup$
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.
answered 5 hours ago
Rob PrattRob Pratt
5077 bronze badges
answered 5 hours ago
Rob PrattRob Pratt
5077 bronze badges
answered 5 hours ago
Rob PrattRob Pratt
5077 bronze badges
answered 5 hours ago
Rob PrattRob Pratt
5077 bronze badges
5077 bronze badges
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 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
1
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
$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
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$
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
$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$
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.
answered 8 hours ago
LarrySnyder610LarrySnyder610
3,1436 silver badges47 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.
answered 8 hours ago
LarrySnyder610LarrySnyder610
3,1436 silver badges47 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.
answered 8 hours ago
LarrySnyder610LarrySnyder610
3,1436 silver badges47 bronze badges
$endgroup$
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.
answered 8 hours ago
LarrySnyder610LarrySnyder610
3,1436 silver badges47 bronze badges
answered 8 hours ago
LarrySnyder610LarrySnyder610
3,1436 silver badges47 bronze badges
answered 8 hours ago
LarrySnyder610LarrySnyder610
3,1436 silver badges47 bronze badges
answered 8 hours ago
LarrySnyder610LarrySnyder610
3,1436 silver badges47 bronze badges
3,1436 silver badges47 bronze badges
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$
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
1
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
$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 |
Sriram Sankaranarayanan is a new contributor. Be nice, and check out our Code of Conduct.
Sriram Sankaranarayanan is a new contributor. Be nice, and check out our Code of Conduct.
Sriram Sankaranarayanan is a new contributor. Be nice, and check out our Code of Conduct.
Sriram Sankaranarayanan is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Operations Research Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
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
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$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