Complexity of verifying optimality in (mixed) integer programmingThe difference between max-min and min-maxSingle reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?Using CPLEX “solution pool” to count feasible pointsWhen to use indicator constraints versus big-M approaches in solving (mixed-)integer programsConditional Controls in MIP Modelsmaximum eigenvalue across subsamplesHeuristics for mixed integer linear and nonlinear programsDeciding the presence of mixed-integer points in the relative interior of a polyhedronHow to write a mixed-integer linear programming formulation in Python using Gurobi?How to formulate this scheduling problem efficiently?
Blank spaces in a font
Why does Canada require bilingualism in a lot of federal government posts?
How well would the Moon protect the Earth from an Asteroid?
How to store my pliers and wire cutters on my desk?
What are the cons of stateless password generators?
Story about separate individuals coming together to make some supernatural universe power
Exploiting the delay when a festival ticket is scanned
Rampant sharing of authorship among colleagues in the name of "collaboration". Is not taking part in it a death knell for a future in academia?
Does dual boot harm a laptop battery or reduce its life?
Is it safe if the neutral lead is exposed and disconnected?
Would people understand me speaking German all over Europe?
Is it unprofessional to mention your cover letter and resume are best viewed in Chrome?
To find islands of 1 and 0 in matrix
Wrapping IMemoryCache with SemaphoreSlim
Complaints from (junior) developers against solution architects: how can we show the benefits of our work and improve relationships?
Newton's cradles
Why does the Eurostar not show youth pricing?
Is it okay for me to decline a project on ethical grounds?
Why does aggregate initialization not work anymore since C++20 if a constructor is explicitly defaulted or deleted?
Alternatives to minimizing loss in regression
Was Donald Trump at ground zero helping out on 9-11?
Self-deportation of American Citizens from US
Can Lightning Lure be used to knock out a creature like a magical Taser?
Why did Windows 95 crash the whole system but newer Windows only crashed programs?
Complexity of verifying optimality in (mixed) integer programming
The difference between max-min and min-maxSingle reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?Using CPLEX “solution pool” to count feasible pointsWhen to use indicator constraints versus big-M approaches in solving (mixed-)integer programsConditional Controls in MIP Modelsmaximum eigenvalue across subsamplesHeuristics for mixed integer linear and nonlinear programsDeciding the presence of mixed-integer points in the relative interior of a polyhedronHow to write a mixed-integer linear programming formulation in Python using Gurobi?How to formulate this scheduling problem efficiently?
$begingroup$
I looked around for a while, but I couldn't find a precise answer to the following question.
If I'm given a candidate solution for a (mixed) integer (convex) program, what's the complexity of deciding whether this solution (a point in the decision space) is optimal or not? I imagine that this decision problem is not NP (i.e., optimality of a MIP feasible solution can't be certified in polynomial time), right? Do you know any text or a reference where this problem is treated in detail?
Thank you very much!
mixed-integer-programming computational-complexity
asked 8 hours ago
Tobia MarcucciTobia Marcucci
1434 bronze badges
New contributor
Tobia Marcucci 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$
I looked around for a while, but I couldn't find a precise answer to the following question.
If I'm given a candidate solution for a (mixed) integer (convex) program, what's the complexity of deciding whether this solution (a point in the decision space) is optimal or not? I imagine that this decision problem is not NP (i.e., optimality of a MIP feasible solution can't be certified in polynomial time), right? Do you know any text or a reference where this problem is treated in detail?
Thank you very much!
mixed-integer-programming computational-complexity
asked 8 hours ago
Tobia MarcucciTobia Marcucci
1434 bronze badges
New contributor
Tobia Marcucci is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
3
$begingroup$
not sure if you don't give the answer yourself: MIP optimality can't be certified in polytime; otherwise you could decide a lot of (=all) NP-complete decision problems in polytime.
$endgroup$
– Marco Lübbecke
8 hours ago
add a comment |
$begingroup$
I looked around for a while, but I couldn't find a precise answer to the following question.
If I'm given a candidate solution for a (mixed) integer (convex) program, what's the complexity of deciding whether this solution (a point in the decision space) is optimal or not? I imagine that this decision problem is not NP (i.e., optimality of a MIP feasible solution can't be certified in polynomial time), right? Do you know any text or a reference where this problem is treated in detail?
Thank you very much!
mixed-integer-programming computational-complexity
asked 8 hours ago
Tobia MarcucciTobia Marcucci
1434 bronze badges
New contributor
Tobia Marcucci is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I looked around for a while, but I couldn't find a precise answer to the following question.
If I'm given a candidate solution for a (mixed) integer (convex) program, what's the complexity of deciding whether this solution (a point in the decision space) is optimal or not? I imagine that this decision problem is not NP (i.e., optimality of a MIP feasible solution can't be certified in polynomial time), right? Do you know any text or a reference where this problem is treated in detail?
Thank you very much!
mixed-integer-programming computational-complexity
mixed-integer-programming computational-complexity
asked 8 hours ago
Tobia MarcucciTobia Marcucci
1434 bronze badges
New contributor
Tobia Marcucci 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
Tobia MarcucciTobia Marcucci
1434 bronze badges
New contributor
Tobia Marcucci 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
Tobia MarcucciTobia Marcucci
1434 bronze badges
New contributor
Tobia Marcucci 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
Tobia MarcucciTobia Marcucci
1434 bronze badges
asked 8 hours ago
Tobia MarcucciTobia Marcucci
1434 bronze badges
1434 bronze badges
New contributor
Tobia Marcucci is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Tobia Marcucci is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
3
$begingroup$
not sure if you don't give the answer yourself: MIP optimality can't be certified in polytime; otherwise you could decide a lot of (=all) NP-complete decision problems in polytime.
$endgroup$
– Marco Lübbecke
8 hours ago
add a comment |
3
$begingroup$
not sure if you don't give the answer yourself: MIP optimality can't be certified in polytime; otherwise you could decide a lot of (=all) NP-complete decision problems in polytime.
$endgroup$
– Marco Lübbecke
8 hours ago
3
3
$begingroup$
not sure if you don't give the answer yourself: MIP optimality can't be certified in polytime; otherwise you could decide a lot of (=all) NP-complete decision problems in polytime.
$endgroup$
– Marco Lübbecke
8 hours ago
$begingroup$
not sure if you don't give the answer yourself: MIP optimality can't be certified in polytime; otherwise you could decide a lot of (=all) NP-complete decision problems in polytime.
$endgroup$
– Marco Lübbecke
8 hours ago
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Deciding if a given solution to a mixed integer linear program is optimal is coNP-complete.
When the answer is “no, it is not optimal” there is an efficiently verifiable witness—a better solution.
Minor caveat: This answer assumes that there is a better solution that is efficiently verifiable (which necessitates that it can be represented with a polynomial number of bits). This is true for mixed integer linear programs, but might not be true for a more generic mixed integer convex program. Here is a recent paper on the issue of polynomial-size bit encodings for mixed integer quadratic programs.
answered 8 hours ago
Austin BuchananAustin Buchanan
3466 bronze badges
$endgroup$
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
);
);
Tobia Marcucci 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%2f1095%2fcomplexity-of-verifying-optimality-in-mixed-integer-programming%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$
Deciding if a given solution to a mixed integer linear program is optimal is coNP-complete.
When the answer is “no, it is not optimal” there is an efficiently verifiable witness—a better solution.
Minor caveat: This answer assumes that there is a better solution that is efficiently verifiable (which necessitates that it can be represented with a polynomial number of bits). This is true for mixed integer linear programs, but might not be true for a more generic mixed integer convex program. Here is a recent paper on the issue of polynomial-size bit encodings for mixed integer quadratic programs.
answered 8 hours ago
Austin BuchananAustin Buchanan
3466 bronze badges
$endgroup$
add a comment |
$begingroup$
Deciding if a given solution to a mixed integer linear program is optimal is coNP-complete.
When the answer is “no, it is not optimal” there is an efficiently verifiable witness—a better solution.
Minor caveat: This answer assumes that there is a better solution that is efficiently verifiable (which necessitates that it can be represented with a polynomial number of bits). This is true for mixed integer linear programs, but might not be true for a more generic mixed integer convex program. Here is a recent paper on the issue of polynomial-size bit encodings for mixed integer quadratic programs.
answered 8 hours ago
Austin BuchananAustin Buchanan
3466 bronze badges
$endgroup$
add a comment |
$begingroup$
Deciding if a given solution to a mixed integer linear program is optimal is coNP-complete.
When the answer is “no, it is not optimal” there is an efficiently verifiable witness—a better solution.
Minor caveat: This answer assumes that there is a better solution that is efficiently verifiable (which necessitates that it can be represented with a polynomial number of bits). This is true for mixed integer linear programs, but might not be true for a more generic mixed integer convex program. Here is a recent paper on the issue of polynomial-size bit encodings for mixed integer quadratic programs.
answered 8 hours ago
Austin BuchananAustin Buchanan
3466 bronze badges
$endgroup$
Deciding if a given solution to a mixed integer linear program is optimal is coNP-complete.
When the answer is “no, it is not optimal” there is an efficiently verifiable witness—a better solution.
Minor caveat: This answer assumes that there is a better solution that is efficiently verifiable (which necessitates that it can be represented with a polynomial number of bits). This is true for mixed integer linear programs, but might not be true for a more generic mixed integer convex program. Here is a recent paper on the issue of polynomial-size bit encodings for mixed integer quadratic programs.
answered 8 hours ago
Austin BuchananAustin Buchanan
3466 bronze badges
edited 6 hours ago
answered 8 hours ago
Austin BuchananAustin Buchanan
3466 bronze badges
answered 8 hours ago
Austin BuchananAustin Buchanan
3466 bronze badges
answered 8 hours ago
Austin BuchananAustin Buchanan
3466 bronze badges
3466 bronze badges
add a comment |
add a comment |
Tobia Marcucci is a new contributor. Be nice, and check out our Code of Conduct.
Tobia Marcucci is a new contributor. Be nice, and check out our Code of Conduct.
Tobia Marcucci is a new contributor. Be nice, and check out our Code of Conduct.
Tobia Marcucci 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%2f1095%2fcomplexity-of-verifying-optimality-in-mixed-integer-programming%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
3
$begingroup$
not sure if you don't give the answer yourself: MIP optimality can't be certified in polytime; otherwise you could decide a lot of (=all) NP-complete decision problems in polytime.
$endgroup$
– Marco Lübbecke
8 hours ago