Simplex (GLPK) doesn't find a feasible solution on this simple assignment problem, but there is an obvious one

Question

Problem

Assign 11 projects to 11 students, based on their preference.

For this example, each students chooses only one project, for simplicity shake (as shown below). Student 1 one chooses project 1, students 2 chooses project 2 etc. Obviously there is a feasible solution!

students/projects       1 2 3 4 5 6 7 8 9 10 11
                    1   9 0 0 0 0 0 0 0 0 0 0
                    2   0 9 0 0 0 0 0 0 0 0 0
                    3   0 0 9 0 0 0 0 0 0 0 0
                    4   0 0 0 9 0 0 0 0 0 0 0
                    5   0 0 0 0 9 0 0 0 0 0 0
                    6   0 0 0 0 0 9 0 0 0 0 0
                    7   0 0 0 0 0 0 9 0 0 0 0
                    8   0 0 0 0 0 0 0 9 0 0 0
                    9   0 0 0 0 0 0 0 0 9 0 0
                    10  0 0 0 0 0 0 0 0 0 9 0
                    11  0 0 0 0 0 0 0 0 0 0 9

The problem is that glpk does not find it! I'll demonstrate the modeling of the problem and the code below.

---

Modeling

This is a maxmin problem

Decision Variables

$ x_{ij} =\left\{ \begin{array}{@{}ll@{}} 0, & \text{project j not assigned to student i}\\\ 1, & \text{otherwise} \end{array}\right. $

$p_{ij}:$ The "profit" of assigning project $j$ to student $i$

$P$: The minimum profit on bilateral matching

Constraints

Every project is assigned to only one student: $\sum_{i=1}^{11} x_{ij} = 1$

Each student gets only one problem: $\sum_{j=1}^{11} x_{ij} = 1$

Assign a project to a student, only if her chose it (upper bound): $P \leq x_{ij} \cdot p_{ij} + A \cdot (1-x_{ij})$ (Where A is a big constant)

Objective Function

Maximize P

---

GLPK code

/* number of students */
param m, integer, > 0;

/* number of projects */
param n, integer, > 0;

/* set of students */
set I := 1..m;

/* set of projects */
set J := 1..n;

/* profit of allocating project j to student i */
param p{i in I, j in J}, >= 0;

/* Binary assignment variable */
var x{i in I, j in J}, = 0;

/* Minimum profit of allocating project j to student i */
var P, >= 0; 

/* each student must perform exactly one project */
s.t. con1{i in I}: sum{j in J} x[i,j] = 1;

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

/* Upper bound */
s.t. con3{j in J, i in I}: P <=  x[i,j] * p[i,j]  + 9999999 * (1 - x[i,j]);  

maximize obj: P;

solve;

printf "\n";
printf "student  project       profit\n";
printf{i in I} "%5d %5d %10g\n", i, sum{j in J} j * x[i,j],
   sum{j in J} p[i,j] * x[i,j];
printf "----------------------\n";
printf "     Total: %10g\n", sum{i in I, j in J} p[i,j] * x[i,j];
printf "\n";

data;

param m := 11;

param n := 11;

param p : 1 2 3 4 5 6 7 8 9 10 11:=
      1   9 0 0 0 0 0 0 0 0 0 0
      2   0 9 0 0 0 0 0 0 0 0 0
      3   0 0 9 0 0 0 0 0 0 0 0
      4   0 0 0 9 0 0 0 0 0 0 0
      5   0 0 0 0 9 0 0 0 0 0 0
      6   0 0 0 0 0 9 0 0 0 0 0
      7   0 0 0 0 0 0 9 0 0 0 0
      8   0 0 0 0 0 0 0 9 0 0 0
      9   0 0 0 0 0 0 0 0 9 0 0
      10  0 0 0 0 0 0 0 0 0 9 0
      11  0 0 0 0 0 0 0 0 0 0 9 ;
end;

The question

GLPK doesn't seem to find a solution. But there is obviously one. What went wrong?

user@ubuntu:~$ glpsol -m assign.mod 
GLPSOL: GLPK LP/MIP Solver, v4.65
Parameter(s) specified in the command line:
 -m assign.mod
Reading model section from assign.mod...
Reading data section from assign.mod...
61 lines were read
Generating con1...
Generating con2...
Generating con3...
Generating obj...
Model has been successfully generated
GLPK Simplex Optimizer, v4.65
144 rows, 122 columns, 485 non-zeros
Preprocessing...
PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION
Time used:   0.0 secs
Memory used: 0.3 Mb (295915 bytes)

P.S: I know this can be easily solved with Hungarian algorithm. But using hungarian I cannot add the P constraint, where I ask the program to assign a project to a student only if he chose it.

Answer 1

Maybe the unnecessarily large value for $A$ is causing numerical trouble. Try instead $A = \max_{i,j} p_{i,j} = 9$.

Probably your $=0$ in the declaration of $x$ should be $\ge 0$. In fact, you generally need to declare $x$ to be binary when you include side constraints.