Estimation of the size of Branch-and-Bound trees using MLBranching rules in commercial MIP solversUsing CPLEX “solution pool” to count feasible pointsWhat are the tradeoffs between “exact” and Reinforcement Learning methods for solving optimization problemsWhen to use indicator constraints versus big-M approaches in solving (mixed-)integer programsWhy is it important to choose big-M carefully and what are the consequences of doing it badly?Has the expressibility of 'non-integrality testing' as extension to MILP been studied before?“Best practices” for formulating MIPsGood resources for solving techniques (Metaheuristics, MILP, CP etc)Querying attributes of LP relaxation at MIP-optimality in GurobiAre there examples of spatially explicit MIP problems?
How to disable "Completion time:..." in SQL Server Messages window
The cat ate your input again!
How would timezones work on a planet 100 times the size of our Earth
Not going forward with internship interview process
Solution to German Tank Problem
How to write hyperlinks to local files in GeoJSON properties?
How can I categorize files in a directory based on their content?
Are employers legally allowed to pay employees in goods and services equal to or greater than the minimum wage?
How do some PhD students get 10+ papers? Is that what I need for landing good faculty position?
Can sampling rate be a floating point number?
How can I decide if my homebrew item should require attunement?
If clocks themselves are based on light signals, wouldn't we expect the measured speed of light to always be the same constant?
Breadcrumb history decision
Is it legal for a company to enter an agreement not to hire employees from another company?
Is it feasible to get a hash collision for CRC32, MD-5 and SHA-1 on one file?
Is God unknowable?
What does the phrase "pull off sick wheelies and flips" mean here?
How can this older-style irrigation tee be replaced?
Why does the standard fingering / strumming for a D maj chord leave out the 5th string?
How to take the beginning and end parts of a list with simpler syntax?
Why are Gatwick's runways too close together?
How can Radagast come across Gandalf and Thorin's company?
What gave Harry Potter the idea of writing in Tom Riddle's diary?
Why did Gandalf use a sword against the Balrog?
Estimation of the size of Branch-and-Bound trees using ML
Branching rules in commercial MIP solversUsing CPLEX “solution pool” to count feasible pointsWhat are the tradeoffs between “exact” and Reinforcement Learning methods for solving optimization problemsWhen to use indicator constraints versus big-M approaches in solving (mixed-)integer programsWhy is it important to choose big-M carefully and what are the consequences of doing it badly?Has the expressibility of 'non-integrality testing' as extension to MILP been studied before?“Best practices” for formulating MIPsGood resources for solving techniques (Metaheuristics, MILP, CP etc)Querying attributes of LP relaxation at MIP-optimality in GurobiAre there examples of spatially explicit MIP problems?
$begingroup$
A short background:
A paper [1] published in 2006 intends to show that the time needed to solve mixed-integer programming problems by branch and bound can be roughly predicted early in the solution process. Authors mentioned that "The application of the branch-and-bound algorithm can be limited by both the computing time and the storage space required (even when storing nodes on a hard disk). The solution process may take hours or days and there is very little a priori indication of how difficult a model will be to solve. Unfortunately, there is no known method to extract this information from the problem formulation."
on the other hand, commercial solvers are like black boxes, from which extracting useful data about the number of nodes, number of branches and so on, is very hard (I tried to extract related data from Cplex callback functions in Matlab but the trial was unsuccessful). My question is:
Is there any way to use ML techniques to estimate the branch and bound tree size? Are open-source solvers provide such data that can be used to train an ML model and then test the model on benchmark problems?
Doing my homework on searching for answers before asking the question, I can mention the following papers that also aimed to tackle the problem:
Knuth's method: In [2], two new online methods for estimating the size of backtracking search tree are proposed. They mentioned that, "Knuth’s method estimates $N$, the size of a backtrack tree as $1 + b_1 + b_1.b_2 + . . .$ where $b_i$ is the branching rate observed at depth $i$ using random probing".
Mentioning the effect of choosing the right variable to branch on, the authors in [3] mentioned that "branching on a variable that does not lead to any serious simplifications on any of the (two) children can be seen as doubling the size of the tree with no improvement, thus leading to extremely large (out of control) search trees."
[1] Cornuéjols, Gérard, Miroslav Karamanov, and Yanjun Li. "Early estimates of the size of branch-and-bound trees." INFORMS Journal on Computing 18.1 (2006): 86-96.
[2] Kilby, Philip, et al. "Estimating search tree size." Proc. of the 21st National Conf. of Artificial Intelligence, AAAI, Menlo Park. 2006.
[3] Lodi, Andrea, and Giulia Zarpellon. "On learning and branching: a survey." Top 25.2 (2017): 207-236.
mixed-integer-programming machine-learning branch-and-bound
asked Aug 1 at 2:33
Oguz ToragayOguz Toragay
2,0602 silver badges24 bronze badges
$endgroup$
add a comment |
$begingroup$
A short background:
A paper [1] published in 2006 intends to show that the time needed to solve mixed-integer programming problems by branch and bound can be roughly predicted early in the solution process. Authors mentioned that "The application of the branch-and-bound algorithm can be limited by both the computing time and the storage space required (even when storing nodes on a hard disk). The solution process may take hours or days and there is very little a priori indication of how difficult a model will be to solve. Unfortunately, there is no known method to extract this information from the problem formulation."
on the other hand, commercial solvers are like black boxes, from which extracting useful data about the number of nodes, number of branches and so on, is very hard (I tried to extract related data from Cplex callback functions in Matlab but the trial was unsuccessful). My question is:
Is there any way to use ML techniques to estimate the branch and bound tree size? Are open-source solvers provide such data that can be used to train an ML model and then test the model on benchmark problems?
Doing my homework on searching for answers before asking the question, I can mention the following papers that also aimed to tackle the problem:
Knuth's method: In [2], two new online methods for estimating the size of backtracking search tree are proposed. They mentioned that, "Knuth’s method estimates $N$, the size of a backtrack tree as $1 + b_1 + b_1.b_2 + . . .$ where $b_i$ is the branching rate observed at depth $i$ using random probing".
Mentioning the effect of choosing the right variable to branch on, the authors in [3] mentioned that "branching on a variable that does not lead to any serious simplifications on any of the (two) children can be seen as doubling the size of the tree with no improvement, thus leading to extremely large (out of control) search trees."
[1] Cornuéjols, Gérard, Miroslav Karamanov, and Yanjun Li. "Early estimates of the size of branch-and-bound trees." INFORMS Journal on Computing 18.1 (2006): 86-96.
[2] Kilby, Philip, et al. "Estimating search tree size." Proc. of the 21st National Conf. of Artificial Intelligence, AAAI, Menlo Park. 2006.
[3] Lodi, Andrea, and Giulia Zarpellon. "On learning and branching: a survey." Top 25.2 (2017): 207-236.
mixed-integer-programming machine-learning branch-and-bound
asked Aug 1 at 2:33
Oguz ToragayOguz Toragay
2,0602 silver badges24 bronze badges
$endgroup$
add a comment |
$begingroup$
A short background:
A paper [1] published in 2006 intends to show that the time needed to solve mixed-integer programming problems by branch and bound can be roughly predicted early in the solution process. Authors mentioned that "The application of the branch-and-bound algorithm can be limited by both the computing time and the storage space required (even when storing nodes on a hard disk). The solution process may take hours or days and there is very little a priori indication of how difficult a model will be to solve. Unfortunately, there is no known method to extract this information from the problem formulation."
on the other hand, commercial solvers are like black boxes, from which extracting useful data about the number of nodes, number of branches and so on, is very hard (I tried to extract related data from Cplex callback functions in Matlab but the trial was unsuccessful). My question is:
Is there any way to use ML techniques to estimate the branch and bound tree size? Are open-source solvers provide such data that can be used to train an ML model and then test the model on benchmark problems?
Doing my homework on searching for answers before asking the question, I can mention the following papers that also aimed to tackle the problem:
Knuth's method: In [2], two new online methods for estimating the size of backtracking search tree are proposed. They mentioned that, "Knuth’s method estimates $N$, the size of a backtrack tree as $1 + b_1 + b_1.b_2 + . . .$ where $b_i$ is the branching rate observed at depth $i$ using random probing".
Mentioning the effect of choosing the right variable to branch on, the authors in [3] mentioned that "branching on a variable that does not lead to any serious simplifications on any of the (two) children can be seen as doubling the size of the tree with no improvement, thus leading to extremely large (out of control) search trees."
[1] Cornuéjols, Gérard, Miroslav Karamanov, and Yanjun Li. "Early estimates of the size of branch-and-bound trees." INFORMS Journal on Computing 18.1 (2006): 86-96.
[2] Kilby, Philip, et al. "Estimating search tree size." Proc. of the 21st National Conf. of Artificial Intelligence, AAAI, Menlo Park. 2006.
[3] Lodi, Andrea, and Giulia Zarpellon. "On learning and branching: a survey." Top 25.2 (2017): 207-236.
mixed-integer-programming machine-learning branch-and-bound
asked Aug 1 at 2:33
Oguz ToragayOguz Toragay
2,0602 silver badges24 bronze badges
$endgroup$
A short background:
A paper [1] published in 2006 intends to show that the time needed to solve mixed-integer programming problems by branch and bound can be roughly predicted early in the solution process. Authors mentioned that "The application of the branch-and-bound algorithm can be limited by both the computing time and the storage space required (even when storing nodes on a hard disk). The solution process may take hours or days and there is very little a priori indication of how difficult a model will be to solve. Unfortunately, there is no known method to extract this information from the problem formulation."
on the other hand, commercial solvers are like black boxes, from which extracting useful data about the number of nodes, number of branches and so on, is very hard (I tried to extract related data from Cplex callback functions in Matlab but the trial was unsuccessful). My question is:
Is there any way to use ML techniques to estimate the branch and bound tree size? Are open-source solvers provide such data that can be used to train an ML model and then test the model on benchmark problems?
Doing my homework on searching for answers before asking the question, I can mention the following papers that also aimed to tackle the problem:
Knuth's method: In [2], two new online methods for estimating the size of backtracking search tree are proposed. They mentioned that, "Knuth’s method estimates $N$, the size of a backtrack tree as $1 + b_1 + b_1.b_2 + . . .$ where $b_i$ is the branching rate observed at depth $i$ using random probing".
Mentioning the effect of choosing the right variable to branch on, the authors in [3] mentioned that "branching on a variable that does not lead to any serious simplifications on any of the (two) children can be seen as doubling the size of the tree with no improvement, thus leading to extremely large (out of control) search trees."
[1] Cornuéjols, Gérard, Miroslav Karamanov, and Yanjun Li. "Early estimates of the size of branch-and-bound trees." INFORMS Journal on Computing 18.1 (2006): 86-96.
[2] Kilby, Philip, et al. "Estimating search tree size." Proc. of the 21st National Conf. of Artificial Intelligence, AAAI, Menlo Park. 2006.
[3] Lodi, Andrea, and Giulia Zarpellon. "On learning and branching: a survey." Top 25.2 (2017): 207-236.
mixed-integer-programming machine-learning branch-and-bound
mixed-integer-programming machine-learning branch-and-bound
asked Aug 1 at 2:33
Oguz ToragayOguz Toragay
2,0602 silver badges24 bronze badges
asked Aug 1 at 2:33
Oguz ToragayOguz Toragay
2,0602 silver badges24 bronze badges
asked Aug 1 at 2:33
Oguz ToragayOguz Toragay
2,0602 silver badges24 bronze badges
asked Aug 1 at 2:33
Oguz ToragayOguz Toragay
2,0602 silver badges24 bronze badges
asked Aug 1 at 2:33
Oguz ToragayOguz Toragay
2,0602 silver badges24 bronze badges
2,0602 silver badges24 bronze badges
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Great question. You might be interested in this paper here:
Learning MILP Resolution Outcomes Before Reaching Time-Limit by Martina Fischetti, Andrea Lodi, and Giulia Zarpellon.
They don't exactly answer your question but you may see why the question is hard to answer and what partial progress can be made.
A priori estimating the tree size is estimating whether a model is hard to solve or not. From the static features of the instance, without any runtime knowledge (and even with it!), I personally deem this task virtually undoable. But this is just gut feeling.
edit concerning the data: B&B solvers do not provide such data, but of course you can collect this from B&B runs a posteriori.
answered Aug 1 at 5:55
Marco LübbeckeMarco Lübbecke
2,2335 silver badges30 bronze badges
$endgroup$
1
$begingroup$
Thanks for the suggestion @Marco Lübbecke, I will check the paper but I believe any progress in estimating the tree size, as you said, will reveal a great detail on how hard the problem is and how to allocate memory and time on solving that.
$endgroup$
– Oguz Toragay
Aug 1 at 15:02
2
$begingroup$
I therefore thought it would be great to "only" be able to classify, maybe into "short, medium, long", but even this seems to be not reliable. With runtime information, however, there might be more hope. Fascinating area at any rate.
$endgroup$
– Marco Lübbecke
Aug 2 at 10:57
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
);
);
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%2f1122%2festimation-of-the-size-of-branch-and-bound-trees-using-ml%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Great question. You might be interested in this paper here:
Learning MILP Resolution Outcomes Before Reaching Time-Limit by Martina Fischetti, Andrea Lodi, and Giulia Zarpellon.
They don't exactly answer your question but you may see why the question is hard to answer and what partial progress can be made.
A priori estimating the tree size is estimating whether a model is hard to solve or not. From the static features of the instance, without any runtime knowledge (and even with it!), I personally deem this task virtually undoable. But this is just gut feeling.
edit concerning the data: B&B solvers do not provide such data, but of course you can collect this from B&B runs a posteriori.
answered Aug 1 at 5:55
Marco LübbeckeMarco Lübbecke
2,2335 silver badges30 bronze badges
$endgroup$
1
$begingroup$
Thanks for the suggestion @Marco Lübbecke, I will check the paper but I believe any progress in estimating the tree size, as you said, will reveal a great detail on how hard the problem is and how to allocate memory and time on solving that.
$endgroup$
– Oguz Toragay
Aug 1 at 15:02
2
$begingroup$
I therefore thought it would be great to "only" be able to classify, maybe into "short, medium, long", but even this seems to be not reliable. With runtime information, however, there might be more hope. Fascinating area at any rate.
$endgroup$
– Marco Lübbecke
Aug 2 at 10:57
add a comment |
$begingroup$
Great question. You might be interested in this paper here:
Learning MILP Resolution Outcomes Before Reaching Time-Limit by Martina Fischetti, Andrea Lodi, and Giulia Zarpellon.
They don't exactly answer your question but you may see why the question is hard to answer and what partial progress can be made.
A priori estimating the tree size is estimating whether a model is hard to solve or not. From the static features of the instance, without any runtime knowledge (and even with it!), I personally deem this task virtually undoable. But this is just gut feeling.
edit concerning the data: B&B solvers do not provide such data, but of course you can collect this from B&B runs a posteriori.
answered Aug 1 at 5:55
Marco LübbeckeMarco Lübbecke
2,2335 silver badges30 bronze badges
$endgroup$
1
$begingroup$
Thanks for the suggestion @Marco Lübbecke, I will check the paper but I believe any progress in estimating the tree size, as you said, will reveal a great detail on how hard the problem is and how to allocate memory and time on solving that.
$endgroup$
– Oguz Toragay
Aug 1 at 15:02
2
$begingroup$
I therefore thought it would be great to "only" be able to classify, maybe into "short, medium, long", but even this seems to be not reliable. With runtime information, however, there might be more hope. Fascinating area at any rate.
$endgroup$
– Marco Lübbecke
Aug 2 at 10:57
add a comment |
$begingroup$
Great question. You might be interested in this paper here:
Learning MILP Resolution Outcomes Before Reaching Time-Limit by Martina Fischetti, Andrea Lodi, and Giulia Zarpellon.
They don't exactly answer your question but you may see why the question is hard to answer and what partial progress can be made.
A priori estimating the tree size is estimating whether a model is hard to solve or not. From the static features of the instance, without any runtime knowledge (and even with it!), I personally deem this task virtually undoable. But this is just gut feeling.
edit concerning the data: B&B solvers do not provide such data, but of course you can collect this from B&B runs a posteriori.
answered Aug 1 at 5:55
Marco LübbeckeMarco Lübbecke
2,2335 silver badges30 bronze badges
$endgroup$
Great question. You might be interested in this paper here:
Learning MILP Resolution Outcomes Before Reaching Time-Limit by Martina Fischetti, Andrea Lodi, and Giulia Zarpellon.
They don't exactly answer your question but you may see why the question is hard to answer and what partial progress can be made.
A priori estimating the tree size is estimating whether a model is hard to solve or not. From the static features of the instance, without any runtime knowledge (and even with it!), I personally deem this task virtually undoable. But this is just gut feeling.
edit concerning the data: B&B solvers do not provide such data, but of course you can collect this from B&B runs a posteriori.
answered Aug 1 at 5:55
Marco LübbeckeMarco Lübbecke
2,2335 silver badges30 bronze badges
edited Aug 1 at 6:01
answered Aug 1 at 5:55
Marco LübbeckeMarco Lübbecke
2,2335 silver badges30 bronze badges
answered Aug 1 at 5:55
Marco LübbeckeMarco Lübbecke
2,2335 silver badges30 bronze badges
answered Aug 1 at 5:55
Marco LübbeckeMarco Lübbecke
2,2335 silver badges30 bronze badges
2,2335 silver badges30 bronze badges
1
$begingroup$
Thanks for the suggestion @Marco Lübbecke, I will check the paper but I believe any progress in estimating the tree size, as you said, will reveal a great detail on how hard the problem is and how to allocate memory and time on solving that.
$endgroup$
– Oguz Toragay
Aug 1 at 15:02
2
$begingroup$
I therefore thought it would be great to "only" be able to classify, maybe into "short, medium, long", but even this seems to be not reliable. With runtime information, however, there might be more hope. Fascinating area at any rate.
$endgroup$
– Marco Lübbecke
Aug 2 at 10:57
add a comment |
1
$begingroup$
Thanks for the suggestion @Marco Lübbecke, I will check the paper but I believe any progress in estimating the tree size, as you said, will reveal a great detail on how hard the problem is and how to allocate memory and time on solving that.
$endgroup$
– Oguz Toragay
Aug 1 at 15:02
2
$begingroup$
I therefore thought it would be great to "only" be able to classify, maybe into "short, medium, long", but even this seems to be not reliable. With runtime information, however, there might be more hope. Fascinating area at any rate.
$endgroup$
– Marco Lübbecke
Aug 2 at 10:57
1
1
$begingroup$
Thanks for the suggestion @Marco Lübbecke, I will check the paper but I believe any progress in estimating the tree size, as you said, will reveal a great detail on how hard the problem is and how to allocate memory and time on solving that.
$endgroup$
– Oguz Toragay
Aug 1 at 15:02
$begingroup$
Thanks for the suggestion @Marco Lübbecke, I will check the paper but I believe any progress in estimating the tree size, as you said, will reveal a great detail on how hard the problem is and how to allocate memory and time on solving that.
$endgroup$
– Oguz Toragay
Aug 1 at 15:02
2
2
$begingroup$
I therefore thought it would be great to "only" be able to classify, maybe into "short, medium, long", but even this seems to be not reliable. With runtime information, however, there might be more hope. Fascinating area at any rate.
$endgroup$
– Marco Lübbecke
Aug 2 at 10:57
$begingroup$
I therefore thought it would be great to "only" be able to classify, maybe into "short, medium, long", but even this seems to be not reliable. With runtime information, however, there might be more hope. Fascinating area at any rate.
$endgroup$
– Marco Lübbecke
Aug 2 at 10:57
add a comment |
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%2f1122%2festimation-of-the-size-of-branch-and-bound-trees-using-ml%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
