# Using GLPK to solve knapsack and related problems

I am taking a course in Supply Chain management from Edx. The transport-network problem in the Supply chain management domain maps directly with the network flow problem. The course recommends using Excel to formulate and solve the model problems. I never had a knack for Excel and while I find it useful for some use cases, I prefer programming using a text editor. I would rather work out numeric problems with R or Python than write formulae and values in cells in Excel. I was looking for an open source alternative to formulate and solve the network flow problems so that I can avoid the drudgery of dealing with Excel spreadsheets.

I came across the `glpk` library for solving linear programs such as Network flow problems. GLPK uses MathProg as its programming language. You specify your variables, objective function, and constraints in MathProg, run the `glpsol` command providing the MathProg file as an input, and the solver outputs a solution if the solution exists. The constraints and the objective function are specified using a math-like notation for inequalities. Here is a sample MathProg specification ::

``````  set Items;
param weight{t in Items};
param value{t in Items};
param quantity{t in Items};

var take{t in Items}, integer, >=0, <=quantity[t];
maximize knap_value: sum{t in Items} take[t] * value[t];
s.t. knap_weight : sum{t in Items} take[t] * weight[t] <= 25;
s.t. knap_vol    : sum{t in Items} take[t] * volume[t] <= 0.25;

``````

This is a specification for a knapsack problem. We are maximizing the value of the items in the knapsack subject to the constraint the total weight does exceed 400. The expression `knap_value` is the objective function which is the value of the items. The expression `knap_weight` is the constraint.

Next, we’ll need to provide the `.dat` file as data. We can structure the file like so:

``````data;

param : Items   : weight   value     volume :=
A      0.3        3000      0.025
B      0.2	       1800	     0.015
C		  2.0	       2500      0.002
;
end;

``````

We can solve the Knapsack problem like so:

``````    glpsol --model knapsack.mod --data knapsack.dat -o result
``````

The file `result` produced as a result of the `glpsol` command will have the details about the solution, if a solution exists.