State-of-the-art algorithms for solving linear programsAlgorithms vs LP or MIPRecommended books/materials for...
Prove your innocence
Why is 1. d4 Nf6 2. c4 e6 3. Bg5 almost never played?
Sum ergo cogito?
If someone uses the Command spell and says "drop", what happens?
Why is the UK so keen to remove the "backstop" when their leadership seems to think that no border will be needed in Northern Ireland?
moon structure ownership
Architectural feasibility of a tiered circular stone keep
Why doesn't 'd /= d' throw a division by zero exception?
Is gzip atomic?
Are the players on the same team as the DM?
Did a flight controller ever answer Flight with a no-go?
Numbers Decrease while Letters Increase
How do I make my image comply with the requirements of this photography competition?
Network helper class with retry logic on failure
Can I get temporary health insurance while moving to the US?
How much does Commander Data weigh?
How to know which loss function is suitable for image classification?
If an earthquake can destroy buildings why it cant kill us according to physics?
How do you interpolate outside the range of data?
Why is it not possible to create electricity by forcibly putting electrons into the system and closing the loop?
Does an atom recoil when photon radiate?
How do I get toddlers to stop asking for food every hour?
Why does Windows store Wi-Fi passwords in a reversable format?
Where can/should I, as a high schooler, publish a paper regarding the derivation of a formula?
State-of-the-art algorithms for solving linear programs
Algorithms vs LP or MIPRecommended books/materials for practical applications of Operations Research in industryWhen to use indicator constraints versus big-M approaches in solving (mixed-)integer programsCombinatorial Optimization: Metaheuristics, CP, IP — “versus” or “and”?How to reduce recursion when using Gomory cutting planes to solve an integer program?Guidelines for Linear Optimization approaches?Tightness of an LP relaxation without using objective functionApplication of complex numbers in Linear Programming?Polynomially solvable problems with exponential extension complexity
$begingroup$
Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances). As the authors write:
Arguably, the most important consequences of our reductions are constraints on algorithms to solve the LP relaxations. Leaving runtime aside, they show that such algorithms cannot be arbitrarily simple since they must be able to solve any linear program.
Linear programming is an important tool used to solve integer linear programs (via the LP-based branch and bound approach). There has been a huge progress towards solving such integer programs. However, there does not seem to be much progress in solving the general linear programming problem. As far as I know, the classical simplex algorithm or its dual variant is still used in modern IP solvers (even as the default LP algorithm).
Are there are any new algorithms that could potentially beat the simplex algorithm in practice (at least on average)? If not, then I am wondering why?
The result of Průša and Werner implies that no matter how good the underlying formulation is (or no matter how good the valid inequalities can be), we still need to solve the resulting linear program (i.e., ANY linear program) efficiently to be able to solve large problems.
mixed-integer-programming linear-programming combinatorial-optimization computational-complexity valid-inequalities
edited yesterday
Rodrigo de Azevedo
1296 bronze badges
asked yesterday
OptOpt
2618 bronze badges
New contributor
Opt 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$
Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances). As the authors write:
Arguably, the most important consequences of our reductions are constraints on algorithms to solve the LP relaxations. Leaving runtime aside, they show that such algorithms cannot be arbitrarily simple since they must be able to solve any linear program.
Linear programming is an important tool used to solve integer linear programs (via the LP-based branch and bound approach). There has been a huge progress towards solving such integer programs. However, there does not seem to be much progress in solving the general linear programming problem. As far as I know, the classical simplex algorithm or its dual variant is still used in modern IP solvers (even as the default LP algorithm).
Are there are any new algorithms that could potentially beat the simplex algorithm in practice (at least on average)? If not, then I am wondering why?
The result of Průša and Werner implies that no matter how good the underlying formulation is (or no matter how good the valid inequalities can be), we still need to solve the resulting linear program (i.e., ANY linear program) efficiently to be able to solve large problems.
mixed-integer-programming linear-programming combinatorial-optimization computational-complexity valid-inequalities
edited yesterday
Rodrigo de Azevedo
1296 bronze badges
asked yesterday
OptOpt
2618 bronze badges
New contributor
Opt 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$
Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances). As the authors write:
Arguably, the most important consequences of our reductions are constraints on algorithms to solve the LP relaxations. Leaving runtime aside, they show that such algorithms cannot be arbitrarily simple since they must be able to solve any linear program.
Linear programming is an important tool used to solve integer linear programs (via the LP-based branch and bound approach). There has been a huge progress towards solving such integer programs. However, there does not seem to be much progress in solving the general linear programming problem. As far as I know, the classical simplex algorithm or its dual variant is still used in modern IP solvers (even as the default LP algorithm).
Are there are any new algorithms that could potentially beat the simplex algorithm in practice (at least on average)? If not, then I am wondering why?
The result of Průša and Werner implies that no matter how good the underlying formulation is (or no matter how good the valid inequalities can be), we still need to solve the resulting linear program (i.e., ANY linear program) efficiently to be able to solve large problems.
mixed-integer-programming linear-programming combinatorial-optimization computational-complexity valid-inequalities
edited yesterday
Rodrigo de Azevedo
1296 bronze badges
asked yesterday
OptOpt
2618 bronze badges
New contributor
Opt is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances). As the authors write:
Arguably, the most important consequences of our reductions are constraints on algorithms to solve the LP relaxations. Leaving runtime aside, they show that such algorithms cannot be arbitrarily simple since they must be able to solve any linear program.
Linear programming is an important tool used to solve integer linear programs (via the LP-based branch and bound approach). There has been a huge progress towards solving such integer programs. However, there does not seem to be much progress in solving the general linear programming problem. As far as I know, the classical simplex algorithm or its dual variant is still used in modern IP solvers (even as the default LP algorithm).
Are there are any new algorithms that could potentially beat the simplex algorithm in practice (at least on average)? If not, then I am wondering why?
The result of Průša and Werner implies that no matter how good the underlying formulation is (or no matter how good the valid inequalities can be), we still need to solve the resulting linear program (i.e., ANY linear program) efficiently to be able to solve large problems.
mixed-integer-programming linear-programming combinatorial-optimization computational-complexity valid-inequalities
mixed-integer-programming linear-programming combinatorial-optimization computational-complexity valid-inequalities
edited yesterday
Rodrigo de Azevedo
1296 bronze badges
asked yesterday
OptOpt
2618 bronze badges
New contributor
Opt is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Rodrigo de Azevedo
1296 bronze badges
asked yesterday
OptOpt
2618 bronze badges
New contributor
Opt is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited yesterday
Rodrigo de Azevedo
1296 bronze badges
edited yesterday
Rodrigo de Azevedo
1296 bronze badges
edited yesterday
Rodrigo de Azevedo
1296 bronze badges
1296 bronze badges
asked yesterday
OptOpt
2618 bronze badges
New contributor
Opt is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked yesterday
OptOpt
2618 bronze badges
asked yesterday
OptOpt
2618 bronze badges
2618 bronze badges
New contributor
Opt is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Opt is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The simple answer is that for large scale problems (1m+ rows and columns) we would use interior point instead of dual simplex.
The main challenge is not really the solving algorithm, since interior point has polynomial complexity for LP, it's being able to reliably find a feasible point to begin interior point. Finding this point with a guarantee is actually a non-polynomial complexity task. Because of this, tackling the general LP case (up to arbitrary numbers of constraints and variables) is not yet a solved problem. The other reasons are numerical stability and factorising the coefficient matrix which are also prone to large scale difficulties.
answered yesterday
nikazanikaza
3994 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
2
$begingroup$
Not sure whether your comment about finding an interior point is non-polynomial ist a correct. Do you have some source for that claim.
$endgroup$
– JakobS
yesterday
1
$begingroup$
I also doubt that claim, and I would appreciate some source. @nikaza makes a similar claim in this answer.
$endgroup$
– Kevin Dalmeijer
yesterday
$begingroup$
I'll see if I can find a reference for you but the principle is that there are two main ways to find feasible points: (I) simplex based methods to find a feasible vertex on the polytope (NP hard), and (ii) solving the Newton system during interior point, which reduces to a linear system. In the latter case, we hope to land in the interior by minimising the slack error while solving the system, but (I) this is not guaranteed to always work, and (ii) we need a point close to the solution for Newton's method to begin with. The only reliable ways of solving this are NP hard, e.g. interval Newton.
$endgroup$
– nikaza
yesterday
$begingroup$
@nikaza In Khachiyan (1980) it is proven that "determining the compatibility of a system of linear inequalities in $mathbb{R}^n$ belongs to the class of $P$ of problems". This seems to contradict that finding a feasible point is difficult.
$endgroup$
– Kevin Dalmeijer
yesterday
4
$begingroup$
@nikaza The Ellipsoid method of Khachiyan provides a feasible point (or concludes the polytope is empty) in polynomial time. But there is no guarantee the provided point is an integer point. Determining whether a feasible integer point exists in a polytope is NP-complete. Be aware that LP and ILP are very different problems! Also, be aware that if you can optimize an LP, you can also find a feasible solution, using a trick called the Two-Phase method. This involves adding artificial variables to your model that provide you with a known feasible solution.
$endgroup$
– Paul Bouman
17 hours ago
|
show 1 more 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
});
}
});
Opt 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%2f1354%2fstate-of-the-art-algorithms-for-solving-linear-programs%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$
The simple answer is that for large scale problems (1m+ rows and columns) we would use interior point instead of dual simplex.
The main challenge is not really the solving algorithm, since interior point has polynomial complexity for LP, it's being able to reliably find a feasible point to begin interior point. Finding this point with a guarantee is actually a non-polynomial complexity task. Because of this, tackling the general LP case (up to arbitrary numbers of constraints and variables) is not yet a solved problem. The other reasons are numerical stability and factorising the coefficient matrix which are also prone to large scale difficulties.
answered yesterday
nikazanikaza
3994 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
2
$begingroup$
Not sure whether your comment about finding an interior point is non-polynomial ist a correct. Do you have some source for that claim.
$endgroup$
– JakobS
yesterday
1
$begingroup$
I also doubt that claim, and I would appreciate some source. @nikaza makes a similar claim in this answer.
$endgroup$
– Kevin Dalmeijer
yesterday
$begingroup$
I'll see if I can find a reference for you but the principle is that there are two main ways to find feasible points: (I) simplex based methods to find a feasible vertex on the polytope (NP hard), and (ii) solving the Newton system during interior point, which reduces to a linear system. In the latter case, we hope to land in the interior by minimising the slack error while solving the system, but (I) this is not guaranteed to always work, and (ii) we need a point close to the solution for Newton's method to begin with. The only reliable ways of solving this are NP hard, e.g. interval Newton.
$endgroup$
– nikaza
yesterday
$begingroup$
@nikaza In Khachiyan (1980) it is proven that "determining the compatibility of a system of linear inequalities in $mathbb{R}^n$ belongs to the class of $P$ of problems". This seems to contradict that finding a feasible point is difficult.
$endgroup$
– Kevin Dalmeijer
yesterday
4
$begingroup$
@nikaza The Ellipsoid method of Khachiyan provides a feasible point (or concludes the polytope is empty) in polynomial time. But there is no guarantee the provided point is an integer point. Determining whether a feasible integer point exists in a polytope is NP-complete. Be aware that LP and ILP are very different problems! Also, be aware that if you can optimize an LP, you can also find a feasible solution, using a trick called the Two-Phase method. This involves adding artificial variables to your model that provide you with a known feasible solution.
$endgroup$
– Paul Bouman
17 hours ago
|
show 1 more comment
$begingroup$
The simple answer is that for large scale problems (1m+ rows and columns) we would use interior point instead of dual simplex.
The main challenge is not really the solving algorithm, since interior point has polynomial complexity for LP, it's being able to reliably find a feasible point to begin interior point. Finding this point with a guarantee is actually a non-polynomial complexity task. Because of this, tackling the general LP case (up to arbitrary numbers of constraints and variables) is not yet a solved problem. The other reasons are numerical stability and factorising the coefficient matrix which are also prone to large scale difficulties.
answered yesterday
nikazanikaza
3994 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
2
$begingroup$
Not sure whether your comment about finding an interior point is non-polynomial ist a correct. Do you have some source for that claim.
$endgroup$
– JakobS
yesterday
1
$begingroup$
I also doubt that claim, and I would appreciate some source. @nikaza makes a similar claim in this answer.
$endgroup$
– Kevin Dalmeijer
yesterday
$begingroup$
I'll see if I can find a reference for you but the principle is that there are two main ways to find feasible points: (I) simplex based methods to find a feasible vertex on the polytope (NP hard), and (ii) solving the Newton system during interior point, which reduces to a linear system. In the latter case, we hope to land in the interior by minimising the slack error while solving the system, but (I) this is not guaranteed to always work, and (ii) we need a point close to the solution for Newton's method to begin with. The only reliable ways of solving this are NP hard, e.g. interval Newton.
$endgroup$
– nikaza
yesterday
$begingroup$
@nikaza In Khachiyan (1980) it is proven that "determining the compatibility of a system of linear inequalities in $mathbb{R}^n$ belongs to the class of $P$ of problems". This seems to contradict that finding a feasible point is difficult.
$endgroup$
– Kevin Dalmeijer
yesterday
4
$begingroup$
@nikaza The Ellipsoid method of Khachiyan provides a feasible point (or concludes the polytope is empty) in polynomial time. But there is no guarantee the provided point is an integer point. Determining whether a feasible integer point exists in a polytope is NP-complete. Be aware that LP and ILP are very different problems! Also, be aware that if you can optimize an LP, you can also find a feasible solution, using a trick called the Two-Phase method. This involves adding artificial variables to your model that provide you with a known feasible solution.
$endgroup$
– Paul Bouman
17 hours ago
|
show 1 more comment
$begingroup$
The simple answer is that for large scale problems (1m+ rows and columns) we would use interior point instead of dual simplex.
The main challenge is not really the solving algorithm, since interior point has polynomial complexity for LP, it's being able to reliably find a feasible point to begin interior point. Finding this point with a guarantee is actually a non-polynomial complexity task. Because of this, tackling the general LP case (up to arbitrary numbers of constraints and variables) is not yet a solved problem. The other reasons are numerical stability and factorising the coefficient matrix which are also prone to large scale difficulties.
answered yesterday
nikazanikaza
3994 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
The simple answer is that for large scale problems (1m+ rows and columns) we would use interior point instead of dual simplex.
The main challenge is not really the solving algorithm, since interior point has polynomial complexity for LP, it's being able to reliably find a feasible point to begin interior point. Finding this point with a guarantee is actually a non-polynomial complexity task. Because of this, tackling the general LP case (up to arbitrary numbers of constraints and variables) is not yet a solved problem. The other reasons are numerical stability and factorising the coefficient matrix which are also prone to large scale difficulties.
answered yesterday
nikazanikaza
3994 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered yesterday
nikazanikaza
3994 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered yesterday
nikazanikaza
3994 bronze badges
answered yesterday
nikazanikaza
3994 bronze badges
3994 bronze badges
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
nikaza is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
$begingroup$
Not sure whether your comment about finding an interior point is non-polynomial ist a correct. Do you have some source for that claim.
$endgroup$
– JakobS
yesterday
1
$begingroup$
I also doubt that claim, and I would appreciate some source. @nikaza makes a similar claim in this answer.
$endgroup$
– Kevin Dalmeijer
yesterday
$begingroup$
I'll see if I can find a reference for you but the principle is that there are two main ways to find feasible points: (I) simplex based methods to find a feasible vertex on the polytope (NP hard), and (ii) solving the Newton system during interior point, which reduces to a linear system. In the latter case, we hope to land in the interior by minimising the slack error while solving the system, but (I) this is not guaranteed to always work, and (ii) we need a point close to the solution for Newton's method to begin with. The only reliable ways of solving this are NP hard, e.g. interval Newton.
$endgroup$
– nikaza
yesterday
$begingroup$
@nikaza In Khachiyan (1980) it is proven that "determining the compatibility of a system of linear inequalities in $mathbb{R}^n$ belongs to the class of $P$ of problems". This seems to contradict that finding a feasible point is difficult.
$endgroup$
– Kevin Dalmeijer
yesterday
4
$begingroup$
@nikaza The Ellipsoid method of Khachiyan provides a feasible point (or concludes the polytope is empty) in polynomial time. But there is no guarantee the provided point is an integer point. Determining whether a feasible integer point exists in a polytope is NP-complete. Be aware that LP and ILP are very different problems! Also, be aware that if you can optimize an LP, you can also find a feasible solution, using a trick called the Two-Phase method. This involves adding artificial variables to your model that provide you with a known feasible solution.
$endgroup$
– Paul Bouman
17 hours ago
|
show 1 more comment
2
$begingroup$
Not sure whether your comment about finding an interior point is non-polynomial ist a correct. Do you have some source for that claim.
$endgroup$
– JakobS
yesterday
1
$begingroup$
I also doubt that claim, and I would appreciate some source. @nikaza makes a similar claim in this answer.
$endgroup$
– Kevin Dalmeijer
yesterday
$begingroup$
I'll see if I can find a reference for you but the principle is that there are two main ways to find feasible points: (I) simplex based methods to find a feasible vertex on the polytope (NP hard), and (ii) solving the Newton system during interior point, which reduces to a linear system. In the latter case, we hope to land in the interior by minimising the slack error while solving the system, but (I) this is not guaranteed to always work, and (ii) we need a point close to the solution for Newton's method to begin with. The only reliable ways of solving this are NP hard, e.g. interval Newton.
$endgroup$
– nikaza
yesterday
$begingroup$
@nikaza In Khachiyan (1980) it is proven that "determining the compatibility of a system of linear inequalities in $mathbb{R}^n$ belongs to the class of $P$ of problems". This seems to contradict that finding a feasible point is difficult.
$endgroup$
– Kevin Dalmeijer
yesterday
4
$begingroup$
@nikaza The Ellipsoid method of Khachiyan provides a feasible point (or concludes the polytope is empty) in polynomial time. But there is no guarantee the provided point is an integer point. Determining whether a feasible integer point exists in a polytope is NP-complete. Be aware that LP and ILP are very different problems! Also, be aware that if you can optimize an LP, you can also find a feasible solution, using a trick called the Two-Phase method. This involves adding artificial variables to your model that provide you with a known feasible solution.
$endgroup$
– Paul Bouman
17 hours ago
2
2
$begingroup$
Not sure whether your comment about finding an interior point is non-polynomial ist a correct. Do you have some source for that claim.
$endgroup$
– JakobS
yesterday
$begingroup$
Not sure whether your comment about finding an interior point is non-polynomial ist a correct. Do you have some source for that claim.
$endgroup$
– JakobS
yesterday
1
1
$begingroup$
I also doubt that claim, and I would appreciate some source. @nikaza makes a similar claim in this answer.
$endgroup$
– Kevin Dalmeijer
yesterday
$begingroup$
I also doubt that claim, and I would appreciate some source. @nikaza makes a similar claim in this answer.
$endgroup$
– Kevin Dalmeijer
yesterday
$begingroup$
I'll see if I can find a reference for you but the principle is that there are two main ways to find feasible points: (I) simplex based methods to find a feasible vertex on the polytope (NP hard), and (ii) solving the Newton system during interior point, which reduces to a linear system. In the latter case, we hope to land in the interior by minimising the slack error while solving the system, but (I) this is not guaranteed to always work, and (ii) we need a point close to the solution for Newton's method to begin with. The only reliable ways of solving this are NP hard, e.g. interval Newton.
$endgroup$
– nikaza
yesterday
$begingroup$
I'll see if I can find a reference for you but the principle is that there are two main ways to find feasible points: (I) simplex based methods to find a feasible vertex on the polytope (NP hard), and (ii) solving the Newton system during interior point, which reduces to a linear system. In the latter case, we hope to land in the interior by minimising the slack error while solving the system, but (I) this is not guaranteed to always work, and (ii) we need a point close to the solution for Newton's method to begin with. The only reliable ways of solving this are NP hard, e.g. interval Newton.
$endgroup$
– nikaza
yesterday
$begingroup$
@nikaza In Khachiyan (1980) it is proven that "determining the compatibility of a system of linear inequalities in $mathbb{R}^n$ belongs to the class of $P$ of problems". This seems to contradict that finding a feasible point is difficult.
$endgroup$
– Kevin Dalmeijer
yesterday
$begingroup$
@nikaza In Khachiyan (1980) it is proven that "determining the compatibility of a system of linear inequalities in $mathbb{R}^n$ belongs to the class of $P$ of problems". This seems to contradict that finding a feasible point is difficult.
$endgroup$
– Kevin Dalmeijer
yesterday
4
4
$begingroup$
@nikaza The Ellipsoid method of Khachiyan provides a feasible point (or concludes the polytope is empty) in polynomial time. But there is no guarantee the provided point is an integer point. Determining whether a feasible integer point exists in a polytope is NP-complete. Be aware that LP and ILP are very different problems! Also, be aware that if you can optimize an LP, you can also find a feasible solution, using a trick called the Two-Phase method. This involves adding artificial variables to your model that provide you with a known feasible solution.
$endgroup$
– Paul Bouman
17 hours ago
$begingroup$
@nikaza The Ellipsoid method of Khachiyan provides a feasible point (or concludes the polytope is empty) in polynomial time. But there is no guarantee the provided point is an integer point. Determining whether a feasible integer point exists in a polytope is NP-complete. Be aware that LP and ILP are very different problems! Also, be aware that if you can optimize an LP, you can also find a feasible solution, using a trick called the Two-Phase method. This involves adding artificial variables to your model that provide you with a known feasible solution.
$endgroup$
– Paul Bouman
17 hours ago
|
show 1 more comment
Opt is a new contributor. Be nice, and check out our Code of Conduct.
Opt is a new contributor. Be nice, and check out our Code of Conduct.
Opt is a new contributor. Be nice, and check out our Code of Conduct.
Opt 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%2f1354%2fstate-of-the-art-algorithms-for-solving-linear-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
