ECLiPSe CLP の EPLEX ライブラリを用いて混合整数線形計画問題を解く

ECLiPSe CLPのEPLEXライブラリを使用して混合整数線形計画問題を解きます。

混合整数計画問題とは、線形計画問題の変数のすべてもしくは一部が整数という条件がついた問題です。

Problems and exercises in Operations Research の 3.2 Gomory cutsの問題を解きます。

OR_excersize_3_2
ほぼ線形計画問題と同じですが、x(x1とx2)に整数であるという条件がついています。

線形計画法の時と比べたプログラムの書き方の違いなのですがなんと整数の制約を持つ変数にintegers制約を追加するだけでできてしまいます。(下記のプログラムの13行目)
線形計画問題と混合整数計画問題の解き方の違いとして、混合整数計画問題のほうは分枝限定法を使用したり複雑な方法になるのですが、それらはライブラリの中で行ってくれるため使用する側はほとんど手間が変わりません。

プログラム:

:- lib(eplex).
:- eplex_instance(prob). % declare an eplex instance

solve(Cost, Vars) :-
	% create the problem variables and set their range
	Vars = [X1,X2],
	prob: (Vars $:: 0.0..1.0Inf),
	% post the constraints for the problem to the eplex instance
	prob: (-4*X1 + 6*X2 $=< 9),
	prob: (X1 + X2 $=< 4),
	prob: (X1 $>= 0),
	prob: (X2 $>= 0),
	prob: integers(Vars),
	
	% set up the external solver with the objective function
	prob: eplex_solver_setup(min(X1 - 2*X2)),
	prob: eplex_solve(Cost). % Solve problem using external solver

実行結果:

?- solve(Cost, [X1, X2]).
Cost = -3.0
X1 = X1{0.0 .. 1.7976931348623157e+308 @ 1.0}
X2 = X2{0.0 .. 1.7976931348623157e+308 @ 2.0}
Yes (0.00s cpu)

X1 = 1
X2 = 2
が解答です。かなり便利です!

コメント

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です