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:
./0 𝑥&’
&
𝑠𝑢𝑏. 𝑡𝑜. 1 𝑑’𝑥&’ , … , 𝑛
’45
6
1 𝑥&’ , … , 𝑚
&45
𝑥&’ ∈ [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:
<value of n> <value of m>
<vector of 𝑢& (n numbers in one line)> <vector of 𝑑’ (m numbers in one line)>
<first row of cost matrix 𝑐&’ (m numbers in one line)>
…
<last (nth) row of cost matrix 𝑐&’ (m numbers in one line)>
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:
6 3 6
min./0 1 1 𝑐&’ ∗ 𝑑’ ∗ 𝑥&’ + 1 𝑓& ∗ 𝑦&
& &45
𝑠𝑢𝑏. 𝑡𝑜. 1 𝑑’𝑥&’ ≤ 𝑢&𝑦& ∀𝑖 = 1, … , 𝑛
’45
𝑥&’ , … , 𝑚
1 𝑦& ≤ k
&45
𝑥&’ ∈ [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:
<value of n> <value of m>
<vector of 𝑢& (n numbers in one line)>
<vector of 𝑓& (n numbers in one line)>
<vector of 𝑑’ (m numbers in one line)>
<first row of cost matrix 𝑐&’ (m numbers in one line)>
…
<last (nth) row of cost matrix 𝑐&’ (m numbers in one line)>
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 <glpk.h>
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.
