3

I am trying to implement a solution to a problem using Integer linear programming (ILP). As the problem is NP-hard , I am wondering if the solution provided by Simplex Method would be optimal ? Can anyone comment on the optimality of ILP using Simplex Method or point to some source. Is there any other algorithm that can provide optimal solution to the ILP problem?

EDIT: I am looking for yes/no answer to the optimality of the solution obtained by any of the algorithms (Simplex Method, branch and bound and cutting planes) for ILP.

Improve this question
12
  • 5
    Be specific. If you ask a vague question, you’ll get a vague answer. But if you give us details and context, we can provide a useful answer. Commented Mar 8, 2013 at 20:39
  • 1
    If your ILP is a correct formulation of your problem, you will get a solution corresponding to your optimization constraints. Provided you have enough patience to wait for it, which could take ages. For an np-hard problem to do with graph layouts, I used general constraint based programming last year; took more than a day for some graphs with no more than 50 vertices and 250 edges. Commented Mar 8, 2013 at 21:33
  • 1
    @RobertHarvey with all due respect, the question is not vague. harold has the correct answer. The question is probably a little advanced for SO, having more to do with mathematical algorithms than programming; but context isn't needed to understand what is being asked. Commented Mar 8, 2013 at 22:15
  • 1
    Harold's answer is precise as well as correct -- although it only answers the question of "does Simplex solve ILP problems?", not the additional question "what algorithms do solve ILP problems?" Commented Mar 8, 2013 at 22:26
  • 1
    @StackUnderflow for a general integer linear program: simplex method: no. Branch and bound: yes, in finite time and finite memory, but it can easily be too much for a typical computer to solve quickly or without running out of memory. Cutting planes: The classic Gomory cuts will eventually get you to an optimal solution. Due to numerical instability, practical implementations of them are extremely non-trivial (there were 30+ years between their development and a practical implementation). Commented Mar 11, 2013 at 16:59

2 Answers 2

Reset to default
5

The Simplex Method doesn't handle the constraint that you want integers. Simply rounding the result is not guaranteed to give an optimal solution.

Using the Simplex Method to solve an ILP problem does work if the constraint matrix is totally dual integral.

Some algorithms that solve ILP (not constrained to totally dual integral constraint matrixes) are Branch and Bound, which is simple to implement and generally works well if the costs are reasonably uniform (very non-uniform costs make it try many attempts that look promising at first but turn out not to be), and Cutting Plane, which I honestly don't know much about but it's probably good because people are using it.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

-2

The solution set for a linear programming problem is optimal by definition.

Linear programming is a class of algorithms known as "constraint satisfaction". Once you have satisfied the constraints you have solved the problem and there is no "better" solution, because by definition the best outcome is to satisfy the constraints.

If you have not completely modeled the problem, however, then obviously some other type of solution may be better.

Clarification: When I write above "satisfy the constraints", I am including maximization of objective function. The cutting plane algorithm is essentially an extension of the simplex algorithm.

Improve this answer

4 Comments

Downvoted because this answer is wrong. In a linear program, you're searching for a solution that both satisfies the constraints and optimizes (either minimizes or maximizes) a given objective function. It also doesn't answer the question of what algorithms can solving integer programs.
The answer says "Once you have satisfied the constraints you have solved the problem and there is no "better" solution, because by definition the best outcome is to satisfy the constraints." This isn't true in general. You don't just want to satisfy the constraints, you want to minimize (or maximize) the objective function.
OP was asking about Integer LP methods, which experience suggests are going to produce a less-optimal solution than might be obtained by removing the integer-only requirement. Your answer seems to have ignored this point. Additionally @raoulcousins point about maximizing or minimizing the objective function subject to the constraints is well taken.
If you solve an ILP problem using the simplex method, then (1) the constraints WILL be satisfied, and (2) the objective function WILL be maxed. So, the answer will be optimal. Cased closed. Possibly the OP really means to be asking, Is there a known better technique than the simplex method for ILP? and the answer to that is not really (if we are considering cutting plane approaches to be variations of the simplex method).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.