The power of combinatorial optimization solvers

what is this

Let's try the power (performance) of the solver that solves the optimization problem by using a random and simple problem (knapsack problem).

Create a random knapsack problem

Create a knapsack problem [^ 1] with n items. The optimum solution is adjusted to be about 80% of the total number of items.

python

import numpy as np
from pulp import *
def make(n):
    np.random.seed(1)
    w = 1 + np.random.rand(n)
    p = w + np.random.randn(n)*0.1
    m = LpProblem(sense=LpMaximize)
    v = [LpVariable('x%d'%i, cat=LpBinary) for i in range(n)]
    m += lpDot(p, v)
    m += lpDot(w, v) <= int(n*1.25)
    return v, m

Check the calculation time

Let's see the calculation time while changing the number of items. The optimization solver uses GUROBI 6.51.

python

v, m = make(10000)
%timeit -n 3 m.solve(GUROBI_CMD())
sum(value(x) for x in v)
>>>
3 loops, best of 3: 222 ms per loop
8254.0

python

v, m = make(20000)
%timeit -n 3 m.solve(GUROBI_CMD())
sum(value(x) for x in v)
>>>
3 loops, best of 3: 486 ms per loop
16470.0

python

v, m = make(50000)
%timeit -n 3 m.solve(GUROBI_CMD())
sum(value(x) for x in v)
>>>
3 loops, best of 3: 1.38 s per loop
41237.0

python

v, m = make(100000)
%timeit -n 3 m.solve(GUROBI_CMD())
sum(value(x) for x in v)
>>>
3 loops, best of 3: 2.64 s per loop
82458.0

Summary

When there are n items, there are $ 2 ^ n $ possible choices. Also, since this calculation time is the time to find the exact solution, we are investigating (almost) all of this possibility [^ 2].

――The number of possible solutions increases exponentially with the number of items. However, the calculation time is close to linear. ――It took less than 3 seconds to find out the tremendous combination of 10 to the 30,000th power [^ 3].

You can see how high performance the recent solvers are. However, it should be noted that the performance may be significantly deteriorated depending on the type of combinatorial optimization problem and the method of formulation.

The knapsack problem is NP-complete, but you can see the solver's high performance even in the maximum weight matching problem with class P (Comparison of solutions in weight matching problem. 7fd199a95d78a6f3b741)).

reference

-Use combinatorial optimization --Professor Miyashiro's Memo of Integer Programming --Knapsack problem related -Combinatorial optimization-Typical problem-Knapsack problem -Determine golf expectations using dynamic optimization -Illustration of the results of the knapsack problem --Solver related -Introduction to Formulation by Integer Programming -Introduction to Integer Programming Solver -Mathematical optimization by ZIMPL language and SCIP - Gurobi Optimizer

that's all

[^ 1]: The knapsack problem is an NP-hard problem and it is thought that there is no solution on the order of polynomials, but the solver can solve it efficiently. [^ 2]: We are looking for a solution whose ratio difference is ε or less with respect to the value of the objective function of the exact optimal solution. By default, it seems to be ε = 0.0001 (reference integer programming memo). [^ 3]: Even the number of atoms in the universe is about $ 10 ^ {80} $, which is much smaller.