Pulp Integer Programming Constraint ignored

Question

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)

Output

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:

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.

Also, in your solution x_27 != x_72.What is the status of the solver when you get the solution? — abc
– abc, Commented Dec 28, 2020 at 0:57
Hadn't noticed that. Another constraint ignored. What do you mean by status? The solver says it found an optimal solution. However, before finding the solution, it outputs in the console that it reduces the amount of rows and columns of the problem several times. I don't know exactly what this means. I assumed that it ignores redundant constraints/variables. — Zufra
– Zufra, Commented Dec 28, 2020 at 12:18

pchtsp · Accepted Answer · 2020-12-29 21:48:23Z

1

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.

answered Dec 29, 2020 at 21:48

pchtsp

8741 gold badge7 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Zufra Over a year ago

You are right. The problem was when reading the variables values, as stated here: github.com/coin-or/pulp/issues/377. Thank you @pchtsp!

foglerit · Accepted Answer · 2020-12-28 14:19:30Z

1

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.

answered Dec 28, 2020 at 14:19

foglerit

8,4469 gold badges52 silver badges70 bronze badges

1 Comment

Zufra Over a year ago

Thanks for your answer @foglerit, I'll read the documentation you referenced and make the necessary changes to my code. Still, it is weird that with my way of doing it Pulp ignores certain constraints even though they are correctly defined.

Collectives™ on Stack Overflow

Pulp Integer Programming Constraint ignored

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related