↓Skip to main content
  1. Posts/

Using GLPK to solve knapsack and related problems

·2 mins

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.

[1] http://rosettacode.org/wiki/Knapsack_problem/Bounded#Mathprog