nAG数値計算ライブラリ
> 最適化アルゴリズムExample集
> 疎な大規模線形計画問題の内点法による解法
大規模線形計画法-LP（疎、内点法）
このExampleでは、内点法を用いて7変数の線形計画問題(LP)を解いています。問題サイズが小さいため、内点法の使用方法を簡潔に示すことを目的としています。
目的関数:
| タスク | 式 |
|---|---|
| minimize | \(-0.02x_1 - 0.2x_2 - 0.2x_3 - 0.2x_4 - 0.2x_5 + 0.04x_6 + 0.04x_7\) |
決定変数:
| 変数 | 範囲 |
|---|---|
| \(x_1\) | \(-0.01 \leq x_1 \leq 0.01\) |
| \(x_2\) | \(-0.1 \leq x_2 \leq 0.15\) |
| \(x_3\) | \(-0.01 \leq x_3 \leq 0.03\) |
| \(x_4\) | \(-0.04 \leq x_4 \leq 0.02\) |
| \(x_5\) | \(-0.1 \leq x_5 \leq 0.05\) |
| \(x_6\) | \(-0.01 \leq x_6 \leq 1e^{20}\) |
| \(x_7\) | \(-0.01 \leq x_7 \leq 1e^{20}\) |
制約条件:
| 制約 | 式 |
|---|---|
| 1 | \(x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 = -0.13\) |
| 2 | \(0.15x_1 + 0.04x_2 + 0.02x_3 + 0.04x_4 + 0.02x_5 + 0.01x_6 + 0.03x_7 \geq -0.0049\) |
| 3 | \(0.03x_1 + 0.05x_2 + 0.08x_3 + 0.02x_4 + 0.06x_5 + 0.01x_6 \geq -0.0064\) |
| 4 | \(0.02x_1 + 0.04x_2 + 0.01x_3 + 0.02x_4 + 0.02x_5 \geq -0.0037\) |
| 5 | \(0.02x_1 + 0.03x_2 + 0.01x_5 \geq -0.0012\) |
| 6 | \(0.7x_1 + 0.75x_2 + 0.8x_3 + 0.75x_4 + 0.8x_5 + 0.97x_6 \leq 0.0992\) |
| 7 | \(0.02x_1 + 0.06x_2 + 0.08x_3 + 0.12x_4 + 0.02x_5 + 0.01x_6 + 0.97x_7 \leq 0.002\) |
また、box constraintsとして各変数の上下限値が設定されています。特に\(x_6\)と\(x_7\)の上限値は非常に大きな値(\(1e^{20}\))となっており、事実上上限なしとみなせます。
Exampleの実行コマンド:
python -m naginterfaces.library.examples.opt.handle_solve_lp_ipm_exソースコード表示コマンド:
python -c "import inspect; from naginterfaces.library.examples.opt import handle_solve_lp_ipm_ex; print(''.join(inspect.getsourcelines(handle_solve_lp_ipm_ex)[0]))"出力結果例:
naginterfaces.library.opt.handle_solve_lp_ipm Python Example Results.
Solve a small LP problem.
E04MT, Interior point method for LP problems
Status: converged, an optimal solution found
Final primal objective value 2.359648E-02
Final dual objective value 2.359648E-02
マニュアル:
ソース:
#!/usr/bin/env python3
"``naginterfaces.library.opt.handle_solve_lp_ipm`` Python Example."
# nAG Copyright 2018-2020.
# pylint: disable=invalid-name
from naginterfaces.base import utils
from naginterfaces.library import opt
def main():
"""
Example for :func:`naginterfaces.library.opt.handle_solve_lp_ipm`.
Large-scale linear programming based on an interior point method.
>>> main()
naginterfaces.library.opt.handle_solve_lp_ipm Python Example Results.
Solve a small LP problem.
E04MT, Interior point method for LP problems
Status: converged, an optimal solution found
Final primal objective value 2.359648E-02
Final dual objective value 2.359648E-02
"""
print(
'naginterfaces.library.opt.handle_solve_lp_ipm Python Example Results.'
)
print('Solve a small LP problem.')
# The problem size:
n = 7
# Create a handle for the problem:
handle = opt.handle_init(nvar=n)
# Set the objective function:
opt.handle_set_quadobj(
handle,
idxc=list(range(1, n+1)),
c=[-0.02, -0.2, -0.2, -0.2, -0.2, 0.04, 0.04],
)
# Set box constraints:
opt.handle_set_simplebounds(
handle,
bl=[-0.01, -0.1, -0.01, -0.04, -0.1, -0.01, -0.01],
bu=[0.01, 0.15, 0.03, 0.02, 0.05, 1.e20, 1.e20],
)
# Set linear constraints:
opt.handle_set_linconstr(
handle,
bl=[-0.13, -1.e20, -1.e20, -1.e20, -1.e20, -0.0992, -0.003],
bu=[-0.13, -0.0049, -0.0064, -0.0037, -0.0012, 1.e20, 0.002],
irowb=[
1, 1, 1, 1, 1, 1, 1,
2, 2, 2, 2, 2, 2, 2,
3, 3, 3, 3, 3, 3,
4, 4, 4, 4, 4,
5, 5, 5,
6, 6, 6, 6, 6, 6,
7, 7, 7, 7, 7, 7, 7,
],
icolb=[
1, 2, 3, 4, 5, 6, 7,
1, 2, 3, 4, 5, 6, 7,
1, 2, 3, 4, 5, 6,
1, 2, 3, 4, 5,
1, 2, 5,
1, 2, 3, 4, 5, 6,
1, 2, 3, 4, 5, 6, 7,
],
b=[
1., 1., 1., 1., 1., 1., 1.,
0.15, 0.04, 0.02, 0.04, 0.02, 0.01, 0.03,
0.03, 0.05, 0.08, 0.02, 0.06, 0.01,
0.02, 0.04, 0.01, 0.02, 0.02,
0.02, 0.03, 0.01,
0.7, 0.75, 0.8, 0.75, 0.8, 0.97,
0.02, 0.06, 0.08, 0.12, 0.02, 0.01, 0.97,
],
)
# Set some algorithmic options.
for option in [
'Print Options = NO',
'Print Level = 1',
'LPIPM Stop Tolerance = 1.0e-10',
'LPIPM Centrality Correctors = -6',
]:
opt.handle_opt_set(handle, option)
# Use an explicit I/O manager for abbreviated iteration output:
iom = utils.FileObjManager(locus_in_output=False)
# Solve the problem.
# The default primal-dual algorithm is employed:
opt.handle_solve_lp_ipm(handle, io_manager=iom)
# Destroy the handle:
opt.handle_free(handle)
if __name__ == '__main__':
import doctest
import sys
sys.exit(
doctest.testmod(
None, verbose=True, report=False,
optionflags=doctest.ELLIPSIS | doctest.REPORT_NDIFF,
).failed
)