Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

Many important problems can be expressed as a mixed integer linear program. Unfortunately computing the optimal solution to this class of problems is NP-Complete. Luckily there are approximation algorithms that can sometimes provide quality solutions with only moderate amounts of computation.

How should I analyze a particular mixed integer linear program to see if it lends itself to one of these approximation algorithms? What are the relevant traits or qualities such a program might possess?

What are the relevant algorithms in use today and how do these qualities map onto these algorithms?

What software packages should I look to for experimentation?

share|improve this question
add comment

1 Answer

up vote 13 down vote accepted

Although mixed-integer linear programming (MILP) is indeed NP-complete, there are solvable (nontrivial) instances of mixed-integer linear programming.

NP-complete means that mixed integer linear programming is:

a) solvable in polynomial time with a nondeterministic Turing machine (the NP part)

b) polynomial time reducible to 3-SAT (the complete part; for the rest of the discussion, this part really doesn't matter)

In practical terms, since we don't have nondeterministic Turing machines and can't write algorithms that do things like, "set our binary decision variables to all possible combinations of zero and one, and solve the resulting linear programs (LPs)" in polynomial time, that means that in an asymptotic sense, MILP is $\mathcal{O}(2^{n})$, where $n$ is the number of binary variables. That statement means that as problem instances get very large, they will require large amounts of computing power to solve.

That statement doesn't mean that "small" instances are intractable. Unfortunately, I can't make a precise statement of what small means for an MILP instance. I solve problems that have 3,000 or more binary decision variables on a routine basis. Depending on the problem formulation, the problems could take less than .01 seconds (which is the case for relatively under-constrained problems) or more than an hour (which is the case for problems where many constraints are active), because the problems seem to have favorable structure. I can say that state of the art LP solvers can solve LPs with several million continuous decision variables, and that without special structure, it's highly unlikely that a problem instance with somewhere around 1,000 to 10,000 binary variables will be solvable in reasonable amounts of time with state-of-the-art MILP algorithms.

If you think you have a solvable instance of MILP, you will want to use a branch-and-bound or branch-and-cut algorithm. The best implementations are CPLEX and Gurobi. Both of them are commercial products that have free academic licensing if you dig around enough. If you really need an open source solver, projects in the COIN-OR community are more appropriate, although the source packages can be finicky sometimes. The most relevant projects would be the CBC branch-and-cut solver, the SYMPHONY solver, the BCP branch-cut-price solver, and the ABACUS branch-and-cut solver. All of these projects will require multiple packages from COIN-OR, due to its modular structure.

If you would like the option to try multiple solvers, your best bet is to use the Open Solver Interface from COIN-OR. Be advised that portions of this interface will only let you set basic solver options, and that to set advanced options for solvers, you should consult the mailing lists of COIN-OR for further details. The commercial MILP solvers are MUCH (sometimes an order of magnitude or more) faster than the open source solvers. Another option for prototyping is use of an algebraic modeling language like GAMS or AMPL. Both software packages are commercial, but have trial versions that can be used on small problem instances. For larger problem instances, you could submit GAMS or AMPL files to the NEOS server to be solved; this server is available to the public.

If you have a sufficiently large instance of MILP, then none of these solvers will work well. You could relax the integer variables to continuous variables, solve the problem, and then round to the nearest collection of integer variables that is a feasible solution of your problem instance. An optimal solution of the LP relaxation of your MILP will give you a lower bound on the optimal objective function value of your MILP (assuming minimization, of course), and a feasible solution of your MILP will give you an upper bound on the optimal objective function value of your MILP.

If you're really lucky and your constraint matrix is totally unimodular, then you can use an LP solver to generate integer solutions to your MILP, and you can solve your problem efficiently despite its large size. Other classes of problems have fast approximation algorithms, such as knapsack problems and cutting stock problems. Specialized MILP decomposition algorithms also exist for problems that have special structure, though I am not familiar with the particulars, since those topics are somewhat specialized and outside the scope of my thesis.

I'm not aware of a fully polynomial time approximation scheme (FPTAS) specifically for MILP, though an FPTAS of a problem class that includes MILP exists (see this paper). My recommendation would be to use one of the mixed-integer linear programming solvers above in conjunction with a time limit and appropriate tolerances on optimality gaps. Doing so would give you the best possible feasible solution to your MILP within the time limit, and if the solver terminates successfully prior to the time limit, the feasible solution would be optimal to within the optimality gap tolerances you set. This course of action would still give you bounds on the quality of the solution, because your feasible solution would be an upper bound, and the solver could give you an appropriate lower bound. The bound wouldn't be guaranteed to be within a certain factor optimal solution, but then again, any FPTAS will become more expensive as the approximation becomes better.

The most important thing you can do before you settle on an MILP formulation is to pick the strongest formulation that you can find; you can find advice on how to pick strong formulations in Introduction to Linear Optimization by Bertsimas and Tsitsiklis. The main idea is to pick a formulation whose constraints define a polytope that is as close to the convex hull of the formulation as possible (also see these course notes). Picking a strong formulation can make a huge difference in the time it takes to solve a problem.

share|improve this answer
    
What are examples of the sort of favorable structure you refer to? What are some questions that I should be asking about my program? –  MRocklin Jan 11 '12 at 2:37
    
Aside from unimodularity, knapsack problems, and cutting stock problems, if your problem is a multi-stage stochastic program, there are decomposition strategies to take advantage of that structure. You can employ methods like (generalized) Benders' decomposition, Dantzig-Wolfe decomposition, and L-shaped decomposition. You can also take advantage of block-angular structure in your constraints. Dantzig-Wolfe decomposition, Benders' decomposition, and generalized Benders' decomposition are methods I've used once or twice in the past for homework problems. –  Geoff Oxberry Jan 11 '12 at 2:53
    
There are some other tricks and traps that Geoff didn't mention, but it's hard to come up with any specific advice without seeing the exact problem or class. –  Aron Ahmadia Jan 11 '12 at 10:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.