Search code examples
linear-programmingcplexglpkinteger-programmingcoin-or-cbc

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, i.e, 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.

Solution

  • 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.

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