Modeling in GNU MathProg language a short introduction

Pawe Zielinski
Institute of Mathematics and Computer Science, Wrocaw University of Technology, Poland

General informations

Webpages: My home page: http://www.im.pwr.wroc.pl/ pziel/ The GNU Linear Programming Kit (GLPK): glpsol solver

plus the GNU MathProg modeling language The software is free and can be downloaded:
GUSEK (GLPK Under Scite Extended Kit): The GLPK +

IDE - Windows version: http://gusek.sourceforge.net/,

GLPK (GNU Linear Programming Kit) for Windows (without

IDE): http://gnuwin32.sourceforge.net/packages/glpk.htm,
GLPK (GNU Linear Programming Kit) sources (without

IDE): http://www.gnu.org/software/glpk/glpk.html

Linear programming problem

n

cj xj min(max)
j =1 n

(a linear objective function)

aij xj = (, )bi ,
j =1

i = 1, . . . , m (linear constraints) j = 1, . . . , n (nonnegative variables)

xj 0,

Parameters (input data): cj , j = 1, . . . , n, objective function coefcients, bi , i = 1, . . . , m, the right hand side vector coefcients, aij , i = 1, . . . , m, j = 1, . . . , n, matrix coefcients. xj , j = 1, . . . , n, decision variables (output).

Linear programming problem (LP)

Example 1: Solve the following linear programming problem:
4x1 + 5x2 max x1 + 2x2 40 4x1 + 3x2 120 x1 0, x2 0
/* decision variables*/ var x1 >= 0; var x2 >=0; /* Objective function */ maximize label : 4*x1 +5*x2; /* Constraints */ subject to label1: x1 + 2*x2 <= 40; s.t. label2: 4*x1 + 3*x2 <= 120; end;

Solve the above model (feasible.mod) in glpsol. glpsol --model feasible.mod glpsol --model feasible.mod --output feasible.txt

Linear programming problem

Example 2: Solve the following linear programming problem:
4x1 + 2x2 max x1 + x2 = 40 x1 + x2 120 x1 0, x2 0 The set of feasible solutions is empty - there is no a feasible solution.
/* The declaration of decision variables x1, x2 var x1 >= 0; var x2 >=0; /* Objective function */ maximize ObjectiveFunctionLabel : 4*x1 +2*x2; /* Constraints */ s.t. label1: x1 + x2 = 2; s.t. label2: x1 + x2 >= 4; end; */

Solve the above model (infeasible.mod) in glpsol. glpsol --model infeasible.mod

Linear programming problem

Exercise: Implement in GNU MathProg and try to solve the

following linear programming model (surprise!): 4x1 + 2x2 max 3x1 + 6x2 18 x1 2x2 4 x1 0, x2 0

LP: a production planning problem

Example 3: (S.P. Bradley, A.C. Hax, T.L. Magnanti, Applied Mathematical
Programming, 1977) The Candid Camera Company manufactures three lines of cameras: the Cub, the Quickiematic and the VIP, whose contributions are $3, $9, and $25, respectively. The distribution center requires that at least 250 Cubs, 375 Quickiematics, and 150 VIPs be produced each week. Each camera requires a certain amount of time in order to: (1) manufacture the body parts; (2) assemble the parts (lenses are purchased from outside sources and can be ignored in the production scheduling decision); and (3) inspect, test, and package the nal product. The Cub takes 0.1 hours to manufacture, 0.2 hours to assemble, and 0.1 hours to inspect, test, and package. The Quickiematic needs 0.2 hours to manufacture, 0.35 hours to assemble, and 0.2 hours for the nal set of operations. The VIP requires 0.7, 0.1, and 0.3 hours, respectively. In addition, there are 250 hours per week of manufacturing time available, 350 hours of assembly, and 150 hours total to inspect, test, and package. Maximize contribution.

LP: a production planning problem

Denitions of decision variables: cub - total number of the Cub produced, quick - total number of the Quickiematic produced, vip - total number of the VIP produced. The constraints: 0.1 cub + 0.2 quick 0.2 cub + 0.35 quick 0.1 cub + 0.2 quick cub quick + 0.7 vip 250, + 0.1 vip 350, + 0.3 vip 150, 250, 375, vip 150.

The objective function: 3 cub + 9 quick + 25 vip max.

The rst approach (old one) - a mixture of data and model

/* decision variables */ var cub >=0; var quick >=0; var vip >=0; # # # the number of the Cub produced the number of the Quickiematic produced the number of the VIP produced

/* objective function represents profit */ maximize profit: 3*cub + 9*quick + 25*vip; /* constraints determine composition manufacturing cameras */ s.t. s.t. s.t. s.t. s.t. s.t. end; time_manufacture: 0.1*cub + 0.2*quick + time_assemble: 0.2*cub + 0.35*quick + time_inspect: 0.1*cub + 0.2*quick + requirements_cub: cub requirements_quick: quick requirements_vip: 0.7*vip <= 250; 0.1*vip <= 350; 0.3*vip <= 150; >= 250; >= 375; vip >= 150;

glpsol --model camera.mod --output camera.txt

Towards isolating the data from the model - arrays and sets
/* Arrays and sets */ /* enumerated set Cameras represents the set of cameras manufactured by the company */ set Cameras; /* array of three decision variables: production[cub], production[quick] and production[vip] */ var production{Cameras} >=0; /* objective function represents profit */ maximize profit: 3*production[cub] + 9*production[quick] + 25*production[vip]; /* constraints determine composition manufacturing cameras */ s.t. man: 0.1*production[cub] + 0.2*production[quick] +0.7*production[vip] <= 250; s.t. ass: 0.2*production[cub] + 0.35*production[quick] +0.1*production[vip] <= 350; s.t. insp: 0.1*production[cub] +0.2*production[quick] +0.3*production[vip] <= 150; s.t. requirements_cub: s.t. requirements_quick: s.t. requirements_vip: production[cub] production[quick] production[vip] >= 250; >= 375; >= 150;

data; /* Definition of the set Cameras */ set Cameras:= cub quick vip; end;

Model: camera_arrays.mod

Towards isolating the data from the model - arrays and sets
The declaration of the set of cameras manufactured by the

company: set Cameras; The initialization of the set Cameras set Cameras:= cub quick vip;
The declaration of array of three nonnegative decision

variables indexed by Cameras (production[cub], production[quick]and production[vip]): var productionCameras >=0

Other examples:

set Range:= 1..n; set MyIntegerSet:= 4 8 9 10 ; var array{1..m};

Isolating the data from the model - the data

/* Data section */ data; /* Definitions of the sets */ set Cameras:= cub quick vip; set Times:= manufacture assemble inspect; /* The initialization of the parameters */ param profit:= cub 3 quick 9 vip 25; 350 inspect 150; 150;

param capacity:= manufacture 250 assemble param demand:=cub 250 quick 375 vip

param consumption: cub quick vip:= manufacture 0.1 0.2 0.7 assemble 0.2 0.35 0.1 inspect 0.1 0.2 0.3; end;

Model: camera_isolation.mod

Isolating the data from the model - the data

Declaring and initializing one dimensional array of prot:
param profit{Cameras} >=0; param profit:= cub 3 quick 9 vip 25;

Declaring and initializing one dimensional array of amount of times:

param capacity{Times} >=0; param capacity:= manufacture 250 assemble 350 inspect 150;

Similarly declaring and initializing one dimensional array of the

distribution center requirements.

Declaring and initializing two dimensional array:

param consumption{Times,Cameras} param consumption: cub quick manufacture 0.1 0.2 assemble 0.2 0.35 inspect 0.1 0.2 >=0; vip:= 0.7 0.1 0.3;

Isolating the data from the model - the model

set Cameras; set Times; /* Parameters */ param param param param profit{Cameras} >=0; # one dimensional array of profit consumption{Times,Cameras} >=0; # two dimensional array capacity{Times} >=0; # one dimensional array of amount of times demand{Cameras} >=0; # one dimensional array of the distribution center requirements

/* Variables */ var production{j in Cameras} >=demand[j]; # decision variables plus trivial bounds /* objective function represents profit */ maximize Profit: sum{j in Cameras} profit[j]*production[j]; /* constraints determine composition manufacturing cameras */ s.t. time{i in Times}: sum{j in Cameras} consumption[i,j]*production[j] <=capacity[i];

Model: camera_isolation.mod

Aggregate operators and quantiers

The aggregate operator sum in the objective function:

sum{j in Cameras} profit[j]*production[j]; Other aggregate operators: prod, max, min.

The universal quantier: time{i in Times} - closely related

constraints s.t. time{i in Times}: sum{j in Cameras} ...;

The trivial bounds:

var production{j in Cameras} >=demand[j];

One may add the bounds to the constraints using universal quantier:
requirements{j in Cameras} s.t. requirements{j in Cameras}: production[j]>=demand[j];

Solving and checking the model

Solving the model:
glpsol --model camera_isolation.mod

Solving the model and writing results to the le:

glpsol --model camera_isolation.mod --output camera_isolation.txt

Checking the model without solving it:

glpsol --check --model camera_isolation.mod

Checking the model without solving it and writing the generated model
to the le:
glpsol --check --model camera_isolation.mod --wcpxlp camera_isolation.lp \* Problem: camera_isolation *\ Maximize Profit: + 3 production(cub) + 9 production(quick) + 25 production(vip) Subject To time(manufacture): + 0.1 production(cub) + 0.2 production(quick) + 0.7 production(vip) <= 250 time(assemble): + 0.2 production(cub) + 0.35 production(quick) + 0.1 production(vip) <= 350 time(inspect): + 0.1 production(cub) + 0.2 production(quick) + 0.3 production(vip) <= 150 Bounds production(cub) >= 250 production(quick) >= 375 production(vip) >= 150 End

Displaying results, the data section in a separated le

Displaying results: maximize Profit: sum{j in Cameras} profit[j]*production[j]; s.t. time{i in Times}: sum{j in Cameras} consumption[i,j]*production[j] <=capacity[i]; solve; /* solve command is needed !!!*/ display production; display -----------more elegant way -------------; display profit =, sum{j in Cameras} profit[j]*production[j]; display{j in Cameras} production[j];

the data section in a separated le camera_isolation1.dat data; set Times:= manufacture assemble inspect; param: Cameras: profit demand := cub 3 250 quick 9 375 vip 25 150; param capacity:= manufacture 250 assemble 350 inspect 150; param consumption: cub quick vip:= manufacture 0.1 0.2 0.7 assemble 0.2 0.35 0.1 inspect 0.1 0.2 0.3; end;

Solving the model: glpsol --model camera_isolation1.mod --data camera_isolation1.dat

Integer programming problem (IP)

n

cj xj min(max)
j =1 n

(a linear objective function)

aij = (, )bi ,
j =1

i = 1, . . . , m (linear constraints) j = 1, . . . , n (nonnegative variables) j = 1, . . . , n

xj 0, xj integer, (binary)

The integrality constraints on variables make the general integer programming problem NP-hard and thus very hard from computational point of view. If there exist real nonnegative variables and integer variables in a model, then we call the problem the Mixed Integer programming Problem (MIP) MIP=LP+IP

Mixed Integer programming Problem (MIP)

Example 4: Solve the following mixed integer programming
problem: 3x1 2x2 + 10 max x1 2x2 + x3 2x1 + x2 + x1 , x2 , x3 , x4 0 x2 , x3 integer = 2.5; 1.5

x4

var x1 >= 0; var x4 >=0; /* The declaration of nonnegative integer decision variables*/ var x2 integer >= 0; var x3 integer >=0; /* Objective function */ maximize ObjectiveFunctionLabel : -3*x1 -2*x2+10; /* Constraints */ s.t. label1: s.t. label2: end;

x1 - 2*x2 + x3 2*x1 + x2

= 2.5; +x4 >= 1.5;

Solve the above model (mip.mod) in glpsol. glpsol --model mip.mod glpsol --model mip.mod --output mip.txt

Integer programming Problem (IP)

Example 5: Let E = {1, 2, . . . , n} be a given set of items. A nonnegative real cost ci is associated with every item i E and we wish to choose a subset X E that contains exactly p items, whose total cost i X ci is minimal. The model has the following form:
n

ci xi min
i =1 n

xi = p
i =1

xi {0, 1}, i = 1, . . . , n xi is a binary decision variable that takes value 1 if and only if i -th item belongs to X .

Integer programming Problem (IP)

/* input data */ param n, integer, >= 1; # the param p, integer, >= 1, <n; # the set E:={1..n}; # the param c{E} >=0; # the /* The variables */ var x{E} binary; number of items number of items for selecting set of items costs of items

/* The objective function */ minimize TotalCost: sum{i in E} c[i]*x[i]; /* The constraint */ s.t. exact_p: sum{i in E} x[i] = p; solve; /* Displaying results */ display solution X; display{i in E: x[i]=1 }: x[i]; display total costs=,sum{i in E} c[i]*x[i]; /* Data section */ data; param n:=10; param p:=6; param c:=[1] 3 [2] 2 [3] 6 [4] 3 [5] 9 [6] 5 [7] 8 [8] end;

1 [9] 2 [10] 6;

Solve the above model (selecting.mod) in glpsol. glpsol --model selecting.mod

Integer programming Problem (IP)

Example 6: The multidimensional zero-one knapsack problem can be described as follows: given two sets of n items and m knapsack constraints (or resources), for each item j a prot pj is assigned and for each constraint i a consumption value rij is designated. The goal is to determine a set of items that maximizes the total prot, not exceeding the given constraint capacities ci . The problem is a well-known NP-Hard combinatorial optimization problem. The multidimensional zero-one knapsack problem can modeled:
n

pj xi max
j =1 n

rij xj ci ,
j =1

i = 1, . . . , m j = 1, . . . , n

xj {0, 1}, xj = 1 if and only if the j -th item is chosen.

Integer programming Problem (IP)

/* Parameters */ param n>0 integer; /* the number of items */ param m>0 integer; /* the number of resources */ /* Sets */ set Items:=1..n; set Resources:=1..m; /* parametry */ param capacity{Resources}>=0; /* array represents the capacity of the resources*/ param consumption{Resources,Items}>=0; /* the consumption of resource by item */ param profit{Items}>=0; /* array the value of each item */ /* Decision variables */ /* variable */ var choose{Items} >=0 binary; /* Objective function */ maximize Value: sum{j in Items} profit[j]*choose[j];

/* Constraints */ s.t. ResourceConstraints{i in Resources}: sum{j in Items} consumption[i,j]*choose[j] <= capaci solve; display{j in Items: choose[j]=1} choose[j];

Solve the above model (knapsack.mod) in glpsol. glpsol --model knapsack.mod

Dynamic Lot Sizing with Backorders (DLS)

Example 7: We are given T periods. For period t , t = 1, . . . , T let dt be the demand in period t , dt 0. We wish to meet prescribed demand dt for each of T periods t = 1, . . . , T by either producing an amount xt up to ut ( the production capacity limit on xt ) in period t and/or by drawing upon the inventory It 1 carried from the previous period. Furthermore, we might not fully satisfy the demand of any period from the production in that period or from current inventory, but could fulll the demand from production in future periods - we permit backordering. The costs of carrying one unit of inventory from period t to period t + 1 is given by ctI 0 and the costs of backordering one unit from period t + 1 to period t is given by ctB 0. The unit production cost in period t is ct . We assume that the total production capacity is at least as large as the total demand. So, we wish to nd a production plan xt , t = 1, . . . , T , that minimizes the total cost of production, storage and backordering subject to the conditions of satisfying each demand.

DLS - a model
The Dynamic lot sizing with backorders can be formulated as follows:
T t =1 (ct xt

+ ctI It + ctB Bt ) min

t

Bt It = j =1 (dj xj ), xt ut , xt , Bt , It 0, Decision variables: xt - production amount in period t ,

t = 1, . . . , T , t = 1, . . . , T , t = 1, . . . , T .

It - inventory amount carried from period t to period t + 1, Bt - backordering amount carried from period t + 1 to period t .

DLS - implementation (lotsizing.mod)

/* input data */ param T, integer,>=1; # number of periods set Periods:={1..T}; # set of Periods param cI{Periods} >=0; # costs of carrying one unit of inventory param cB{Periods} >=0; # costs of backordering one unit param c{Periods} >=0; # unit production costs param u{Periods}>=0; # the production capacity limits param d{Periods}>=0; # demands /* Checking the total production capacity is at least as large as the total demand*/ check sum{t in Periods} d[t]<= sum{t in Periods} u[t]; var x{t in Periods}>=0,<=u[t]; # production plan var I{Periods}>=0; #inventory amount var B{Periods}>=0; # backordering amount minimize TotalCost: sum{t in Periods} (c[t]*x[t]+cI[t]*I[t]+cB[t]*B[t]); s.t. balance{t in Periods}: B[t]-I[t]=sum{j in Periods : j<=t}(d[j]-x[j]); solve; /* Displaying results */ display production plan; display {t in Periods}: x[t]; display total cost=, sum{t in Periods} (c[t]*x[t]+cI[t]*I[t]+cB[t]*B[t]); display {t in Periods}: I[t]; display {t in Periods}: B[t];

Exercise: Provide a separated data le and solve the problem.

DLS, a positive initial inventory (lotsizing1.mod)

If initial inventory is positive I0 , then one can append period 0 and assign x0 = I0 and d0 = 0 with zero inventory cost.
param InitInvent>=0, default 0; # initial inventory param T, integer,>=1; # number of periods /* Adding period 0*/ set Periods:=if InitInvent =0 then {1..T} else {0} union {1..T}; param cI{t in Periods}>=0; # costs of carrying one unit of inventory param cB{Periods}>=0; # costs of backordering one unit param c{Periods}>=0; # unit production costs param u{Periods}>=0; # the production capacity limits param d{Periods}>=0; # demands /* input data with period 0 */ param c0I{t in Periods}:=if t=0 then 0 else cI[t]; param c0B{t in Periods}:=if t=0 then 0 else cB[t]; param c0{t in Periods}:=if t=0 then 0 else c[t]; param u0{t in Periods}:=if t=0 then InitInvent else u[t]; param d0{t in Periods}:=if t=0 then 0 else d[t]; /* Assigning x_0 = I_0 */ var x{t in Periods} >=(if t=0 then InitInvent else 0), <=u0[t]; # production plan var I{Periods}>=0; #inventory amount var B{Periods}>=0; # backordering amount minimize TotalCost: sum{t in Periods} (c0[t]*x[t]+c0I[t]*I[t]+c0B[t]*B[t]); s.t. balance{t in Periods}: B[t]-I[t]=sum{j in Periods : j<=t}(d0[j]-x[j]);

The minimum cost ow problem

Example 8: Consider the problem of shipment of a commodity through a network in order to satisfy demands at certain nodes V3 from available supplies at other nodes V1 . For each i V1 supply ai is given, for each i V3 demand bi is given. Each arc (i , j ) has an associated cost cij that denotes the cost per unit ow on that arc. A capacity uij is also associated with each arc (i , j ) that denotes the maximum amount that can ow on the arc. The problem consists in nding a least cost ow. Given a network G = (V , A), V = {1, . . . , n}. The set of nodes V is partitioned into V1 (sources - supply nodes), V2 (transshipment nodes), V3 (sinks - demand nodes). For every i V the following sets are dened S (i ) = {j | (i , j ) A} and P (i ) = {j | (j , i ) A} cij xij min
(i ,j )A

xij
j S (i ) j P (i )

xji =

ai 0 bi

i V1 , i V2 , i V3 ,

0 xij uij , (i , j ) A.

The minimum cost ow problem - an implementation

param n, integer, >= 2; #the number of nodes set V:={1..n}; # the set of nodes set V1 within V; # sources - supply nodes set V3 within V; # sinks - demand nodes set V2:=V diff V1 diff V3; # transshipment nodes check: (V1 inter V3) within {}; # check if V1 and V3 are disjoint sets set A within V cross V; # the set of arcs set S{i in V}:={j in V: (i,j) in A}; # the set of direct successors of i set P{i in V}:={j in V: (j,i) in A}; # the set of direct predecessors of i param a{V1}>=0; # the supplies param b{V3}>=0; # the demands check sum{i in V1} a[i] = sum{i in V3} b[i]; # check if the problem is balanced param c{A}>= 0; # the arc costs param u{A}>= 0; # the capacities of arcs var x{(i,j) in A}>= 0, <= u[i,j]; # the flow on arc (i,j) minimize Cost: sum{(i,j) in A} c[i,j]*x[i,j]; s.t. supplies{i in V1}:sum{j in S[i]} x[i,j]-sum{j in P[i]}x[j,i]=a[i]; s.t. trans{i in V2}: sum{j in S[i]} x[i,j]-sum{j in P[i]}x[j,i]=0; s.t. demands{i in V3}: sum{j in S[i]} x[i,j]-sum{j in P[i]}x[j,i]=-b[i]; solve;

glpsol --model mincostflow.mod

The minimum cost ow problem - an implementation

Sets:
set V1 within V; the declaration of set V1 such that V1 V set V2:=V diff V1 diff V3; the declaration of set V2 of the form V \ V1 \ V3 set A within V cross V; the declaration of set A such that A V V (the subset of the Cartesian product) set S{i in V}:={j in V: (i,j) in A}; S (i ) = {j V | (i , j ) A } set P{i in V}:={j in V: (j,i) in A}; P (i ) = {j V | (j , i ) A}

Checking a value of logical expression:

check: (V1 inter V3) within {}; test: V1 V3 = ; if test fail the model translator reports error check sum{i in V1} a[i] = sum{i in V3} b[i]; test: i V1 ai = i V3 bi

The shortest path problem - a model

Example 9: We are given G = (V , A) with distinguished nodes s and t , s, t V . A nonnegative cost cij is given for each arc (i , j ) A. We wish to nd a path from s to t whose total cost is minimal. It is sufcient to set V1 = {s}, V3 = {t }, a1 = 1, bn = 1, uij = 1 for (i , j ) A in the model of the minimum cost ow problem (see Example 6) and so: cij xij min
(i ,j )A

xij
j S (i ) j P (i )

xji =

1 0 1

i = s, i = s, i = t , i = t,

0 xij 1, (i , j ) A.

The shortest path problem - an implementation

param n, integer, >= 2; # the number of nodes set V:={1..n}; # the set of nodes set A within V cross V; # the set of arcs param c{(i,j) in A} >= 0; # cij the cost of arc (i,j) param s in V, default 1; # source s param t in V, != s, default n; # sink t var x{(i,j) in A}, >= 0, <= 1; /* x[i,j] =1 if arc belongs to the shortest path, 0 otherwise*/ minimize Cost: sum{(i,j) in A} c[i,j]*x[i,j]; s.t. node{i in V}: sum{(j,i) in A} x[j,i] + (if i = s then 1)= sum{(i,j) in A} x[i,j] + (if i = t then 1);

glpsol --model path.mod

The shortest path problem - randomly generated costs

Example 10: We construct an acyclic and complete graph G = (V , A), with arc costs cij , (i , j ) A, randomly generated from interval [a, b].
param n, integer, >= 2; # the number of nodes set V :={1..n}; # the set of nodes set A:={i in V, j in V:i<j}; /* the set of arcs in the complete acyclic graph*/ param a >=0; param b, >a; /* the interval of costs */ param c{(i,j) in A}, >= 0 :=Uniform(a,b); # cij the cost of arc (i,j) /* the costs are randomly generated according to uniform distribution */ /* The rest is the same as in Example 7 */

glpsol --model path1.mod --data path1.dat

The ow shop problem

Example 11: Given m different items that are to be routed through n machines. Each item must be processed rst on machine 1, then on machine 2, and nally on machine n. The sequence of items may differ for each machine. Assume that the times pij required to perform the work on item i by machine j are known. Our objective is to minimize the total time necessary to process all the items called makespan.

The ow shop problem...

The ow shop problem can modeled as follows: ms min precedence constraints: ti ,j +1 tij + pij resource constraints: tij + Byjik tjk + pkj tkj + B (1 yjik ) tij + pij tin + pin ms tij 0 yjik {0, 1} j = 1, . . . , n, i = 1, . . . , m 1, k = i + 1, . . . , m j = 1, . . . , n, i = 1, . . . , m 1, k = i + 1, . . . , m i = 1, . . . , m i = 1, . . . , m, j = 1, . . . , n j = 1, . . . , n, i = 1, . . . , m 1, k = i + 1, . . . , m i = 1, . . . , m, j = 1, . . . , n 1

Decision variables: tij is the earliest starting time of processing item i on machine j , yjik = 1 if and only if on machine j item i is processed before item k , ms is the makespan. B is a big number, for instance: B = 1 +
m i n j =1

pij .

The ow shop problem...

Exercise: Implement the ow shop problem in GNU MathProg and solve it by glpk for the following data:
data; param n:=3; # the number of machine param m:=7; # the number of items /* the times p_ij required to perform the work on item i by machine j */ param p: 1 2 3:= 1 3 3 2 2 9 3 8 3 9 8 5 4 4 8 4 5 6 10 3 6 6 3 1 7 7 10 3; end;

Exercises
Exercise 1: Generalize the model presented in Example 1 to m constraints and n variables. Isolate the model from data. Input data: n, m, A Rmn (the constraint matrix), b Rm (the right hand side vector), c Rn (the vector of objective function coefcients) Solve the model with the data provided in Example 1. Exercise 2:(C.H. Papadimitriou, K. Steiglitz, 1998). Consider the problem faced by a homemaker when buying food to meet certain nutritional requirements. He has a set of different kinds of foods F (for example F = {potato, carrot, bread, butter, apple}) and a set of nutrients N (for example N = {vitamin A, vitamin B, vitamin C}. Each food from F has some of each nutrient from N . Namely, he has some information about amount aij of i -th nutrient, i N , in a unit of the j -th food, j F . The requirements of i -th nutrient are given by ri , i N . The cost per unit of the j -th food is cj , j F . The homemaker has to decide how many units of each food to buy in order to satisfy the nutritional requirements. Formulate a linear programming model for nding the least expensive diet (which foods to buy) and implement in GNU MathProg and solve it for a sample data by glpk. The model must isolated from data. Hint : See Example 3.

Exercises
Exercise 3: (The constrained shortest path) Given a directed graph G = (V , A) with distinguished nodes s and t , s, t V and cost cij , length lij for each arc (i , j ) A and length L. We wish to nd a path from s to t whose total cost is minimal and total length is at most L. Formulate an integer programming model for nding the problem and implement in GNU MathProg and solve it for a sample data by glpk. The model must isolated from data. Hint : Modify Example 9. Exercise 4: Scheduling a set of jobs on identical parallel machines to minimize the makespan is one of the basic and most extensively studied scheduling problems . We are given a set of jobs J = {1, . . . , n} which must be processed on m identical machines M1 , . . . , Mm . Each machine can process at most one job at a time. Each job i J has a processing time pi . We wish to assign each job to exactly one machine so that the maximum job completion time of the resulting schedule, called a makespan, is minimal. Formulate an integer programming model for nding the problem and implement in GNU MathProg and solve it for a sample data by glpk. The model must isolated from data.