Python 種々の最適化ライブラリ

はじめに

線形計画の簡単な例を種々の最適化ライブラリを使用して解いてみます。

使用するライブラリ

Pulp
Scipy
Google Ortools

コード例

Github

問題設定

最大化する目的関数　100x + 100 y

制約条件
x + 2y <=16
3x + y <= 18
x >0
y>0

Pulp

import pulp
# Problem 1

# Numerical model
m = pulp.LpProblem(sense=pulp.LpMaximize) 

# valiables to optimize
x = pulp.LpVariable('x', lowBound=0) 
y = pulp.LpVariable('y', lowBound=0) 

# Objective function to optimize ( maximize)
m += 100 * x + 100 * y

#  Constraints
m += x + 2 * y <= 16 
m += 3 * x + y <= 18 

# Solve
m.solve()
print(pulp.value(x), pulp.value(y)) # 4, 6

scipy

from scipy.optimize import fmin,minimize

# Problem1


# Objective
def func(X):
    return -(100*X[0]+100*X[1])

# constraint function
def cons1(X):
    return 16-(X[0] + 2*X[1])
def cons2(X):
    return 18-(3*X[0] + X[1])
def cons3(X):
    return np.abs(X)

# set constraits (negative constraint)
cons = (
    {'type': 'ineq', 'fun': cons1},
    {'type': 'ineq', 'fun': cons2},
    {'type': 'ineq', 'fun': cons3},
)
X = [1.0,1.0] #init

# result = minimize(func, x0=X, constraints=cons, method="SLSQP")
result = minimize(func, x0=X, constraints=cons, method="COBYLA")

print(result)

Google Or-tools

from __future__ import print_function
from ortools.linear_solver import pywraplp

solver = pywraplp.Solver('SolveIntegerProblem',
                         pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)


# Problem1

# set variables
# x and y are integer non-negative variables.
x = solver.IntVar(0.0, solver.infinity(), 'x')
y = solver.IntVar(0.0, solver.infinity(), 'y')


# constraints
constraint1 = solver.Constraint(-solver.infinity(), 16)
constraint1.SetCoefficient(x, 1)
constraint1.SetCoefficient(y, 2)

constraint2 = solver.Constraint(-solver.infinity(), 18)
constraint2.SetCoefficient(x, 3)
constraint2.SetCoefficient(y, 1)

# Objective  .
objective = solver.Objective()
objective.SetCoefficient(x, 100)
objective.SetCoefficient(y, 100)
objective.SetMaximization()

"""Solve the problem and print the solution."""
result_status = solver.Solve()
# The problem has an optimal solution.
assert result_status == pywraplp.Solver.OPTIMAL

# The solution looks legit (when using solvers other than
# GLOP_LINEAR_PROGRAMMING, verifying the solution is highly recommended!).
assert solver.VerifySolution(1e-7, True)

print('Number of variables =', solver.NumVariables())
print('Number of constraints =', solver.NumConstraints())

# The objective value of the solution.
print('Optimal objective value = %d' % solver.Objective().Value())
print()
# The value of each variable in the solution.
variable_list = [x, y]

for variable in variable_list:
  print('%s = %d' % (variable.name(), variable.solution_value()))