Description
In this assignment, we will solve some real-world problems using
Linear Programming (https://en.wikipedia.org/wiki/Linear_programming) and
Integer Programming (https://en.wikipedia.org/wiki/Integer_programming).
We are going to use the opensource library GLPK (GNU Linear Programming Kit,
https://www.gnu.org/software/glpk/) for solving the optimization problem.
In this assignment we are going to solve the
Optimal Transport problem (https://en.wikipedia.org/wiki/Transportation_theory_(mathematics)) and
Facility location problem (https://en.wikipedia.org/wiki/Facility_location_problem).
Task 1
Consider that an army has located its units in � locations and has to supply soldiers to � battlegrounds. The cost
of supplying one soldier to from unit � to battleground �, is �&’. Also, there is a demand of at least �’ soldiers in
battleground �, and there is an upper bound of �& on the total number of soldiers who can be accommodated at
unit location �. The task is to find the optimal fraction of demand for soldiers �’ to be met by the unit location �,
denoted as �&’. This can be obtained by solving the linear program:
min
./0
11�&’ ∗ �’ ∗ �&’
3
’45
6
&45
���.��.1 �’�&’
3
’45
≤ �& ∀� = 1, … , �
1 �&’
6
&45
≥ 1 ∀� = 1, … , �
�&’ ∈ [0,1] ∀�,�
Here, the objective function measures total cost of transporting all soldiers. Note that, �’ ∗ �&’ are the number of
soldiers supplied from location � to battleground �. The first set of constraints ensures that not more than �&
soldiers are supplied from location �, and the second set of constraints ensure that at least �’ soldiers are supplied
to battleground �.
Input:
The input file format is:
…
Output:
Print input data: values of n and m, u vector, d vector, and c matrix.
Print the matrix of optimal allocation of soldiers from unit location I to battleground j: �’ ∗ �&’
Task 2:
Consider the problem of locating army units in at most � locations (facility points) for servicing the needs of
�battle grounds (demand points). Each facility point � has a cost of �&’ of supplying the demand point �, this
could be the cost of transporting one soldier to from unit location � to battleground �. Each battleground � has a
demand for �’ soldiers, assumed to be known. Moreover, each facility � has an initial fixed cost of �& of setting
up, and an upper bound �& on the demand for number of soldiers which can be accommodated. Let us say we
want to open � of the � facilities. The problem is to find out the optimal fraction �&’ of the soldiers �’ which will
be supplied by facility location � to battleground �. Additionally, we must find out which of the � locations should
be used to set up unit facilities, maximum number of them being �. This can be solved using a mixed integer
linear programming problem. Let �& be a binary integer variable denoting whether facility location � should be
opened (�& = 1) or not (�& = 0). The optimization problem becomes:
min
./0
11�&’ ∗ �’ ∗ �&’
3
’45
6
&45
+1�& ∗ �&
6
&45
���.��.1 �’�&’
3
’45
≤ �&�& ∀� = 1, … , �
1 �&’
6
&45
≥ 1 ∀� = 1, … , �
1�&
6
&45
≤ k
�&’ ∈ [0,1] ∀�,�
�& ∈ {0,1} ∀�
Here, the objective function measures total cost of transporting all soldiers (first term) and the total setup cost of
all open facilities (second term). Note that, �’ ∗ �&’ are the number of soldiers supplied from location � to
battleground �. If location � is not open (�& = 0) the upper bound is 0, otherwise it is �&. The first set of constraints
ensures that not more than �& soldiers are supplied from location �, and the second set of constraints ensure that
at least �’ soldiers are supplied to battleground �. Here, �& are integral binary variables.
Input:
The input file format is:
…
Output:
Print input data: values of n and m, u vector, f vector, d vector, and c matrix.
Print the list of opened facilities: y vector.
Print the matrix of optimal allocation of soldiers from unit location I to battleground j: �’ ∗ �&’
GLPK Guide:
Get yourself introduced to the GLPK API. If you want to install it in your personal machine (like laptop), you
need to download the package from the standard repositories (http://ftp.gnu.org/gnu/glpk/) and compiling it from
source. For Ubuntu, pre-built binaries can be installed using:
$ sudo apt install glpk-utils libglpk-dev glpk-doc
Read the user’s manual from (https://cse.iitkgp.ac.in/~abhij/course/lab/CompLab-I/Autumn19/glpk.pdf). Include
the following directive in your program.
#include
Compile your code with the following flags.
gcc -Wall glpkdemo.c -lglpk -lm
GLPK supports both real-valued linear programming and mixed-integer optimization. The basic API calls
are glp_simplex and glp_intopt. The integer optimizer needs an initial solution. You can start with the
output of the simplex solver.