0
$\begingroup$

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


```
$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – sascha
    Dec 15, 2023 at 12:19

1 Answer 1

0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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). $\endgroup$
    – Kuifje
    Dec 15, 2023 at 12:49
  • $\begingroup$ 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$ $\endgroup$
    – Sune
    Dec 15, 2023 at 12:57
  • $\begingroup$ @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? $\endgroup$ Dec 15, 2023 at 12:58
  • $\begingroup$ your variables $p$ and $u$ should be the same. you should remove variables $p$ and fix your constraints with variables $u$. $\endgroup$
    – Kuifje
    Dec 15, 2023 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.