GLPK by GLPK http://mukun mmg.at.infoseek.co.jp/mmg/glpk/ 17 7 5 : update 1 GLPK GNU Linear Programming Kit GNU LP/MIP ILOG AMPL(A Mathematical Programming Language) 1. 2. 3. 2 (optimization problem) X S X f : X R f ( x S f(x) (1) x S (2) f (objective function) S (feasible region) (2) (constraint condition) x S f(x ) 1
f(x) x S (optimal solution) f(x ) (optimal value) f(x) (1) 3 GLPK glpsol -m -d -m glpsol -h -m -d -o -y --simplex ( ) --interior --min --max --check --nomip MIP LP --wmps MPS ( ) --wlpt CPLEX ( ) --wtxt ( ) glpsol -m model1.mod -d data1.dat -o result1.sol --wlpt cplexform.txt --min result1.sol CPLEX cplexform.txt 4 GLPK.mod 2
.dat 5 (set) GLPK set 5.1 set {, }; ) Node set Node; 5.2 := )Node 1,2,3,4 set Node := 1 2 3 4; 6 (parameter) 0 GLPK param 6.1 param {, }; 3
) Cost i i Node param Cost{Node}; 6.2 1 2 ) 1) 1 5 2 3 3 6 4 9 param Cost := 1 5 2 3 3 6 4 9; 2) param Cost[1] := 5; param Cost[2] := 3; param Cost[3] := 6; param Cost[4] := 9; ) ( ) 4
1 p 10 1 q 20 2 p 15 2 q 23 3 p 12 3 q 18 1 2 (tr) tr (transpose matrix) 1) 2) tr 1) param Val: p q := 1 10 20 2 15 23 3 12 18 2) param Val(tr): 1 2 3:= p 10 15 12 q 20 23 18 ) ( ) 1 2 1 10 1 2 2 15 1 3 1 13 1 3 2 17 5
1) param ArcResourceFC := 1 2 1 10 1 2 2 15 1 3 1 13 1 3 2 17 ; 2) param ArcResourceFC[1,2,1] := 10; param ArcResourceFC[1,2,2] := 15; param ArcResourceFC[1,3,1] := 13; param ArcResourceFC[1,3,2] := 17; ) param : ) 1 2 1 1 1 3 1 2 2 1 2 6 1 3 1 1 1 4 1 3 2 1 2 8 param: LT CT:= 1 2 1 1 1 3 1 2 2 1 2 6 6
1 3 1 1 1 4 1 3 2 1 2 8 ; 7 (variable) 0 GLPK var var {, } )2 Flow i,j i Node, j Node GLPK var Flow{Node, Node}; 7.1 0-1 2 ) x Z + integer binary 0-1 / set x integer, >=0; 8 (constraint condition) GLPK s.t. subject to s.t. {, } ) r Res x ir M i Node 7
s.t. COND1{i in Node}: sum{r in Res}x[i,r] <= M; in sum 1 1 9 (objective function) (maximize) (minimize) GLPK maximize minimize minimize : ) : min. Cost i x i i Node minimize OBJ: sum{i in Node} Cost[i] * x[i]; 10 GLPK GNU 10.1 + - * / less A > B A-B, A < B 0 div A/B mod A/B ** ˆ A B 8
10.2 / A < B A < B A <= B A B A > B A > B A >= B A B A <> B A! = B A B A in B A B A not in B A! in B A / B A within B A B 10.2.1 if( ) then else ) t 1 X t 1 t = 1 0 if(t!=1) X[t-1] else 0 10.2.2 : )i > j (i,j) Arc w ij (i > j) sum{(i,j) in Arc : i > j} w[i,j] 10.2.3 within within ) 9
set A; set K within A; K A set A := 1 2 3 4; set K := 5; 10.3 A union B A B A diff B A/B A simdiff B A B A inter B A B A cross B A B a.. b [a,b] 10.3.1 setof setof{(, ) in } (, ) ) ARP( (i,j), (r), (p) 3 ) (i,j) (p) 2 AP set AP := setof{(i,j,r,p) in ARP}(i,j,p); 10.4 ) param p default 9999; p 9999 10
10.5 display display ; display 11
11 AMPL AMPL GLPK 300 11.1 AMPL AMPL GLPK AMPL ampl ampl: AMPL model data solve option solver expand show display reset quit exit let commands AMPL AMPL m1.mod model m1.mod; AMPL commands option solver cplex; model m1.mod; data d1.dat; solve; com1.cms commands com1.cms; expand 12
reset; quit; MINOS( ) MIP MIP option solver cplex; CPLEX( ) AMPL 13
12 12.1 unbounded (or badly scaled) problem. 1 0 12.2 ( or ) must have * subscripts rather than # *,# * # 1 1 ) set Node; set Arc{Node, Node}; var X{Arc}; X Node2 14
12.3 ( or )[ ] out of domain ( ) 1 {1..N} 2 GLPK 12.3.1 param T; # set Period := 1..T; # param T:=10; # 15
12.3.2 param T; # set Period; # param T:=10; # set Period := 1..T; # 12.4 syntax error in set statementset = := = := VB param 12.5 operand preceding = has invalid type if 16
x > 0 y = 1 if if http://www.ampl.com/faq/ 17