# LP instead of IP formulation of assignment problem

In the example files of GLPK, the assignment problem is written as a linear program. I don't understand why this isn't an integer programming problem. The problem formulation:

minimize obj: sum{i in I, j in J} c[i,j] * x[i,j];
/* the objective is to find a cheapest assignment */

s.t. phi{i in I}: sum{j in J} x[i,j] <= 1;
/* each agent can perform at most one task */

s.t. psi{j in J}: sum{i in I} x[i,j] = 1;
/* each task must be assigned exactly to one agent */



The relevant line is here:

var x{i in I, j in J}, >= 0;
/* x[i,j] = 1 means task j is assigned to agent i
note that variables x[i,j] are binary, however, there is no need to
declare them so due to the totally unimodular constraint matrix */


When I invoke the solver it says that the LP solver was used.

glpsol --math assign.mod
...
OPTIMAL LP SOLUTION FOUND
...


The way I understand the comment is that the author of this problem says that the constraint matrix is unimodular, and hence the variables $$x_{ij}$$ will be automatically binary. Therefore we can use an LP solver instead of an IP solver. The cost matrix are positive integers, in case this is relevant:

param c : 1  2  3  4  5  6  7  8 :=
1  13 21 20 12  8 26 22 11
2  12 36 25 41 40 11  4  8
3  35 32 13 36 26 21 13 37
4  34 54  7  8 12 22 11 40
5  21  6 45 18 24 34 12 48
6  42 19 39 15 14 16 28 46
7  16 34 38  3 34 40 22 24
8  26 20  5 17 45 31 37 43 ;


What does it mean that the constraint matrix is unimodular, and why does this imply that the solution is binary? I understand the reasoning that $$0 \leq x_{ij} \leq 1$$, but why isn't $$x_{ij}$$ real?

Thank you

the full file can be found here: https://ftp.gnu.org/gnu/glpk/ by downloading glpk-5.0 and looking into examples/assign.mod.

• It can be show that for assignment problems, you can relax the integer variables to continuous ones. You are correct though, this is a special case and initially the variables should be integer. As mentioned in the "relevant part", this is because the matrix is unimodular. – Kuifje Apr 21 at 10:08
• And see here for a proof. – Kuifje Apr 21 at 12:40