CODEWITHSUNDEEP
pythonpulp
Zufra
Zufra

Reputation: 646

Pulp Integer Programming Constraint ignored

I am trying to solve a LpProblem with only boolean variables and Pulp seems to be ignoring some constraints. To give some context about the problem:

I want to find an optimal solution to the problem schools face when trying to create classroom groups. In this case, students are given a paper to write at most 5 other students and the school guarantees them that they will be together with at least one of those students. To see how I modeled this problem into an integer programming problem please refer to this question.

In that link you will see that my variables are defined as x_ij = 1 if student i will be together with student j, and x_i_j = 0 otherwise. Also, in that link I ask about the constraint that I am having trouble implementing with Pulp: if x_i_j = 1 and x_j_k = 1, then by transitive property, x_i_k = 1. In other words, if student i is with student j, and student j is with student k, then, student i will inherently be together with student k.

My objective is to maximize the sum of all the elements of the matrix obtained when performing a Hadamard product between the input matrix and the variables matrix. In other words, I want to contemplate as many of the student's requests as possible.

I will now provide some code snippets and screen captures that should help visualize the problem:

Inputs (just a sample: the real matrix is 37x37)

enter image description here

Output

enter image description here

As you can see in this last image, x_27 = 1 and x_37 = 1 but x_23 = 0 which doesn't make sense.

Here is how I define my variables

def define_variables():
  variables = []
  for i in range(AMOUNT_OF_STUDENTS):
    row = []
    for j in range(AMOUNT_OF_STUDENTS):
      row.append(LpVariable(f"x_{i}_{j}", lowBound=0, upBound=1, cat='Integer'))
    variables.append(row)
  return variables

Here is how I define the transitive constraints

    for i in range(len(variables)):
      for j in range(i, len(variables)):
        if i != j:
          problem += variables[i][j] == variables[j][i]   # Symmetry
        for k in range(j, len(variables)):
          if i < j < k < len(variables):
            problem += variables[i][j] + variables[j][k] - variables[i][k] <= 1 # Transitive
            problem += variables[i][j] + variables[i][k] - variables[j][k] <= 1
            problem += variables[j][k] + variables[i][k] - variables[i][j] <= 1

When printing the LpProblem I see the constraint that is apparently not working: enter image description here

As you can see in the output: x_2_7 = 1 and x_3_7 = 1. Therefore, to satisfy this constraint, x_2_3 should also be 1, but as you can also see in the output, it is 0.

Any ideas about what could be happening? I've been stuck for days and the problem seems to be modeled fine and it worked when I only had 8 students (64 variables). Now that I have 37 students (1369 variables) it seems to be behaving oddly. The solver arrives to a solution but it seems to be ignoring some constraints.

Any help is very much appreciated! Thank you in advance.

Upvotes: 0

Views: 1518

Answers (2)

pchtsp
pchtsp

Reputation: 864

The constraint is working correctly. Find below the analysis: (crossposted from github: https://github.com/coin-or/pulp/issues/377)

import pulp as pl
import pytups as pt

path = 'debugSolution.txt'

# import model
_vars, prob = pl.LpProblem.from_json(path)

# get all variables with non-zero value
vars_value = pt.SuperDict(_vars).vfilter(pl.value)

# export the lp
prob.writeLP('debugSolution.lp')

# the constraint you show in the SO problem is:
# _C3833: - x_2_3 + x_2_7 + x_3_7 <= 1

'x_2_7' in vars_value
# True, so x_2_7 has value 1

'x_3_7' in vars_value
# False, so x_3_7 has value 0

'x_2_3' in vars_value
# False, so x_2_3 has value 0

So -0 + 1 + 0 <= 1 means the constraint is respected. There must be a problem with bringing back the value of x_3_7 somewhere because you think is 1 when in pulp it's 0.

Upvotes: 1

foglerit
foglerit

Reputation: 8269

This is called a set partitioning problem and PuLP has an example in their documentation here.

In essence, instead of modeling your variables as indicators of whether student A is in the same class as student B, you'll define a mapping between a set of students and a set of classrooms. You can then apply your student preferences as either constraints or part of a maximization objective.

Upvotes: 1

Related Questions