1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – Kuifje Apr 21 at 10:08
  • 3
    $\begingroup$ And see here for a proof. $\endgroup$ – Kuifje Apr 21 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.