# Ensure complete cycle in binary succession matrix LP [PuLP]

I have a set of orders N, for which i have to determine an optimal sequence. I wrap this decision within a binary matrix x[i][j], meaning whether i is succeeded by j.

For example

[[0 1 0 0]

[0 0 1 0]

[0 0 0 1]

[0 0 0 0]]

where the 1st row is the start (evident from its lack of preceding elements) and the 4th row is the final one scheduled.

I enforce that each element is preceded and succeeded exactly once, except for first and last. In addition, the total number of 'movements' is also constrained to N-1.

Sometimes, the model generates solutions which satisfy these constraints, but are not feasible. In such case, there exists a closed loop. For example, with N = 15, i got 0 -> 1 -> 11 -> 10 -> 5 -> 6 -> 0, which does not interact with the start or end point of the schedule.

Q: How can introduce a constraint or variable that makes sure there is a single complete cycle, where each element can and is visited exactly once? Below is sample code.


# the decision variable is a succesion matrix of i by j, i.e. whether i is followed by j
x = LpVariable.dicts("transition", (range(N), range(N)), 0, 1, cat='Binary')

# auxiliary variable to enforce a single starting point
u = LpVariable.dicts("position", range(N), 1, N)

# constraint 1: each product has exactly one sucessor
# we do not enforce this hard, since the last scheduled has no successor
for i in range(N):
prob += lpSum(x[i][j] for j in range(N)) <= 1

# constraint 2: each product is preceded by exactly one other
# we do not enforce this hard, since the first one does not have a predecessor
for j in range(N):
prob += lpSum(x[i][j] for i in range(N)) <= 1

# constraint 3: the total number of movements is at max N-1
# this means every productis selected once, except the start product
prob += lpSum(x[i][j] for i in range(N) for j in range(N)) == N - 1

# constraint 4: avoid circular dependencies, i.e. 1 -> 2 -> 1 is not allowed
for i in range(N):
for j in range(N):
if i != j:
prob += x[i][j] + x[j][i] <= 1

# constraint 5: a product cannot be succeeded by itself
# diagonal axis of x is 0
for i in range(N):
for j in range(N):
if i == j:
prob += x[i][j] == 0

# constraint 6: ensure that there is only one starting point
for i in range(N):
for j in range(1,N):
if i != j:
prob += u[i] - u[j] + N * x[i][j] <= N - 1

# constraint 7: the start product has no predecessor
prob+= lpSum(x[i][zero_j] for i in range(N)) == 0

# constraint 8: the start product must have a successor
prob+= lpSum(x[zero_j][j] for j in range(N)) == 1

$$$$

• It seems you are looking for a permutation which is exactly what one would do in a TSP. So why not use any of the popular TPS approaches, the most popular ones (usually also based on the complete-graph where edges are boolean-variables) being MTZ Formulation or on-demand subtour-elimination (e.g. using lazy constraints like in this example). Not sure if the latter is well-supported in pulp (i doubt it). Dec 15, 2023 at 12:19

I think i resolved this by introducing a new variable p_i, i.e. position i. This denotes the position of the assignment in the sequence. I used the following constraints

    # constraint 10: positional constraint
# if i is in the sequence, its position must be smaller than j if j is present
for i in range(N):
for j in range(N):
if i != j:
prob += p[i] +1 <= p[j] + M * (1-x[i][j])

# constraint 11: positional constraint
# i and j cannot have the same position
for i in range(N):
for j in range(N):
if i != j:
prob += p[i] != p[j]

# constraint 12
# the sum of assigned positions should be equal to the sum of range N
# i.e. each position is present once
prob += lpSum(p[i] for i in range(N)) == sum_n


• Note that the !=` operator is not supported by PuLP. But if you define the right amount of position variables, and the right value for $M$, you can remove constraint 11 (as well as constraint 12). Dec 15, 2023 at 12:49
• In addition to @Kuifje's comment: you can bound your variables and remove constraint 12 as well: If you define $p_i$ as the position of order $i$ in the sequence, then you know that $1\leq p_i\leq N$. Given that you have $x_{ij}=1\Rightarrow p_i+1\leq p_j$ you will have $p_i\neq p_j$ for $i\neq j$ and thereby automatically $\sum_{i=1}^Np_i=((N+1)N)/2$
– Sune
Dec 15, 2023 at 12:57
• @Kuifje in that case, isn't my decision variable u and constraint 6 also not redudant? Since by constraint 10 & 12, i ensure j has a predecessor, and the sum of positions is equal to sum_n, therefore there can be only start position? Dec 15, 2023 at 12:58
• your variables $p$ and $u$ should be the same. you should remove variables $p$ and fix your constraints with variables $u$. Dec 15, 2023 at 13:43