How many decision variables can be solved for Mixed Integer Programming?

 

I have a Mixed Integer Programming problem(binary integer variables), how many variables can I solve, ie, upper limit and what would be time taken?

The problem would have a utmost 5 constraints and a minimisation cost function, but variables are in the form of a matrix of m*n. So, the question is what could be the max values of m and n, also the time it would take to finish the computation?

Using standard software/libraries like COIN CBC, GLPK, CPLEX, GUROBI.

Is it really possible to use the open-source/commercial solvers, available in the market, to solve it ?

Short answer : Yes it is possible to solve MIP with millions of decision variables.

Theory

In general MIP is NP-hard problem and cannot be solved in polynomial times O(n^k). Also it is NOT straightforward to determine what is input "n" in for MIP problem. Is it no. of rows, column or their product, nature of the matrix A , nature of decision variables, gap between MIP and relaxed LP?

If IP formulation ( Ax = b ), the matrix A is totally unimodular, and all coefficients are integers, then the solution of the LP relaxation is also a solution of IP, and thus the complexity of your problem is polynomial .

If not, then you should expect the problem to be NP-hard in the general case. As a thumb rule, the more variables and the more constraints, the harder is the problem.

Practice

MIP/LP Solvers can use various techniques/algorithms to solve any problem in reasonable amount of time (in hours), especially if you are not looking for "the" optimal integer solution and willing to accept solution close the optimal.

There is no fixed size limit — the Gurobi Optimizer routinely solves models with millions of variables and constraints, even on standard laptop and desktop computers. More importantly, you can see the results in Gurobi's performance, particularly on larger, more difficult models. In fact, Gurobi recently solved 11 models in the MIPLIB2010 library that had not previously been solved by any other solver.

Source: http://www.gurobi.com/products/gurobi-optimizer

Special MIP Problems

Special techniques are available to solve special instances of MIPs.

  • Cutting stock problem
  • bin packing problem : special case of the cutting stock problem.

    • I wrote simple column generation algorithm to solve cutting stock problems. See https://github.com/vcphub/cspsol

    链接地址: http://www.djcxy.com/p/39988.html

    上一篇: 非确定性多项式（NP）与多项式（P）？

    下一篇: 混合整数编程可以解决多少个决策变量？