nAG数値計算ライブラリ
> 最適化アルゴリズムExample集
> 疎な大規模線形計画問題の内点法による解法
大規模線形計画法-LP（疎、内点法）
このExampleでは、内点法を用いて7変数の線形計画問題(LP)を解いています。問題サイズが小さいため、内点法の使用方法を簡潔に示すことを目的としています。
目的関数:
| タスク | 式 |
|---|---|
| minimize |
決定変数:
| 変数 | 範囲 |
|---|---|
制約条件:
| 制約 | 式 |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 |
また、box
constraintsとして各変数の上下限値が設定されています。特に
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
)