$$ \min \sum_{i \in P_0} \sum_{j \in P_0, i \neq j} c_{i,j} x_{i,j} \qquad (\text{MIP}_{\text{UB}}) $$

$$ \text{s.t.} \quad \sum_{j \in P_0, i \neq j} x_{i,j} = 1 \qquad \forall i \in P \quad (4a) $$

$$ \sum_{i \in P_{N+1}, i \neq j} x_{j,i} - \sum_{i \in P_0, i \neq j} x_{i,j} = 0 \qquad \forall j \in P \quad (4b) $$

$$ t_i + x_{i,j} - |P|(1 - x_{i,j}) \leq t_j \qquad \forall i \in P_{N+1}, j \in P_{N+1}, i \neq j \quad (4c) $$

$$ s_j \leq s_i + (S_{i+n}^0 + S_j^0)x_{i,j} + |\hat{S}|(1 - x_{i,j}) \qquad \forall i \in P_0, j \in P_{N+1}, i \neq j \quad (4d) $$

$$ Ls_i + \hat{q}_i \leq K \qquad \forall i \in P_{N+1} \quad (4e) $$

$$ 1 \leq t_i \leq |P| \qquad \forall i \in P \quad (4f) $$

$$ s_i \leq \hat{S} \qquad \forall i \in P \quad (4g) $$

$$ s_i \geq \hat{\pi}_i \qquad \forall i \in P \quad (4h) $$

$$ t_0 = 0 \qquad (4i) $$

$$ \tilde{S}_0 \leq s_0 \leq \tilde{S}_0 + S_0^0 \qquad (4j) $$

$$ x_{i,j} \in \{0,1\} \qquad \forall i \in P \quad (4k) $$

$$ t_i \in \mathbb{N}, s_i \in \mathbb{N} \qquad \forall i \in P_{0,N+1} \quad (4l) $$

Figure 5 The Upper Bound MIP model for a restriction of PD-SRP.

The upper bound model is obtained by over-constraining the original problem to require that a request must be delivered immediately after being picked up. The nodes in this problem include the start depot $v_0$, the end depot $v_{N+1}$, and all the pickup nodes $P = \{v_1, \dots, v_n\}$. For modeling purposes we define sets $P_{N+1} = P \cup \{v_{N+1}\}$, $P_0 = P \cup \{v_0\}$ and $P_{0,N+1} = P \cup \{v_0, v_{N+1}\}$. The delivery nodes are not explicitly included because each origin-to-destination trip takes place immediately after the visit to the pickup node with the total distance increased by both the travel to the pickup node and the travel between the pickup node and the delivery node.

The MIP$_{UB}$ model is presented in Figure 5. Let $x_{i,j}$ be a binary variable indicating that the aircraft goes from the delivery location of the request $i$ to the pickup location of request $j$. Let $s_i$ be the number of seats in the aircraft right after visiting location $i$. Finally, let $t_i$ be the position of location $i$ on the tour. The solution returned by this model is likely to be sub-optimal for the PD-SRP.

The objective function minimizes the total distance traveled. The coefficient $c_{ij}$ represents the total distance starting from the delivery location of request $i$, visiting the pickup location of request $j$, and then travelling to the delivery locations of request $j$. Request 0 is to travel from the depot to the pickup location of the first request. The delivery and pickup locations of request 0 are nodes $v_0$ and $v_{2n+1}$, respectively.

Constraints (4a) and (4b) ensure that each node is visited exactly once. Constraints (4c), (4f), and (4i) prevent the formation of subtours. Constraint (4d) describes seat changes when the aircraft visits a node and constraint (4e) requires that the space taken up by the seats in the aircraft must be less than or equal to the remaining space after picking up the cargo of the current request. Constraint (4g) restricts the number of seats to never surpasses the maximum number of seats allowed in the aircraft and constraint (4h) ensures that the number of seats in the aircraft never drops below the number of passengers to be picked up. Constraints (4j) - (4l) specify the domains of the variables.
## 4.3 Domain-Independent Dynamic Programming Models

Domain-Independent Dynamic Programming (DIDP) is a recently proposed methodology for solving combinatorial optimization problems by formulating the problem as state-based dynamic program (DP) and using a generic solver to solve it [14]. DP models are declaratively formulated in Dynamic Programming Description Language (DyPDL), a solver-independent modeling formalism for DP that is inspired by AI planning. In DyPDL, a model consists of the following:

- **state variables**: variables that take on numeric, set, or set-element values that define the states in the search space of the problem

- **target state**: the problem state for which the optimal value is to be computed by the recursive formulation

- **constants**: state-independent values

- **transitions**: decisions in the DP that move between states

- **base cases**: a set of conditions that define states that terminate the recursion

- **state constraints**: conditions that must be satisfied by all states

- **dual bound**: an optional lower (upper) bound on the objective function for minimization (maximization) problems.

We developed two DIDP models for the PD-SRP.

### 4.3.1 A Two-transition DIDP Model ($\mathit{DIDP}_{2T}$)

Our first DIDP model has two types of transition: one to represent adding or removing seats and picking up or delivering cargo and passengers and a second to model moving the aircraft to a different location. In the model, a state is a tuple $(U, i, q, \pi, s, \alpha)$, which represents the set of unvisited vertices, $U$, the current location, $i$, the cargo load, $q$, the number of passengers, $\pi$, the number of seats, $s$, and a flag representing which type of transition to apply, $\alpha$. We set $\alpha = 1$ if we have finished pickup/delivery at a location to indicate that the next transition should be to move the aircraft. Otherwise, $\alpha = 0$.

The $\mathit{DIDP}_{2T}$ model is defined in Figure 6. We focus first on Eqs. (5c) and (5d), which respectively define the possible seat changes and possible next locations at a location $i$.

Suppose that the number of seats at the current location $i$ is increased by $\delta$. Since there are $S_i^0$ seats stored at each location initially, when the aircraft has $s$ seats, at $i$ we can add at most $\min\{S_i^0, \hat{S} - s\}$ seats and remove at most $s$ seats. For simplicity we will denote $\hat{S}_i = \min\{S_i^0, \hat{S} - s\}$. Therefore, $\delta \in [-s, \hat{S}_i]$. Let numeric constants $w_i$ and $u_i$ be the net change of cargo and passengers at location $i$, respectively. The cargo will be increased by $w_i$, so the current cargo will become $q + w_i \le K - (s + \delta)L$, the current space for cargo. Similarly, the number of passengers will be $\pi + u_i \le s + \delta$. Lastly, $\delta$ must only take integer values. With these conditions, Eq. (5c) specifies the values of $\delta$.

Consider visiting the next location, $j$, from current location $i$. To be a valid location to visit next, $j$ must be unvisited ($j \in U$), it must be connected by an edge in the graph to $i$ (($i, j) \in A$), and it must be either a pickup location ($j \notin D$) or its corresponding pickup location must have already been visited. If we let $p_j$ be the pickup location for the request whose delivery location is $j$, then this final condition is: $p_j \notin U$. Eq. (5d) represents the candidate locations to visit next after current location $i$.

The objective function specifies the state for which the optimal cost needs to be computed: the state where all pickup and delivery nodes are unvisited, the current location is the start depot ($v_0$), the cargo and passenger loads are 0, the aircraft has $\tilde{S}_0$ seats, and the next
$$ \text{compute } Z(V, 0, 0, 0, \tilde{S}_0, 0) \qquad (\text{DIDP}_{2T}) $$

$$ Z(U, i, q, \pi, s, \alpha) = \begin{cases} d_{i,2n+1} & \text{if } U = \emptyset, \alpha = 1 \\ \min_{\delta \in T(q, \pi, s, i)} Z(U, i, q + w_i, \pi + u_i, s + \delta, 1) & \text{if } U \neq \emptyset, \alpha = 0 \quad (5a) \\ \min_{j \in R(U, i)} d_{i,j} Z(U \setminus \{j\}, j, q, \pi, s, 0) & \text{if } U \neq \emptyset, \alpha = 1 \end{cases} $$
$$ Z(U, i, q, \pi, s, \alpha) \ge 0 \qquad (5b) $$

$$ T(i, q, \pi, s) = \{ \delta \in [-s, \hat{S}_i] \mid q + w_i \le K - (s + \delta)L \wedge \pi + u_i \le s + \delta, \delta \in \mathbb{Z} \} \quad (5c) $$

$$ R(U, i) = \{j \in U \mid (i, j) \in A \wedge (j \notin D \lor p_j \notin U)\}. \quad (5d) $$

**Figure 6** The Two-transition DIDP Model (DIDP<sub>2T</sub>) for PD-SRP.

$$ \text{compute } Z(V, 0, 0, 0, \tilde{S}_0) \qquad (\text{DIDP}_{1T}) $$

$$ Z(U, i, q, \pi, s) = \begin{cases} d_{i,2n+1} & \text{if } U = \emptyset \wedge \exists \delta \in T(i, q, \pi, s) \\ \min_{(\delta,j) \in T(i,q,\pi,s) \times R(U,i)} d_{i,j} + Z(U \setminus \{j\}, j, q + w_i, \pi + u_i, s + \delta) & \text{if } U \neq \emptyset \end{cases} $$
$$ Z(U, i, q, \pi, s) \ge 0 \qquad (6a) $$

Eq. (5c), Eq. (5d).

**Figure 7** The One-transition DIDP Model (DIDP<sub>1T</sub>) for PD-SRP.

transition should be to move the aircraft ($\alpha = 0$). In Eq. (5a), the first line computes the cost to return to the depot from node $i$, the second line describes the cost of adding or removing $\delta$ seats at node $i$, and the third line describes the cost of visiting node $j$ from $i$. Note that when the aircraft is moved, the state variable $\alpha$ is set to 0 and if the decision regarding seats is made in this transition, $\alpha$ is set to 1. Constraint (5b) is a dual bound for the DIDP model which is optional but may be exploited by the solver.

### 4.3.2 A One-transition DIDP Model (DIDP<sub>1T</sub>)

We present the DIDP<sub>1T</sub> model in Figure 7. In this model, instead of two types of transitions, we define one type that performs the pickup/delivery and seat exchange at a location and then moves the aircraft to a new location. A state is the same as in DIDP<sub>1T</sub> with the exception of the $\alpha$ flag which is no longer necessary: $\langle U, i, q, \pi, s \rangle$. As a transition first picks up or delivers cargo, passengers, and seats at the current location and then moves the aircraft to the next location, each transition corresponds to selecting $(\delta, j)$: $\delta$ is the number of picked up seats and $j$ is the next location to visit. The set of possible decisions at each state is therefore $T(i, q, \pi, s) \times R(U, i)$ as defined in the second line of Eq. (6a).

The objective function of DIDP<sub>1T</sub> defines the state for which the optimal cost is to be calculated. It is identical to the target state in DIDP<sub>2T</sub> with the removal of $\alpha$. In Eq. (6a), the first line describes the cost of returning to the depot from node $i$, and the second line describes the cost of visiting node $j$ from $i$. Note that the first line checks if there exists some $\delta$ such that the capacity constraints on the cargo and the passengers are satisfied. If there is no such $\delta$, we assume $Z(\emptyset, i, q, \pi, s) = \infty$.
### 4.3.3 Model Sizes and Solver

In a DIDP model, we need to define all transitions that are applicable in a state. In $DIDP_{2T}$, $\delta$ can take an integer in $[-\hat{S}, \hat{S}]$ depending on a state, so there are $2\hat{S} + 1$ candidates. We have $|V_{N+1}|$ locations to visit. Thus, $DIDP_{2T}$ requires $2\hat{S} + 1 + |V_{N+1}|$ transitions to be defined in total. In contrast, $DIDP_{1T}$ needs to define $(2\hat{S} + 1)|V_{N+1}|$ transitions but does not have state variable $\alpha$. An alternative perspective is that the two DIDP models make different trade-offs between the maximum branching factor and solution length. $DIDP_{1T}$ has a branching factor of at most $(2\hat{S} + 1)|V_{N+1}|$ at each state and a solution path length of $|V_{N+1}|$. $DIDP_{2T}$ has a maximum branching factor that alternates between $2\hat{S} + 1$ and $|V_{N+1}|$ and a solution length of $2|V_{N+1}|$. The performance of a solver is affected by the number of state variables, the branching factor, and the solution length.

We solve the DIDP models with a complete anytime beam search (CABS) solver [25, 15]. CABS is an anytime algorithm meaning that seeks to quickly find a feasible solution and then to improve it in the remaining run-time. CABS employs beam search: a heuristic search algorithm that maintains a fixed number, $b$ (beam width), of best states when exploring the search space. In CABS, beam search is performed iteratively with increasing the beam width until a stopping condition is met. Due to the iteratively increasing beam width, CABS is a complete algorithm [25].

## 5 Numerical Evaluation

### 5.1 Experimental Setup

We have developed six different models, i.e., CP, $MIP_{loc}$, $MIP_{rank}$, $MIP_{UB}$, $DIDP_{1T}$, $DIDP_{2T}$. For the experiment, we use $MIP_{UB}$ to warm-start the MIP and CP models, producing three additional approaches: $MIP_{loc\_W}$, $MIP_{rank\_W}$ and $CP_W$.

To implement and solve the models we used Python v3.8.0 and the corresponding Python interfaces to the solvers: Gurobi Optimizer 10.0.1 and gurobipy for MIP, CP Optimizer 22.1.0.0 and DOCPlex for CP, and didppy 0.3.3 for DIDP.<fnref n="1" /> Each run has a time limit of 600s. The machine used to run the experiment has Intel(R) Core(TM) i7-9700 8 core CPU @ 3.00GHz, 12MB cache, and memory of 31G.

The models are tested on randomly generated instances with sizes 4, 6, 8, 10, 12, 15, and 20 with 10 instances per size. The size of each instance is the number of requests, which is half of the number of locations. We generate problem instances randomly, approximately reflecting real-world problem size, aircraft capacity and configurations, and stored seats at each location. We fix the maximum number of seats in the aircraft $\hat{S} = 6$, the cargo-to-seat ratio $L = 100$, and the cargo capacity on a full-seat aircraft $\hat{C} = 200$. The number of seats in the aircraft start configuration, $\hat{S}_0$, is selected uniformly from $\{0, ..., 6\}$ and the cargo capacity in the start configuration is $\hat{C}_0 = 800 - 100\hat{S}_0$. Similarly, the number of seats available at location $i$, $S_i^0$, is set uniformly from $\{0, ..., 6\}$, independently for each location. The $(x, y)$ coordinates of every location are uniformly generated from $\{0, ..., 100\}^2$.

We generate the passenger and cargo demand to ensure the existence of capacity-feasible solutions. For each request $i \in \{1, ..., n\}$, there is a demand of $\hat{\pi}_i$ passengers and demand of $\hat{q}_i$ kg cargo (i.e., $\hat{q}_i/L$ units of cargo). We first define the total number of passengers and units of cargo as $\hat{K} = \hat{q}_i/L + \hat{\pi}_i$, and $\hat{K}$ is uniformly generated from $\{1, ..., \hat{S} + \hat{C}/L = 8\}$. The passenger request $\hat{\pi}_i$ is then selected uniformly from $\{0, ..., \min(\hat{S}, \hat{K})\}$. Consequently, the cargo request is $\hat{q}_i = L(\hat{K} - \hat{\pi}_i)$.

<footnote n="1">¹ https://didp.ai</footnote>
To compare the models, we used the number of instances solved and proved optimal, the PAR10 score time [12] (i.e., mean run-time with 10 times the time limit used if no optimal solution was proved), and mean relative error (MRE).

MRE compares the solution quality returned by each model. For an optimization problem let $obj_{t,m,i}$ be the objective value of the best solution achieved by time $t$ of model $m$ for instance $i$ and let $obj_i^*$ be the best-known objective value for that instance considering all the models. For the set of instances, $\mathcal{I}$, the relative error and mean relative error are computed in Eqs. (7) and (8). If a model did not find a feasible solution by a given time, the $MIP_{UB}$ value is used to calculate a non-infinite measure.

$$ RE(t, m, i) = \frac{obj_{t,m,i} - obj_i^*}{obj_i^*} \qquad (7) $$

$$ MRE(t, m) = \frac{1}{|\mathcal{I}|} \sum_{i \in \mathcal{I}} RE(t, m, i) \qquad (8) $$

## 5.2 Results

Figures 8a and 8b show the number of solved instances (i.e., proved infeasible or optimal) and mean PAR10 times for all the models. We do not include $MIP_{UB}$ as it is incomplete, however for each model, its run-time is less than 0.02s. The run times for $MIP_{loc_W}$, $MIP_{rank_W}$, and $CP_W$ models, include the warm-start time.

The DIDP models solved all of the instances with 12 or fewer requests, with $DIDP_{2T}$ performing slightly better than $DIDP_{1T}$ for instances of size 15 as it could solve three instances compared to none for $DIDP_{1T}$. Neither $CP$ nor $CP_W$ were able to solve any instances of size larger than 6 while the MIP models scaled up to size 10 or 12. There was one instance of size 4 that $CP_W$ could not prove optimality, but $CP$ could.

In terms of solution time, the DIDP models were the fastest and $CP$ models were the slowest. For the MIP models, $MIP_{rank_W}$ performed slightly better than $MIP_{rank}$ in terms of both the number of solved instances and mean solution time. For one instance of size 12, $MIP_{rank_W}$ proved optimality where $MIP_{rank}$ could not.

The MRE graph is shown in Figure 8c. $DIDP_{2T}$ returns the best solutions and finds those best solutions within a few 10s of seconds. Up to 300s, $CP_W$ outperformed $MIP_{rank_W}$, $MIP_{loc_W}$, $MIP_{loc}$ but after that point, their solution qualities are very similar. The solution qualities returned by $CP$ are the worst after 100 seconds. However, the use of $MIP_{UB}$ as a warm start substantially improves $CP$ quality especially for short run times. The performance of the $MIP_{loc}$ and $MIP_{loc_W}$ models was very similar, however, the $MIP_{loc_W}$ model returned slightly better solution qualities than $MIP_{loc}$, especially before 200s. As we expected, the solutions found by the incomplete $MIP_{UB}$ are substantially worse than other models.

Overall, DIDP models performed better than MIP and $CP$, and in particular $DIDP_{2T}$ performed best in terms of the number of solved instances and average time to solve the instances. We hypothesize that DIDP outperforms other models due to the combination of tight capacity constraints and the precedence constraints induced by the pickup-and-delivery structure. DIDP uses these constraints to prune many transitions and, thus, reduce the search space. This result is consistent with previously observed behavior of DIDP on constrained routing problems [15] and suggests an opportunity for research to understand model characteristics that correlate with strong DIDP performance compared to other optimization approaches.
17:14 Optimization Models for PDPs with Reconfigurable Capacities

<figure><img src="image_151.png" /><figcaption>(a) Number of instances solved to optimality.</figcaption></figure>

<figure><img src="image_152.png" /><figcaption>(b) Mean PAR10 time to solve instances.</figcaption></figure>

<figure><img src="image_153.png" /><figcaption>(c) Comparison of MRE of all the models.</figcaption></figure>

Figure 8 Performance of MIP, CP and DIDP models.

# 6 Discussion

The contributions of this work are the introduction of a novel pickup-and-delivery problem inspired by air services in northern Canada, the creation and evaluation of six optimization models in three different frameworks, and the further demonstration that the recently proposed domain-independent dynamic programming approach can out-perform incumbent techniques in a model-and-solve paradigm.

While DP models are inherently state-based, the DIDP formalism provides a novel avenue for constraint-based problem solving with connections to early ideas in CP (e.g., [6]). The DIDP models for PD-SRP are unusual as DP models due to the extensive, constraint-based, limitations on transitions (i.e., Eqs. (5c) and (5d)). While such limitations are key to strong DP performance, they are typically procedurally implemented in a problem-specific DP search algorithm. In DIDP, in contrast, constraint reasoning is used to prune transitions based on the values of state variables rather than pruning variable domains based on partial assignments. We believe that understanding this difference and developing constraint-based reasoning for this context is a fruitful research direction for CP.

Our study has a number of limitations and opportunities for further research:

- In the definition of PD-SRP, we discretized cargo into identical boxes with one size dimension (i.e., weight). In reality, cargo can take many forms from boxes of different
sizes and weights to baggage in various forms. Minimally, the volume of cargo needs to be represented. More generally, the problem should address the four-dimensional (i.e., volume plus weight) packing of heterogeneous cargo.

- We made the assumption that passengers do not have travel time restrictions. However, as a potential avenue for future research it would be interesting to incorporate additional constraints regarding how long a single passenger can be stowed in the aircraft or how long they can wait to be picked up.

- As is common in OR literature on transportation problems, our objective function is the minimization of the travel distance. A more realistic objective would represent aspects such as time and fuel consumption as well as handling and storage costs for seats.

- Most airlines run regular services with defined timetables and routings. Preliminary work indicates that determining seat exchanges is an easy problem when routes are decided. If this result bears out, there are two implications. First, we may have tools to deal with harder aspects of the real world problem including multiple aircraft, uncertain and dynamically changing demand (e.g., due to extreme weather in Canada's north), and strategic decisions about timetable creation, seat inventory, and aircraft capacities. Second, even with the version of PD-SRP presented here, we may be able to scale by exploiting the "easy" seat exchange part of the problem through Benders decomposition [2].

- Although, in this study, our focus was to design simple models that can be used "off the shelf", it is interesting to investigate sophisticated custom-constraint CP models in the future development of this work to see if they outperform the currently developed MIP and CP models.

# 7 Conclusion

This paper studied a novel pickup and delivery transportation problem with reconfigurable capacities, a problem inspired by air service in northern Canada. We defined the problem formally and developed six models in three different modeling formalisms: constraint programming, mixed integer programming, and domain-independent dynamic programming. We compared the performance of the models on a set of randomly generated instances. MIP and CP models were solved with commercial solvers, the DIDP model was solved using the recently developed domain-independent dynamic programming solver [15].

Our results show that domain-independent dynamic programming models are the fastest in both finding high-quality feasible solutions to problem instances and in solving them to optimality. For large instances, when the number of requests is greater than 15, even DIDP models were not able to solve the instances to the optimality. Although in general, MIP models were faster to find feasible solutions than CP, for short run times, CP found better solutions than both of the MIP models.

Our future work will study generalizations of the problem by considering multiple aircraft and more realistic representation of cargo size and aircraft capacity. We have also embarked on a study of the decomposition of the problem both to better fit the real-world use case where routes are often predefined and to exploit the computational advances of the mathematical structure of the decomposition.

# References

1. Maria Battarra, Jean-François Cordeau, and Manuel Iori. Chapter 6: pickup-and-delivery problems for goods transportation. In *Vehicle Routing: Problems, Methods, and Applications, Second Edition*, pages 161–191. SIAM, 2014.
17:16 Optimization Models for PDPs with Reconfigurable Capacities

2 J. Benders. Partitioning procedures for solving mixed-variables programming problems. *Numerische mathematik*, 4(1):238–252, 1962.

3 Sanjeeb Dash, Oktay Günlük, Andrea Lodi, and Andrea Tramontani. A time bucket formulation for the traveling salesman problem with time windows. *INFORMS Journal on Computing*, 24(1):132–147, 2012.

4 Irina Dumitrescu, Stefan Ropke, Jean-François Cordeau, and Gilbert Laporte. The traveling salesman problem with pickup and delivery: polyhedral results and a branch-and-cut algorithm. *Mathematical Programming*, 121:269–305, 2010.

5 Pablo Factorovich, Isabel Méndez-Díaz, and Paula Zabala. Pickup and delivery problem with incompatibility constraints. *Computers & Operations Research*, 113:104805, 2020.

6 M. S. Fox, N. Sadeh, and C. Baykan. Constrained heuristic search. In *Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89)*, pages 309–316, 1989.

7 Maria Gabriela S Furtado, Pedro Munari, and Reinaldo Morabito. Pickup and delivery problem with time windows: a new compact two-index formulation. *Operations Research Letters*, 45(4):334–341, 2017.

8 Jonas Hatzenbühler, Erik Jenelius, Győző Gidófalvi, and Oded Cats. Multi-purpose pickup and delivery problem for combined passenger and freight transport. *arXiv preprint arXiv:2210.05700*, 2022.

9 Tino Henke, M Grazia Speranza, and Gerhard Wäscher. The multi-compartment vehicle routing problem with flexible compartment sizes. *European Journal of Operational Research*, 246(3):730–743, 2015.

10 Sin C Ho, Wai Yuen Szeto, Yong-Hong Kuo, Janny MY Leung, Matthew Petering, and Terence WH Tou. A survey of dial-a-ride problems: Literature review and recent developments. *Transportation Research Part B: Methodological*, 111:395–421, 2018.

11 Alexander Hübner and Manuel Ostermeier. A multi-compartment vehicle routing problem with loading and unloading costs. *Transportation Science*, 53(1):282–300, 2019.

12 Serdar Kadioglu, Yuri Malitsky, Ashish Sabharwal, Horst Samulowitz, and Meinolf Sellmann. Algorithm selection and scheduling. In *International conference on principles and practice of constraint programming*, pages 454–469. Springer, 2011.

13 Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, *Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA*, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972.

14 Ryo Kuroiwa and J. Christopher Beck. Domain-independent dynamic programming: Generic state space search for combinatorial optimization. *Proceedings of the International Conference on Automated Planning and Scheduling*, 33(1):236–244, July 2023.

15 Ryo Kuroiwa and J. Christopher Beck. Solving domain-independent dynamic programming problems with anytime heuristic search. *Proceedings of the International Conference on Automated Planning and Scheduling*, 33:245–253, July 2023.

16 Jin Li, Qihui Lu, and Peihua Fu. Carbon footprint management of road freight transport under the carbon emission trading mechanism. *Mathematical Problems in Engineering*, 2015, 2015.

17 Clair E Miller, Albert W Tucker, and Richard A Zemlin. Integer programming formulation of traveling salesman problems. *Journal of the ACM (JACM)*, 7(4):326–329, 1960.

18 Andrea Mor and Maria Grazia Speranza. Vehicle routing problems over time: a survey. *Annals of Operations Research*, 314(1):255–275, 2022.

19 Salma Naccache, Jean-François Côté, and Leandro C Coelho. The multi-pickup and delivery problem with time windows. *European Journal of Operational Research*, 269(1):353–362, 2018.
20 Manuel Ostermeier, Tino Henke, Alexander Hübner, and Gerhard Wäscher. Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions. *European Journal of Operational Research*, 292(3):799-817, 2021.

21 Sophie N Parragh, Karl F Doerner, and Richard F Hartl. A survey on pickup and delivery models part ii: Transportation between pickup and delivery locations. *Journal für Betriebswirtschaft*, 58:81–117, 2006.

22 Yuan Qu and Jonathan F Bard. The heterogeneous pickup and delivery problem with configurable vehicle capacity. *Transportation Research Part C: Emerging Technologies*, 32:1–20, 2013.

23 Oscar Tellez, Samuel Vercraene, Fabien Lehuédé, Olivier Péton, and Thibaud Monteiro. The fleet size and mix dial-a-ride problem with reconfigurable vehicle capacity. *Transportation Research Part C: Emerging Technologies*, 91:99–123, 2018.

24 Marjolein Veenstra, Kees Jan Roodbergen, Iris FA Vis, and Leandro C Coelho. The pickup and delivery traveling salesman problem with handling costs. *European Journal of Operational Research*, 257(1):118–132, 2017.

25 Weixiong Zhang. Complete anytime beam search. In *AAAI/IAAI*, pages 425–430, 1998.
<figure><img src="image_154.png" /></figure>
# Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization

Christoph Jabs ⬒ ⬒ ID

HIIT, Department of Computer Science, University of Helsinki, Finland

Jeremias Berg ⬒ ⬒ ID

HIIT, Department of Computer Science, University of Helsinki, Finland

Hannes Ihalainen ⬒ ID

HIIT, Department of Computer Science, University of Helsinki, Finland

Matti Järvisalo ⬒ ⬒ ID

HIIT, Department of Computer Science, University of Helsinki, Finland

## Abstract

Building on Boolean satisfiability (SAT) and maximum satisfiability (MaxSAT) solving algorithms, several approaches to computing Pareto-optimal MaxSAT solutions under multiple objectives have been recently proposed. However, preprocessing in (Max)SAT-based multi-objective optimization remains so-far unexplored. Generalizing clause redundancy to the multi-objective setting, we establish provably-correct liftings of MaxSAT preprocessing techniques for multi-objective MaxSAT in terms of computing Pareto-optimal solutions. We also establish preservation of Pareto-MCSes – the multi-objective lifting of minimal correction sets tightly connected to optimal MaxSAT solutions – as a distinguishing feature between different redundancy notions in the multi-objective setting. Furthermore, we provide a first empirical evaluation of the effect of preprocessing on instance sizes and multi-objective MaxSAT solvers.

**2012 ACM Subject Classification** Mathematics of computing → Combinatorial optimization; Theory of computation → Constraint and logic programming

**Keywords and phrases** maximum satisfiability, multi-objective combinatorial optimization, preprocessing, redundancy

**Digital Object Identifier** 10.4230/LIPIcs.CP.2023.18

**Supplementary Material** Software (Source Code): https://bitbucket.org/coreo-group/mo-prepro archived at swh:1:dir:57e426c8966cdb2e20db6631aaa2f0cdd5d4cfd4

**Funding** Work financially supported by Academy of Finland under grants 322869, 342145 and 356046.

**Acknowledgements** The authors wish to thank the Finnish Computing Competence Infrastructure (FCCI) for supporting this project with computational and data storage resources.

## 1 Introduction

Boolean satisfiability (SAT) solving [7] is arguably a noticeable success story of constraint programming. The impact of SAT solvers goes beyond merely deciding satisfiability. Incremental use of SAT solvers [13] today enables efficiently solving, e.g., hard optimization problems via maximum satisfiability (MaxSAT) [1]. While MaxSAT allows for finding optimal solutions in terms of a single objective function, practical applications have motivated various algorithmic advances and non-trivial generalizations of MaxSAT solving techniques to optimization under multiple objectives [43, 40, 10, 25, 20, 11]. These algorithms allow for computing one or several of the so-called Pareto-optimal solutions of multi-objective MaxSAT instances, i.e., solutions in which no objective can be improved without negatively affecting the value of another objective.

<figure><img src="image_155.png" /></figure>

© Christoph Jabs, Jeremias Berg, Hannes Ihalainen, and Matti Järvisalo; licensed under Creative Commons License CC-BY 4.0

29th International Conference on Principles and Practice of Constraint Programming (CP 2023).

Editor: Roland H. C. Yap; Article No. 18; pp. 18:1–18:20

<figure><img src="image_156.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
## 18:2 Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization

Preprocessing has become a central part of the SAT solving pipeline [8], pruning the instance through applying complex combinations of different inference and simplification rules based on fundamental notions of (clause) redundancy. Motivated by its success in SAT, preprocessing in MaxSAT solving, through both extensions of SAT-based simplification techniques [3], and novel MaxSAT-specific techniques [5, 23, 39], is becoming increasingly popular and better understood, especially through recent work generalizing fundamental notions of redundancy in SAT [29, 28, 21, 22] to MaxSAT [24]. The MaxSAT liftings of redundancy notions allow for uniformly establishing the formal correctness of a wide range of MaxSAT preprocessing techniques [24, 4].

The advances in SAT and MaxSAT preprocessing, together with the recent advances in extending the reach of SAT-based approaches to multi-objective combinatorial optimization, call for studying fundamental and practical aspects of preprocessing in multi-objective settings. So-far preprocessing for (Max)SAT-based multi-objective optimization remains unexplored, with several open research questions. Developing correct liftings of MaxSAT preprocessing techniques to multi-objective settings, where Pareto-optimal solutions are sought for, calls for redundancy notions in order to uniformly capture the correctness of such liftings. In analogy to work analysing the power of different redundancy notions in SAT and more recently in MaxSAT, understanding the relationship between different redundancy notions in the multi-objective setting is also fundamentally relevant. From a more practical perspective, the effect of preprocessing for multi-objective problems in terms of simplifications achieved and solver runtimes has also not been thoroughly explored.

We make contributions to each of these questions. We provide redundancy notions for the multi-objective setting based on the notions of reconstructible and literal-reconstructible clauses, allowing for establishing the correctness of a large number of preprocessing techniques for multi-objective MaxSAT in terms of computing Pareto-optimal solutions. Additionally, we identify the preservation of Pareto-MCSes (the multi-objective lifting of minimal correction sets tightly connected to Pareto-optimal solutions [42]) as a distinguishing feature between the two proposed redundancy notions. We also consider liftings of MaxSAT preprocessing techniques which alter in a controlled way the objective functions at hand and thereby cannot be directly captured by the clause redundancy notions. Putting these preprocessing techniques lifted to the multi-objective setting into practice, we provide a first preprocessor implementation for multi-objective MaxSAT, and perform a first empirical evaluation of the effect of preprocessing both in terms of instance size reductions achieved and runtimes of recently proposed approaches to multi-objective MaxSAT solving.

## 2 Multi-Objective MaxSAT

For a Boolean variable $x$ there are two literals, $x$ and $\neg x$. A clause $C$ is a set (or disjunction) of literals and a (CNF) formula $F$ a set (or conjunction) of clauses. A (truth) assignment $\tau$ assigns variables to truth values 0 (false) or 1 (true). Assignments are extended to literals $l$, clauses $C$, and formulas $F$, in the standard way: $\tau(\neg l) = 1 - \tau(l)$, $\tau(C) = \max\{\tau(l) \mid l \in C\}$, and $\tau(F) = \min\{\tau(C) \mid C \in F\}$, defining semantics for CNF formulas. An assignment $\tau$ is a solution to a CNF formula $F$ if $\tau(F) = 1$; $\tau$ is complete for $F$ if $\tau$ assigns a value to all variables in $F$, and otherwise partial for $F$. With slight abuse of notation, an assignment $\tau$ can be viewed as the set of the literals it assigns to 1. Then $\tau(x) = 1$ ($\tau(x) = 0$) is shorthand for $x \in \tau(\neg x \in \tau)$, $\neg C$ for $\{\neg l \mid l \in C\}$, and $\tau \supset \neg C$ means that $\tau$ falsifies a clause $C$.

We focus on the following natural generalization of the maximum satisfiability (MaxSAT) problem to multi-objective combinatorial optimization [44, 17, 15]. An instance $I = (F, O)$ of multi-objective MaxSAT (MO-MaxSAT) consists of a CNF formula $F$, the clauses of which
need to be satisfied by any solution to the instance, and a tuple $O = (O_1, \dots, O_p)$ of $p$ linear
objective functions with positive coefficients over literals (or equivalently, pseudo-Boolean
expressions) under minimization. We denote the set of literals appearing in $O_i$ by $B_i(I)$
and the set of literals appearing in at least one of the objectives by $\mathcal{B}(I) = \bigcup_{i=1}^p B_i(I)$.
Furthermore, we denote by $c_i(l)$ the coefficient of literal $l$ in $O_i$. If $l$ does not appear in $O_i$,
then $c_i(l) = 0$.

The cost $O(\tau) = (O_1(\tau), \dots, O_p(\tau))$ of a solution $\tau$ to $\mathcal{I}$ (i.e., a solution to $F$) is obtained
by evaluating each objective under $\tau$. If $\tau$ is not a solution of $F$, we let $O(\tau) = (\infty, \dots, \infty)$.
As a central notion of optimality in the multi-objective setting in general, we focus on
Pareto-optimality, which is based on the following domination relation between solutions.

**Definition 1 (Weak) Domination.** *Consider two solutions $\tau_1$ and $\tau_2$ with costs $O(\tau_1) = (O_1(\tau_1), \dots, O_p(\tau_1))$ and $O(\tau_2) = (O_1(\tau_2), \dots, O_p(\tau_2))$. The solution $\tau_1$ weakly dominates $\tau_2$ (denoted $\tau_1 \preceq \tau_2$) if $O_i(\tau_1) \le O_i(\tau_2)$ holds for all $i = 1, \dots, p$. If additionally $O_i(\tau_1) < O_i(\tau_2)$ for some $i$, then $\tau_1$ dominates $\tau_2$ (denoted $\tau_1 \prec \tau_2$).*

Intuitively, the solution $\tau_1$ weakly dominates another solution $\tau_2$ if it is not worse in any
objective. We use $\tau_1 \not\preceq \tau_2$ to denote that $\tau_1$ does not weakly dominate $\tau_2$. Note that
domination is not a total order on solutions, i.e., $\tau_1 \not\preceq \tau_2$ does not generally imply $\tau_2 \prec \tau_1$ or
$\tau_2 \preceq \tau_1$.

A partial assignment $\tau^p$ dominates another (partial) assignment $\delta^p$ if for every extension
$\delta \supset \delta^p$ there is an extension $\tau \supset \tau^p$ that dominates $\delta$. A solution $\tau$ to an MO-MaxSAT
instance $\mathcal{I}$ is Pareto-optimal<fnref n="1" /> if $\tau$ is not dominated by any other solution to $\mathcal{I}$.

The notion of the non-dominated set of an MO-MaxSAT instance characterizes the
solutions of interest in terms of their (non-dominated) costs.

**Definition 2 (Non-dominated set).** *The non-dominated set *non-dominated*($\mathcal{I}$) = {$O(\tau)$ | $\tau$ is Pareto-optimal} of an MO-MaxSAT instance $\mathcal{I}$ = (F, O) consists of the costs of the Pareto-optimal solutions of $\mathcal{I}$.*

Practical algorithm for computing the non-dominated set of a given MO-MaxSAT instance
also provide for each cost $o \in \text{non-dominated}(\mathcal{I})$ a Pareto-optimal solution having cost
$o$. It is worth noting that for an $o \in \text{non-dominated}(\mathcal{I})$ there may be more than one
Pareto-optimal solution with cost $o$ and that for a single-objective MaxSAT instance $\mathcal{I}$ the
set $\text{non-dominated}(\mathcal{I})$ consists of the optimal (minimum) cost of $\mathcal{I}$.

**3 Clause Redundancy in MO-MaxSAT**

Preprocessing an MO-MaxSAT instance $\mathcal{I}$ refers to the iterative application of a set of preprocessing techniques (inference/simplification rules) on $\mathcal{I}$, resulting in a preprocessed instance $\mathcal{P}(\mathcal{I})$ for which $\text{non-dominated}(\mathcal{I}) = \text{non-dominated}(\mathcal{P}(\mathcal{I}))$. In other words, correctness of preprocessing requires that the non-dominated set of the original $\mathcal{I}$ does not change under the preprocessing techniques applied.

As fundamental notions for capturing, establishing the correctness of, and analysing the
strengths of different MO-MaxSAT preprocessing techniques, we propose several (clause)
redundancy properties in MO-MaxSAT. These properties can be viewed as multi-objective
counterparts of earlier proposed redundancy notions in SAT [29, 28, 21, 22] and most recently

<footnote n="1">¹ Sometimes in the literature also referred to as *efficient* or *non-inferior* [14].</footnote>
18:4 Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization

in MaxSAT [24], with similar motivations. In contrast to SAT (where clause redundancy
notions are required to preserve satisfiability) and similarly as in MaxSAT, clause redundancy
notions are required to preserve optimal costs. Compared to MaxSAT, however, the multiple
objectives and Pareto optimization require additional care.

For an MO-MaxSAT instance $\mathcal{I} = (F, O)$ and a clause $C$, $\mathcal{I} \wedge C = (F \wedge C, O)$ is the instance obtained by adding $C$ to $\mathcal{I}$. We begin with a general notion of redundancy for the problem of computing the non-dominated set in MO-MaxSAT.

**Definition 3 (Redundant clauses).** A clause *C* is redundant wrt an MO-MaxSAT instance *I* if *non-dominated*(*I*) = *non-dominated*(*I* ∧ *C*).

Note that this definition does not require that all Pareto-optimal solutions should be preserved.

We propose two refined redundancy notions which turn out to differ in strength and
thereby in terms of the preprocessing techniques they capture. The notions are based on
the following alternative characterization of redundancy that essentially states that a clause
*C* is redundant if every solution that falsifies it is weakly dominated by some solution that
satisfies *C*.

**Proposition 4.** *A clause C is redundant wrt an instance I = (F, O) iff, for any solution τ ⊃ ¬C to I that falsifies C, there is a witnessing assignment (or simply witness) ω^τ for which ω^τ(C) = 1 and ω^τ ≤ τ.*

**Proof.** We prove each of the directions separately.

C is redundant $\Rightarrow$ a witness exists: Consider a solution $\tau \supset \neg C$ to $\mathcal{I}$. Then there exists a Pareto-optimal solution $\delta \preceq \tau$ (we can pick $\delta = \tau$ if $\tau$ is Pareto-optimal). Since non-dominated($\mathcal{I}$) = non-dominated($\mathcal{I} \wedge C$) (as $C$ is redundant), there is a solution $\omega^\delta$ to $\mathcal{I} \wedge C$ with $O(\tau) = O(\omega^\delta)$. Such $\omega^\delta$ satisfies $C$ and weakly dominates $\delta$. Thus, it also weakly dominates $\tau$, fulfilling the requirements of the proposition.

A witness exists $\Rightarrow$ C is redundant: To show that C is redundant according to Definition 3 we show that non-dominated($\mathcal{I} \wedge C$) = non-dominated($\mathcal{I}$). For the direction non-dominated($\mathcal{I} \wedge C$) $\subset$ non-dominated($\mathcal{I}$), note that every Pareto-optimal solution $\tau$ to $\mathcal{I} \wedge C$ is also a solution to $\mathcal{I}$. Furthermore, $\tau$ is also Pareto-optimal wrt $\mathcal{I}$. If this was not the case, by the assumption the solution $\delta$ dominating $\tau$ wrt $\mathcal{I}$ would have a witness $\omega^\delta$ dominating $\tau$ wrt $\mathcal{I} \wedge C$. Since therefore every Pareto-optimal solution to $\mathcal{I} \wedge C$ is also Pareto-optimal wrt $\mathcal{I}$, it follows that non-dominated($\mathcal{I} \wedge C$) $\subset$ non-dominated($\mathcal{I}$).
For the other direction consider an element $o \in$ non-dominated($\mathcal{I}$) and let $\tau$ be a Pareto-optimal solution to $\mathcal{I}$ for which $O(\tau) = o$. For the interesting case, assume $\tau \supset \neg C$, i.e., that it falsifies $C$. Then by the assumption $\tau$ is weakly dominated by some witness $\omega^\tau$ that satisfies $C$. Now $O(\tau) = O(\omega^\tau) = o$ (as otherwise $\tau$ would not be Pareto-optimal) demonstrating that $o \in$ non-dominated($\mathcal{I} \wedge C$) and thus that $C$ is redundant. $\quad$

The (weakly) dominating witness $\omega^\tau$ guaranteed by Proposition 4 for any redundant
clause *C* might differ depending on the specific solution $\tau$ that falsifies *C*. The redundancy
notions of *reconstructible* and *literal-reconstructible* clauses we propose next are based on
placing stronger requirements on this witness.

**Definition 5 (Reconstructible clauses).** A clause *C* is reconstructible on the (partial) assignment $\omega$ wrt an MO-MaxSAT instance $\mathcal{I}$ if (i) $\omega(C) = 1$, and (ii) $(\tau \setminus \neg\omega) \cup \omega \preceq \tau$ for every solution $\tau \supset \neg C$ to $\mathcal{I}$.
In words, a clause *C* is reconstructible wrt an MO-MaxSAT instance *I* if there is a single witnessing assignment *ω* that satisfies *C* and weakly dominates all solutions *τ* that do not. Moreover, enforcing the partial assignment *ω* in any such solution *τ* allows for efficiently obtaining a solution to *I* that satisfies *C* and weakly dominates *τ*. For the corner case, note that if there are no solutions to *I* that falsify *C*, then *C* is reconstructible on any witness.

The fact that reconstructible clauses are redundant follows directly from Proposition 4.
The next example demonstrates that the converse does not hold. Central to the example is
to note that a direct consequence of Definition 5 is that if C is reconstructible on the partial
assignment ω, then ω weakly dominates the partial assignment ¬C.

**► Example 6.** Let $\mathcal{I} = (F, (O_1, O_2))$ be an MO-MaxSAT instance with $F = (a_1 \lor a_2) \land (b_1 \lor b_2) \land (a_1 \lor b_1) \land (a_1 \lor b_2) \land (a_2 \lor b_1) \land (a_2 \lor b_2)$, $O_1 = a_1 + a_2$, and $O_2 = b_1 + b_2$. Then non-dominated($\mathcal{I}$) = $\{(1, 2), (2, 1)\}$, and the Pareto-optimal solutions are $\tau_1 = \{a_1, \neg a_2, b_1, b_2\}$, $\tau_2 = \{\neg a_1, a_2, b_1, b_2\}$, $\tau_3 = \{a_1, a_2, \neg b_1, b_2\}$, and $\tau_4 = \{a_1, a_2, b_1, \neg b_2\}$. Consider the clause $C = (\neg a_2 \lor \neg b_2)$. Since $\tau_1$ and $\tau_4$ are solutions to $F \land C$, adding $C$ does not change the non-dominated set of the instance. Thus, $C$ is redundant wrt $\mathcal{I}$. To see that $C$ is not reconstructible we show that no partial assignment $\omega$ that satisfies $C$ weakly dominates $\neg C$. There are two possible candidates for such $\omega$ (as $C$ contains two literals): $\omega_1 = \{\neg a_2\}$ and $\omega_2 = \{\neg b_2\}$. The only solution of $\mathcal{I}$ that $\omega_1$ can be extended to is $\tau_1$. However, $\neg C$ can be extended to $\tau_3$, which is not weakly dominated by $\tau_1$. Similarly, $\omega_2 = \{\neg b_2\}$ does not weakly dominate $\tau_2 \supset \neg C$, showing that $\omega_2 \not\le \neg C$.

Contrasting Example 6, the next proposition shows that the notions of (clause) redundancy according to Definition 3 and reconstructible clauses according to Definition 5 coincide for single-objective MaxSAT instances that have solutions.

**► Proposition 7.** For a single-objective MaxSAT instance $\mathcal{I} = (F, (O_1))$ with at least one solution $\tau$ and clause $C$, it holds that $C$ is reconstructible for $\mathcal{I}$ iff $C$ is redundant.

**Proof (sketch).** For the non-trivial direction, assume that *C* is redundant. Then there is an optimal (minimum-cost) solution τ° to *I* that satisfies *C*. As *I* only has a single objective, τ° weakly dominates all solutions to *I*. Therefore, *C* is reconstructible on τ°. ◀

As a further notion of redundancy, we consider *literal-reconstructible* clauses as a special case of reconstructible clauses where the witness is required to consist of a single literal. In Section 4 we discuss properties that literal-reconstructible clauses specifically satisfy and overview in Section 5.1 preprocessing techniques that can be characterized by adding and removing literal-reconstructible clauses.

**► Definition 8 (Literal-reconstructible clauses).** A clause *C* is literal-reconstructible wrt an instance *I* = (*F*,*O*) if either (i) all solutions to *F* satisfy *C*, or (ii) there is a non-objective literal *l* ∈ *C* \ *B(I)* s.t. if *τ* ⊃ ¬*C* is a solution to *F*, then *τ*<sub>*l*</sub> = (*τ* \ {¬*l*}) ∪ {*l*} is a solution to *F* ∧ *C*. If condition (ii) holds, we say that *C* is literal-reconstructible on the literal *l*.

Note that the definition of literal-reconstructible clauses does not explicitly require that $\tau_l$ weakly dominates $\tau$, as this follows from $l$ not being an objective literal. The following proposition states that literal-reconstructible clauses are redundant in terms of Definition 3.

**► Proposition 9.** If a clause *C* is literal-reconstructible wrt an MO-MaxSAT instance *I* = (*F*, (*O*₁, ..., *O*ₚ)), then non-dominated(*I*) = non-dominated(*I* ∧ *C*).
**Proof (sketch).** For the interesting case, assume that there is a solution $\tau \supset \neg C$ to $\mathcal{I}$ that does not satisfy $C$. Let $l \in C \setminus \mathcal{B}(\mathcal{I})$ be the literal on which $C$ is literal-reconstructible and consider the solution $\tau_l = (\tau \setminus \{\neg l\}) \cup \{l\}$. Then by the assumption $\tau_l$ is a solution to $\mathcal{I} \wedge C$ and as $l \notin \mathcal{B}(\mathcal{I})$ we have that $O_i(\tau_l) \le O_i(\tau)$ for all objectives, i.e., for each $i = 1, \dots, p$. As $\tau_l$ is a solution to both $\mathcal{I}$ and $\mathcal{I} \wedge C$, the result follows. ◀

A clause that is literal-reconstructible on $l$ is also reconstructible on the witness $\omega = \{l\}$. The following example shows that the opposite does not hold in general, i.e., there are reconstructible clauses that are not literal-reconstructible.

**► Example 10.** Consider the MO-MaxSAT instance $\mathcal{I} = (F, (O_1))$ with $F = (a_1 \vee a_2)$ and $O_1 = a_1 + a_2$. The clause $C = (\neg a_1)$ is reconstructible on the witness $\omega = \{\neg a_1, a_2\}$. The assignment $\tau = \{a_1, \neg a_2\}$ is a solution to $F$ but does not satisfy $C$. The only literal $l \in C \setminus \mathcal{B}(\mathcal{I})$ is $\neg a_1$, but $(\{a_1, \neg a_2\} \setminus \{a_1\}) \cup \{\neg a_1\} = \{\neg a_1, \neg a_2\}$ is not a solution to $F \wedge C$. It follows that $C$ is not literal-reconstructible.

The relative generality of these three MO-MaxSAT redundancy notion can be summarized as follows. For any MO-MaxSAT instance $\mathcal{I}$, the set of redundant clauses $\text{Red}(\mathcal{I})$ is a superset of the set of reconstructible clauses $\text{Rec}(\mathcal{I})$, and $\text{Rec}(\mathcal{I})$ is a superset of the set of literal-reconstructible clauses $\text{LRec}(\mathcal{I})$. Furthermore, there are clauses that are reconstructible but not literal-reconstructible (i.e., there is an instance $\mathcal{I}$ for which $\text{Rec}(\mathcal{I}) \supsetneq \text{LRec}(\mathcal{I}))$, and clauses that are redundant (in terms of Definition 3) that are not reconstructible (i.e., there is an instance $\mathcal{I}'$ for which $\text{Red}(\mathcal{I}') \supsetneq \text{Rec}(\mathcal{I}'))$. In contrast to single-objective MaxSAT, the last statement holds also for instances that have solutions as for a single objective instance $\mathcal{I}''$ we have that $\text{Red}(\mathcal{I}'') \neq \text{Rec}(\mathcal{I}'')$ if and only if $\mathcal{I}''$ does not have solutions.

As a side-remark, literal-reconstructible clauses are related to so-called cost literal propagation redundant clauses [24] recently proposed for (single-objective) MaxSAT: any cost literal propagation redundant clause is literal-reconstructible under a single objective. The opposite holds only when conditions (i) and (ii) in Definition 8 can be deterministically checked by standard Boolean constraint propagation on clauses (i.e., unit propagation). Intuitively, literal-reconstructible clauses extend and slightly generalize the concept of cost literal propagation redundant clauses for the multi-objective setting.

## 4 Redundancy and Pareto-MCSes

We move on to analysing the effect that adding (literal-)reconstructible clauses to an MO-MaxSAT instance has on the solution space in terms of so-called Pareto minimal correction sets (Pareto-MCSes) [42, 43], that – informally speaking – correspond to subset-minimal sets of objective literals that are assigned to 1 by at least one Pareto-optimal solution.

**► Definition 11 (Pareto-MCS).** Consider an MO-MaxSAT instance $\mathcal{I} = (F, O)$. A subset $M \subset \mathcal{B}(\mathcal{I})$ of objective literals is a correction set if there is a solution $\tau$ of $\mathcal{I}$ that assigns $\tau(l) = 0$ for every objective literal $l$ not appearing in $M$. $M$ is a minimal correction set (MCS) (or multi minimal correction subset as in [42]) if no $M' \subseteq M$ is a correction set. Finally, $M$ is a Pareto-MCS if each solution $\tau$ that assign $\tau(l) = 0$ for every $l \in \mathcal{B}(\mathcal{I}) \setminus M$ is Pareto-optimal. The set $\text{ParetoMCS}(\mathcal{I})$ consists of the Pareto-MCSes of $\mathcal{I}$.

For some intuition, note that assigning an objective literal to 1 can be seen as falsifying a soft constraint. If $M$ is an MCS or Pareto-MCS, then for any solution with $\tau(l) = 0$ for every literal not in $M$ we also have $\tau(l') = 1$ for every literal $l'$ in $M$. From this point of view, these definitions of MCSes align with the (arguably more classical) ones in terms of subset-minimal sets of soft constraints falsified by some solution. Specifically, if $\mathcal{I}$ only has a single objective, this definition is identical to MCSes in single-objective MaxSAT [36].
The relationship between Pareto-optimal solutions, Pareto-MCSes and elements of the non-dominated set is not one-to-one. For a Pareto-MCS $M$ of an MO-MaxSAT instance $\mathcal{I} = (F, O)$, there is at least one corresponding Pareto-optimal solution $\tau$ to $\mathcal{I}$. The cost of each such $\tau$ wrt each objective in $O$ is the sum of the objective coefficients of the objective literals included in $M$. There can be multiple Pareto-optimal solutions that correspond to a Pareto-MCS which differ in how non-objective variables are assigned. Furthermore, for a single element (cost tuple) in the non-dominated set, there can be multiple corresponding Pareto-MCSes, since two different Pareto-MCSes can incur the same cost wrt each objective of $\mathcal{I}$. Hence, preserving the Pareto-MCSes of an input MO-MaxSAT instance $\mathcal{I}$ is a sufficient but not necessary condition for preserving non-dominated($\mathcal{I}$). For computing the non-dominated set, it suffices that at least one corresponding Pareto-MCS for each element in the non-dominated set is preserved.

We establish the fact that preservation of the set of Pareto-MCSes is a property of literal-reconstructible clauses, distinguishing this notion from the more general notion of reconstructible clauses which does not have this property. More precisely, the following summarizes the main theorem of this section: adding/removing literal-reconstructible clauses does not change the set of Pareto-MCSes.

**Theorem 12.** *Assume that $C$ is literal-reconstructible wrt an MO-MaxSAT instance $\mathcal{I} = (F, O)$. Then $\text{ParetoMCS}(\mathcal{I}) = \text{ParetoMCS}(\mathcal{I} \wedge C)$.*

A proof of Theorem 12 relies on showing that, given any Pareto-optimal solution $\tau \supset \neg C$ of $\mathcal{I}$ that does not satisfy $C$, the weakly-dominating (Pareto-optimal) witness $\tau_l$ obtained by flipping the value of the literal $l \in C \setminus \mathcal{B}(\mathcal{I})$ that $C$ is literal-reconstructible on corresponds to the exact same Pareto-MCS as $\tau$. Toward formalizing this intuition, we show that if the negation of $l$ is in any objective, then there is no Pareto-optimal solution that falsifies $C$.

**Lemma 13.** *Let $C$ be literal-reconstructible on $l$ wrt $\mathcal{I} = (F, O)$ and $\neg l$ an objective literal, i.e., $\neg l \in \mathcal{B}(\mathcal{I})$. Then there is no Pareto-optimal solution $\tau \supset \neg C$ to $\mathcal{I}$ that falsifies $C$.*

**Proof of Lemma 13.** As $C$ is literal-reconstructible on $l$, $\tau' = (\tau \setminus \{\neg l\}) \cup \{l\}$ is a solution to $\mathcal{I}$. Because $\neg l \in \mathcal{B}(\mathcal{I})$ and therefore at least one of the objectives evaluates to less for $\tau'$ than for $\tau$, $\tau' \prec \tau$. Therefore, $\tau$ is not Pareto-optimal. ◀

With the inverse of Lemma 13 covering the (special) case of some Pareto-optimal solutions falsifying $C$, we turn to the proof of Theorem 12.

**Proof of Theorem 12.** If $C$ is literal-reconstructible because every solution of $\mathcal{I}$ satisfies $C$, the solutions and therefore the set of Pareto-MCSes of $\mathcal{I}$ and $\mathcal{I} \wedge C$ are the same. Otherwise, let $C$ be literal-reconstructible on $l$ and consider the following.

*ParetoMCS(\(\mathcal{I}\) ⊂ ParetoMCS(\(\mathcal{I} \wedge C\)):* Let $M \in \text{ParetoMCS}(\mathcal{I})$ and consider the Pareto-optimal solution $\tau^M \supset \{\neg b \mid b \in \mathcal{B}(\mathcal{I}) \setminus M\}$ to $\mathcal{I}$ that sets $\tau(b) = 0$ for every objective literal $b$ not in $M$. Since $C$ is literal-reconstructible on $l$, there is a solution $\delta$ to $F \wedge C$ that weakly dominates $\tau^M$. If $\tau^M$ satisfies $C$, then $\delta = \tau^M$. Otherwise, $\delta = (\tau^M \setminus \{\neg l\}) \cup \{l\}$, and since $\tau^M$ is Pareto-optimal and falsifies $C$, by Lemma 13 $\neg l$ is not an objective literal. In both cases $\delta$ corresponds to the same MCS ($M$) as $\tau^M$. Furthermore, $M$ must be a Pareto-MCS of $\mathcal{I} \wedge C$ as any solution dominating $\delta$ would also be a solution to $\mathcal{I}$ and therefore $M$ would not be a Pareto-MCS of $\mathcal{I}$.

*ParetoMCS(\(\mathcal{I} \wedge C\) ⊂ ParetoMCS(\(\mathcal{I}\)):* Given $M \in \text{ParetoMCS}(\mathcal{I} \wedge C)$ and a Pareto-optimal $\tau^M \supset \{\neg b \mid b \in \mathcal{B}(\mathcal{I}) \setminus M\}$ to $\mathcal{I} \wedge C$, $\tau^M$ is also Pareto-optimal for $\mathcal{I}$ as any dominating solution could be reconstructed (by flipping the value of $l$) into a solution to $\mathcal{I} \wedge C$ dominating $\tau^M$. ◀
18:8 Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization

Contrasting Theorem 12, we show that a similar result cannot be obtained for recon-
structible clauses.

**Proposition 14.** *There is an MO-MaxSAT instance *I* and a reconstructible clause *C* wrt *I* for which *ParetoMCS*(*I* ∧ *C*) ⊊ *ParetoMCS*(*I*).*

**Proof.** Consider the MO-MaxSAT instance $\mathcal{I} = (F, (O_1, O_2))$ with $F = (a_1 \lor b_1 \lor b_2)$, $O_1 = a_1$, $O_2 = b_1 + b_2$, and $C = (\neg b_2)$. We have that $\text{ParetoMCS}(\mathcal{I}) = \{\{a_1\}, \{b_1\}, \{b_2\}\}$ and $\text{ParetoMCS}(\mathcal{I} \wedge C) = \{\{a_1\}, \{b_1\}\}$.

Since the only clause in $F$ and $C$ are both satisfied by $\omega = \{b_1, \neg b_2\}$, every superset of $\omega$ is a solution to $F \wedge C$. Furthermore, given a solution $\tau$ to $F$ that falsifies $C$, the solution $\tau_{\omega} = (\tau \setminus \neg \omega) \cup \omega$ has $O_1(\tau_{\omega}) = O_1(\tau)$ and $O_2(\tau_{\omega}) \le O_2(\tau)$, hence $\tau_{\omega} \le \tau$. It follows that $C$ is reconstructible on $\omega$ wrt $\mathcal{I}$. ◀

This distinction between literal-reconstructible and reconstructible clauses in terms of
the preservation of Pareto-MCSes provides two important insights.

Firstly, the fact that adding/removing literal-reconstructible clauses does not change
the set of Pareto-MCSes implies that (single-objective) MaxSAT preprocessing techniques
that can be viewed as sequences of adding and removing literal-reconstructible clauses are
techniques that are “directly applicable” to MO-MaxSAT. In particular, it has been shown
that the non-dominated set of an MO-MaxSAT instance $\mathcal{I} = (F, O)$ can be computed by
enumerating its Pareto-MCSes, which can in turn be achieved by enumerating the MCSes of
the (single-objective) MaxSAT instance $(F, O^m)$ with the single objective $O^m = \sum_{O_i \in O} O_i$
that sums all objectives of $\mathcal{I}$ [43]. Thus, any preprocessing technique for single-objective
MaxSAT that preserves MCSes is directly applicable to MO-MaxSAT by applying it to
$(F, (O^m))$ and using the preprocessed formula in the MO-MaxSAT instance. The correctness
of such techniques – which we will overview shortly – can either be directly argued on the MO-
MaxSAT level by viewing them as sequences of adding and removing literal-reconstructible
clauses, or by using (MCS-preserving) redundancy notions such as cost literal propagation
redundancy on the level of single-objective MaxSAT. On the other hand, preprocessing
techniques captured by reconstructible clauses but which cannot be captured by literal-
reconstructible clauses – as detailed later on – go beyond preserving Pareto-MCSes, having
the ability to eliminate Pareto-MCSes that are redundant in terms of the non-dominating
set. Hence, reconstructible clauses are key in capturing the correctness of such techniques in
a uniform way.

5 Preprocessing for MO-MaxSAT

We proceed with overviewing a range of preprocessing techniques for MO-MaxSAT, lifting
earlier-proposed techniques from single-objective MaxSAT (some of which originate from
SAT) to the multi-objective setting. We detail in short which of the techniques are captured
by the notions of reconstructible or literal-reconstructible clauses by simulating the techniques
via sequences of additions and removals of redundant clauses of a specific type.

**5.1 Preprocessing Techniques Captured by Literal-Reconstructible Clauses**

First, we shortly recall well-known single-objective MaxSAT preprocessing techniques that are
known to preserve MCSes [24]. We note again that the correctness of these techniques follows
from the previously mentioned fact that each of them preserve MCSes in single-objective
MaxSAT, which further follows naturally from earlier work on capturing these techniques in the setting of SAT solving via redundancy notions developed for SAT. Alternatively – as we will detail in the following – the correctness arguments can be directly made on the MO-MaxSAT level by showing that each technique can be simulated via removing and adding literal-reconstructible clauses. For the following list of techniques, let $\mathcal{I} = (F, O)$ be an MO-MaxSAT instance with $O = (O_1, \dots, O_p)$.

**Bounded Variable Elimination (BVE) [41, 12].** BVE as arguably the most important SAT preprocessing technique allows eliminating a non-objective variable $x \notin \mathcal{B}(\mathcal{I})$ (and $\neg x \notin \mathcal{B}(\mathcal{I})$) from $\mathcal{I}$. A step of BVE on $\mathcal{I}$ and $x$ results in the MO-MaxSAT instance $\mathbf{bve}(\mathcal{I}, x) = (F \cup F_{\text{res}} \setminus (F_x \cup F_{\neg x}), O)$, where $F_x = \{C \in F \mid x \in C\}$, $F_{\neg x} = \{C \in F \mid \neg x \in C\}$ are the sets of clauses containing $x$ and $\neg x$, respectively, and $F_{\text{res}} = \{(A \lor B) \mid (A \lor x), (B \lor \neg x) \in F\}$ is the set of all non-tautological resolvents on $x$ of the clauses in $F$, bounded in practice to eliminate variables when this decreases the number of clauses. Working directly on the MO-MaxSAT level, $\mathbf{bve}(\mathcal{I}, x)$ can be obtained from $\mathcal{I} = (F, O)$ by a sequence of additions and removals of literal-reconstructible clauses as follows. First add $F_{\text{res}}$ to $F$ which does not change the non-dominated set because every clause in $F_{\text{res}}$ is satisfied by any solution to $F$ and therefore literal-reconstructible wrt $\mathcal{I}$ and any instance obtained by adding clauses from $F_{\text{res}}$ to $\mathcal{I}$. Note that for every $(A \lor B) \in F_{\text{res}}$, by construction of $F_{\text{res}}$, $(A \lor x), (B \lor \neg x) \in F$. Second, remove the clauses $F_x \cup F_{\neg x}$ from the intermediate instance $\mathcal{I}' = (F \cup F_{\text{res}}, O)$: every clause in $F_x$ (resp. $F_{\neg x}$) is literal-reconstructible on $x$ (resp. $\neg x$) wrt $\mathcal{I}'$ and any instance obtained by removing clauses in $F_x \cup F_{\neg x}$ from $\mathcal{I}'$.

**Blocked Clause Elimination (BCE) [27].** BCE removes blocked clauses [33]: a clause $(C \lor l) \in F$ is blocked on a literal $l \notin \mathcal{B}(\mathcal{I})$ if for every clause $(D \lor \neg l) \in F$ containing $\neg l$, the resolvent $(C \lor D)$ is a tautology. Note that a clause blocked on $l$ is literal-reconstructible on $l$.

**Subsumption Elimination (SE).** A clause $C \in F$ is subsumed by another clause $D \in F$ if $D \subset C$. One step of SE removes a subsumed clause $C$, resulting in the instance $\mathbf{se}(\mathcal{I}, C) = (F \setminus \{C\}, O)$. Note that any solution to $\mathbf{se}(\mathcal{I}, C)$ also satisfies $C$, and thus $C$ is literal-reconstructible wrt $\mathbf{se}(\mathcal{I}, C)$.

**Unit Propagation (UP).** Given a non-objective literal $l \notin \mathcal{B}(\mathcal{I})$ and a unit clause $(l) \in F$, unit propagation removes each clause $C \in F$ containing $l$ ($l \in C$) and removes the negation $\neg l$ from the remaining clauses. Similarly as in SAT, UP can be viewed as an application of BVE on $l$ (to remove negation $\neg l$ from all clauses) followed by an application SE (to remove resolvents introduced by BVE).

**Self-Subsuming Resolution (SSR) [38, 12].** Given two clauses $(x \lor A), (\neg x \lor B) \in F$ s.t. $A \subset B$, $x \notin \mathcal{B}(\mathcal{I})$, and $\neg x \notin \mathcal{B}(\mathcal{I})$, a step of SSR results in the formula $\mathbf{ssr}(\mathcal{I}, (\neg x \lor B)) = ((F \cup \{B\}) \setminus \{(\neg x \lor B)\}, O)$. Note that $B$ is literal-reconstructible wrt $\mathcal{I}$ and that $(\neg x \lor B)$ is subsumed in $F \land B$.

**Failed Literal Elimination (FLE) and TrimMaxSAT.** FLE [46, 18, 34] and TrimMaxSAT [39] allow for detecting unit clauses entailed by $F$, i.e., clauses satisfied by every solution to $\mathcal{I}$. Such clauses are by definition literal-reconstructible.
**Equivalent Literal Substitution (ELS) [35, 9, 45].** Two literals $l_1, l_2$ are equivalent if $\tau(l_1) = \tau(l_2)$ for every solution $\tau$. If neither literal nor their negation occur in objectives, equivalent literal substitution replaces every occurrence of $l_2$ with $l_1$ and $\neg l_2$ with $\neg l_1$. Viewed in terms of literal-reconstructible clauses, first add the clauses in which $l_2$ ($\neg l_2$) has been replaced and then remove clauses containing $l_2$ ($\neg l_2$). Both of these sets of clauses are literal-reconstructible wrt the instance they are added to / removed from because $\tau(l_1) = \tau(l_2)$.

## 5.2 Preprocessing Techniques Captured by Reconstructible Clauses

We now turn to techniques that do not preserve all Pareto-MCSes and therefore require a more general notion of redundancy. Specifically, we lift (group-)subsumed label elimination ((G)SLE) [5, 31] from MaxSAT, extending subsumption to objective literals, to MO-MaxSAT and show that it is captured by adding reconstructible clauses.

**► Definition 15.** An objective literal $l \in \mathcal{B}(\mathcal{I})$ of an MO-MaxSAT instance $\mathcal{I} = (F, (O_1, \dots, O_p))$ is subsumed if there is a group of objective literals $S \subset \mathcal{B}(\mathcal{I})$ for which (i) $c_i(l) \ge c_i(\neg l) + \sum_{s \in S} c_i(s)$ for all objectives $(i = 1, \dots, p)$, (ii) every clause $C \in F$ that contains $l$ also contains some literal $s \in S$, and (iii) every clause $C \in F$ that contains the negation of any $s \in S$ also contains $\neg l$.

Informally speaking, a step of GSLE on an MO-MaxSAT instance $\mathcal{I}$ wrt a subsumed literal $l$ fixes $l=0$. More formally, it results in the instance $\mathbf{gsle}(\mathcal{I}, l) = \mathcal{I} \wedge (\neg l)$.

In contrast to the preprocessing techniques discussed in the preceding subsection, GSLE cannot be lifted from single-objective MaxSAT to MO-MaxSAT by simply combining multiple objectives into a sum. To see this, consider the MO-MaxSAT instance from the proof of Proposition 14. When applying single-objective GSLE by summing the objectives as $O_1 + O_2 = a_1 + b_1 + b_2$, $a_1$ is subsumed by $\{b_1\}$. However, adding the clause $(\neg a_1)$ removes (1,0) from the non-dominated set.

The following example demonstrates that GSLE can remove Pareto-MCSes.

**► Example 16.** Consider the MO-MaxSAT instance in the proof of Proposition 14. According to Definition 15 $b_2$ is subsumed by $\{b_1\}$, hence $\mathbf{gsle}(\mathcal{I}, b_2) = (F \wedge (\neg b_2), (O_1, O_2))$, and thus $\mathbf{ParetoMCS}(\mathbf{gsle}(\mathcal{I}, b_2)) \subseteq \mathbf{ParetoMCS}(\mathcal{I})$

For an alternative proof of the fact that GSLE cannot be viewed as a sequence of adding/re-moving literal-reconstructible clauses, consider Example 10 where it was argued that the clause $(\neg a_1)$ is reconstructible but not literal-reconstructible. Note that in the example $a_1$ is subsumed by $\{a_2\}$, and hence applying GSLE on the instance wrt $a_1$ would result in adding exactly the clause $(\neg a_1)$ into the instance.

The correctness of GSLE for MO-MaxSAT follows by observing that it can be viewed as the addition of a reconstructible clause.

**► Proposition 17.** If $l$ is subsumed in an MO-MaxSAT instance $\mathcal{I} = (F, O)$, then the clause $C = (\neg l)$ is reconstructible wrt $\mathcal{I}$.

**Proof.** Let $S \subset \mathcal{B}(\mathcal{I})$ be the group of literals that subsumes $l$, and $\tau \supset \neg C$ with $\tau(F) = 1$ a solution that falsifies $C$. Consider the witness $\omega = S \cup \{\neg l\}$ and the solution $\tau_\omega = (\tau \setminus \neg \omega) \cup \omega$. Since all clauses that $l$ appears in contain at least one literal $s \in S$ (condition (ii) of Definition 15) and all clauses that a negated literal from $S$ appears in also contain $\neg l$ (condition (iii) of Definition 15), $\tau_\omega$ is a solution to $F \wedge C$. Because $l$ (note that $\tau(l) = 1$) increases every objective more than all of $\omega$ (condition (i) of Definition 15), $\tau_\omega$ weakly dominates $\tau$. ▴
## 5.3 Preprocessing with Changes to Objectives

All techniques we have so far considered solely change the formula of an instance and not the objectives. However, towards practical preprocessing for MO-MaxSAT, we note that MaxSAT preprocessing techniques that may change the single objective in MaxSAT can also be lifted to MO-MaxSAT. These include unit propagation and equivalent literal substitution on objective literals, intrinsic at-most-ones, and binary core removal (BCR). Alike their MaxSAT counterparts, these liftings cannot be expressed directly as a sequence of additions and removals of redundant clauses due to the very fact that redundant clauses by definition do not change costs of instances.

**Unit Propagation on an Objective Literal.** In addition to removing all clauses containing $l$ and removing $\neg l$ from all clauses, unit propagation on an objective literal $l \in \mathcal{B}(\mathcal{I})$ replaces the terms $c_i(l) \cdot l$ with the respective constant $c_i(l)$ in each objective $O_i$ for $i = 1, \dots, p$. It is straightforward to see that by doing so costs of solutions are left unchanged.

**Equivalent Literal Substitution on Objective Literals.** An objective literal $l_1$ is replaced with another objective literal $l_1$ by equivalent literal substitution if $l_1$ and $l_2$ are equivalent – regardless of whether the literals or their negations appear in an objective. Specifically, every occurrence of $l_2$ (resp. $\neg l_2$) is replaced by $l_1$ (resp. $\neg l_1$) and in every objective $O_i$ ($i = 1, \dots, p$) $l_1$ (resp. $\neg l_1$) gets the coefficient $c_i(l_1) + c_i(l_2)$ (resp. $c_i(\neg l_1) + c_i(\neg l_2)$). In this way, the costs of solutions to the preprocessed instance are left unchanged.

**Intrinsic At-Most-One Technique [23, 24].** Lifted to MO-MaxSAT from MaxSAT, the intrinsic at-most-one technique works as follows. Given a set $L$ of objective literals at most one of which are falsified in each solution to $\mathcal{I}$ (i.e., at least $|L| - 1$ of the literals in $L$ will incur cost in all solutions; such an $L$ is sought heuristically using unit propagation), (i) a new literal $l_L$ is introduced, (ii) the clause $(l_L \lor \bigvee_{l \in L} \neg l)$ is added to $F$, and (iii) for every objective $O_i$ ($i = 1, \dots, p$) the coefficients of all literals in $L$ are reduced by the minimum of these coefficients $c_i^m = \min\{c_i(l) \mid l \in L\}$ and the terms $c_i^m \cdot l_L + (|L| - 1) \cdot c_i^m$ are added. For intuition, the preliminary condition implies that for any solution to $\mathcal{I}$, at least $|L| - 1$ of the literals in $L$ will incur cost at least $c_i^m$ wrt each of the objectives. The added clause (ii) enforces that $l_L$ must be true when all literals in $L$ are true, incurring additional cost $c_i^m$ wrt each of the objectives.

**Binary Core Removal (BCR) [19, 31].** BCR can be phrased as first applying a restriction of the intrinsic at-most-one technique and then applying BVE. In detail, assume that a set $L = \{l_1, l_2\}$ with $c_i(l_1) = c_i(l_2)$ for all objectives satisfies the condition required for the intrinsic-at-most-ones and that $\neg l_1$ and $\neg l_2$ do not appear in $F$. Then BCR can be viewed as an application of intrinsic at-most-ones on $L$ followed by applying BVE to eliminate $l_1$ and $l_2$ (in practice when the size of the instance does not increase). Thus, its correctness for MO-MaxSAT follows directly from the correctness of intrinsic at-most-ones and BVE.

# 6 Experiments

Complementing our theoretical observations on redundancy notions for MO-MaxSAT, we detail results from an empirical evaluation of the combined effect of the various MO-MaxSAT preprocessing techniques overviewed in the preceding section in terms of their ability to
18:12 Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization

reduce the size of real-world MO-MaxSAT instances and effect on runtime behaviour of
recent MO-MaxSAT solvers. To the best of our understanding, this is the first evaluation
on the effect of preprocessing on MO-MaxSAT instances and the runtime performance of
MO-MaxSAT solvers.

We extended the MaxSAT preprocessor MaxPre 2 [31, 24] to MaxPre 2.1, covering MO-MaxSAT. The preprocessor implementation, empirical data, and benchmarks are available via https://bitbucket.org/coreo-group/mo-prepro. As the technique specification for MaxPre 2.1 in the experiments we used [[uvsrgc]RTG], including unit propagation, BVE, SE, SSR, GSLE, BCR, TrimMaxSAT, FLE, ELS, and intrinsic at-most-ones.<fnref n="2" />

We consider four MO-MaxSAT solvers: LEXIMAXIST³ [10], BIOPTSAT⁴ [25], CLM⁵ [11], and SCUTTLE, our own implementation of a SAT-based approach based on enumerating so-called *P*-minimal models [40, 32]. BIOPTSAT, CLM, and SCUTTLE compute a Pareto-optimal solution for each element in the non-dominating set. BIOPTSAT is specific for MO-MaxSAT under two objectives (i.e., bi-objective MaxSAT), while SCUTTLE and CLM handle any number of objectives. LEXIMAXIST restricts to the simpler task of computing a leximax-optimal solution, which corresponds to computing a specific element in the non-dominated set [16]. As BIOPTSAT and LEXIMAXIST offer different configurations, for BIOPTSAT we consider the three central variants of a linear SAT-UNSAT based algorithm (denoted LSU), a core-guided (MSU3) algorithm (denoted CG), and a hybrid between the two that was found to perform best in [25] (denoted Hybrid). For LEXIMAXIST, we consider both a linear SAT-UNSAT and a core-guided version of the approach. For CLM we evaluate both the core-guided (denoted CG) and the implicit hitting set algorithm (denoted IHS). To achieve a tight integration, we included MaxPre 2.1 as a library into the source code of each solver. The modified source code of each solver is also available through https://bitbucket.org/coreo-group/mo-prepro.

We used three real-world benchmarks from the literature: package upgradeability (PackUP) [26], learning interpretable decision rules (LIDR) [37], and development assurance level (DAL) [6]. For PackUP we used the set of 3692 instances from [10], obtained from Mancoosi International Solver Competition (https://www.mancoosi.org/misc-2011/) instances using all combinations of 2–5 of the 5 original objectives. The 366 LIDR benchmark instances with two objectives originate from [25], encoding the classification task for public benchmark datasets. The 96 DAL benchmark instances originate from the LION9 challenge (https://www.cristal.univ-lille.fr/LION9/challenge.html), each with 7 objectives. The pseudo-boolean constraints in the DAL instances were encoded with a (generalized) totalizer encoding [2, 30].

All runtime experiments were executed on 2.60-GHz Intel Xeon E5-2670 machines with
64-GB RAM in RHEL under a 1.5-hour per-instance time and 16-GB memory limit. Times
reported include the runtimes of MaxPre 2.1 whenever preprocessing is used.

6.1 Effect of Preprocessing on Instance Characteristics

We first consider the effect of preprocessing on four central characteristics of MO-MaxSAT
instances: the number of variables, the number of clauses, the sum of objective coefficients,
and the number of Pareto-MCSes.

<footnote n="2">² We excluded BCE as using it in preliminary testing led to slightly worse runtimes overall.
³ LEXIMAXIST obtained from https://github.com/miguelcabral/leximaxIST.
⁴ BIOPTSAT obtained from https://bitbucket.org/coreo-group/bioptsat
⁵ CLM obtained from https://gitlab.inesc-id.pt/u001810/moco</footnote>
<figure><img src="image_157.png" /><figcaption>**Figure 1** Per-instance instance size reductions achieved by preprocessing.</figcaption></figure>

Figure 1 shows the reduction of variables (top left), number of clauses (top right), the sum of objective coefficients (bottom left), and the number of Pareto-MCSes (bottom right) obtained with MaxPre 2.1 for each of the three benchmark domains. The number of variables (Figure 1 top left) is reduced significantly on each benchmark domain. In terms of medians, after preprocessing 9.5% of the original variables remain for DAL, 32% for PackUP, and 64% for LIDR instances. In terms of clauses (Figure 1 top right), the reductions are very significant for both DAL and PackUP, with 9.3% and 24% of the original number of clauses remaining after preprocessing in terms of the median, respectively. For LIDR the number of clauses is reduced less significantly, although a reduction can still be observed; 93% of the original number of clauses remain.

Given an instance $\mathcal{I} = (F, (O_1, \dots, O_p))$, we measure the sum of objective coefficients, i.e., $\sum_{i=1}^p \sum_{l \in \mathcal{B}_i(\mathcal{I})} c_i(l)$. Note that preprocessing can change the sum of objective coefficients both by inferring that some objective literals can be set to 0 – conceptually decreasing the trivial upper bound on the objective – and by inferring that some literal must be assigned to 1 – conceptually increasing the lower bound. Figure 1 (bottom left) shows the reduction in the sum of objective coefficients achieved by preprocessing on each benchmark instance. The magnitude of reductions achieved by preprocessing depend significantly on the benchmark domain. For LIDR, preprocessing only seldom reduces objective coefficients. For PackUP a significant reduction is observed; the median sum of objective coefficients after preprocessing is 57% of the original. Furthermore, on 297 of the PackUP instances preprocessing reduced at least one of the objectives to zero, removing it from the instance. For DAL, while for some instances the objective coefficients are reduced only slightly, on every single instance preprocessing reduced at least one of the objectives to zero. The median sum of objective coefficients after preprocessing is 54% of the original for DAL.
18:14 Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization

<table><caption>Table 1 Solved instances (#), uniquely solved instances (uniq.), and cumulative runtimes over solved (Σt) in 10³ seconds, with and without preprocessing (Prepro.).</caption><thead><tr><th rowspan="2">Solver</th><th rowspan="2">Prepro.</th><th colspan="3">PackUP</th><th colspan="3">LIDR</th><th colspan="3">DAL</th></tr><tr><th>#</th><th>uniq.</th><th>Σt</th><th>#</th><th>uniq.</th><th>Σt</th><th>#</th><th>uniq.</th><th>Σt</th></tr></thead><tbody><tr><td rowspan="2">BIOPTSAT (LSU)<br>(bi opt.)</td><td>no</td><td>1134</td><td>0</td><td>61.4</td><td>220</td><td>1</td><td>52.4</td><td>-</td><td>-</td><td>-</td></tr><tr><td>yes</td><td><strong>1161</strong></td><td>27</td><td><strong>47.7</strong></td><td><strong>223</strong></td><td>4</td><td><strong>34.1</strong></td><td>-</td><td>-</td><td>-</td></tr><tr><td rowspan="2">BIOPTSAT (CG)<br>(bi opt.)</td><td>no</td><td>1154</td><td>1</td><td>40.9</td><td>222</td><td>1</td><td>43.9</td><td>-</td><td>-</td><td>-</td></tr><tr><td>yes</td><td><strong>1159</strong></td><td>6</td><td><strong>34.5</strong></td><td>222</td><td>1</td><td><strong>38.4</strong></td><td>-</td><td>-</td><td>-</td></tr><tr><td rowspan="2">BIOPTSAT (Hybrid)<br>(bi opt.)</td><td>no</td><td>1154</td><td>1</td><td>46.6</td><td>222</td><td>0</td><td>40.4</td><td>-</td><td>-</td><td>-</td></tr><tr><td>yes</td><td><strong>1159</strong></td><td>6</td><td><strong>33.0</strong></td><td>222</td><td>0</td><td><strong>35.5</strong></td><td>-</td><td>-</td><td>-</td></tr><tr><td rowspan="2">SCUTTLE<br>(multi opt.)</td><td>no</td><td>1772</td><td>40</td><td>284.5</td><td><strong>219</strong></td><td>1</td><td>51.3</td><td>66</td><td>0</td><td>5.9</td></tr><tr><td>yes</td><td><strong>1778</strong></td><td>46</td><td><strong>244.1</strong></td><td>218</td><td>0</td><td>44.1</td><td><strong>67</strong></td><td>1</td><td><strong>5.3</strong></td></tr><tr><td rowspan="2">CLM (CG)<br>(multi opt.)</td><td>no</td><td><strong>1593</strong></td><td>88</td><td><strong>301.3</strong></td><td>206</td><td>2</td><td><strong>48.0</strong></td><td><strong>60</strong></td><td>7</td><td><strong>8.1</strong></td></tr><tr><td>yes</td><td>1588</td><td>83</td><td>315.8</td><td>206</td><td>2</td><td>49.4</td><td>53</td><td>0</td><td>12.8</td></tr><tr><td rowspan="2">CLM (IHS)<br>(multi opt.)</td><td>no</td><td><strong>1301</strong></td><td>91</td><td>258.5</td><td><strong>134</strong></td><td>19</td><td>26.8</td><td><strong>48</strong></td><td>7</td><td>0.3</td></tr><tr><td>yes</td><td>1282</td><td>72</td><td>189.8</td><td>115</td><td>0</td><td>23.5</td><td>41</td><td>0</td><td>0.2</td></tr><tr><td rowspan="2">LEXIMAXIST (LSU)<br>(leximax opt.)</td><td>no</td><td>2276</td><td>2</td><td>434.6</td><td>224</td><td>0</td><td><strong>28.4</strong></td><td>72</td><td>0</td><td><strong>4.3</strong></td></tr><tr><td>yes</td><td><strong>2347</strong></td><td>73</td><td><strong>268.5</strong></td><td>224</td><td>0</td><td>29.6</td><td>72</td><td>0</td><td>5.2</td></tr><tr><td rowspan="2">LEXIMAXIST (CG)<br>(leximax opt.)</td><td>no</td><td>2450</td><td>13</td><td>140.7</td><td><strong>220</strong></td><td>2</td><td>43.7</td><td>72</td><td>1</td><td>12.9</td></tr><tr><td>yes</td><td><strong>2453</strong></td><td>16</td><td><strong>140.0</strong></td><td>218</td><td>0</td><td>38.0</td><td><strong>73</strong></td><td>2</td><td><strong>9.7</strong></td></tr></tbody></table>

For investigating how preprocessing affects the number of Pareto-MCSes, we used SCUTTLE to enumerate Pareto-MCSes of each benchmark instance under a 1.5-h per-instance time limit. On the LIDR instances, no reduction in the number of Pareto-MCSes was observed. For PackUP and DAL, respectively, preprocessing reduced the number of Pareto-MCSes significantly, by more than one third for 33% and 60% of the instances, respectively. Furthermore, considering the per-instance reduction shown in Figure 1 (bottom right), we observed that for PackUP the number of Pareto-MCSes is often reduced significantly further.

## 6.2 Effect of Preprocessing on Solver Runtimes

We now turn to investigating the effect of preprocessing on the runtime performance of MO-MaxSAT solvers.

Table 1 shows the number of solved instances, number of instances uniquely solved with or without preprocessing, and cumulative runtimes over solved instances (in 10³ seconds) for each solver. We emphasize that here one should focus on comparing the effect of preprocessing on each individual solver and configuration. Most importantly, the numbers reported for the four different solvers – BIOPTSAT, SCUTTLE, CLM, and LEXIMAXIST – are not directly comparable to each other as they solve different variants of MO-MaxSAT: LEXIMAXIST computes a solution corresponding to a single element in the non-dominated set, while BIOPTSAT, SCUTTLE, and CLM enumerate the whole non-dominated set. Furthermore, since BIOPTSAT supports two objectives only, data for BIOPTSAT on PackUP is restricted to the 1420 instances with two objectives, and data on DAL is unavailable as the DAL instances involve more than two objectives.
For PackUP, preprocessing has a clear positive impact on both the number of instances solved and the runtimes of all solvers except for CLM: the solvers use less cumulative runtime after preprocessing for solving more instances than what can be solved without preprocessing. We observe that for each of the three variants of BIOPTSAT as well as the LSU variant of LEXIMAXIST, preprocessing strictly increases the number of PackUP instances solved. There are close to no uniquely solved instances when preprocessing is not employed. Interestingly, the runtime improvement obtained using preprocessing for the LSU variants of BIOPTSAT, which without preprocessing is outperformed by the other BIOPTSAT variants, is so significant on PackUP instances that the LSU variant ends up even slightly outperforming the other variants. For SCUTTLE and the CG variant of LEXIMAXIST the number of uniquely solved instances with preprocessing is also higher than without, although there is a more significant number of instances that are uniquely solved without preprocessing. For LIDR, preprocessing speeds up all three configurations of BIOPTSAT and also increases the number of instances solved for the LSU variant. However, preprocessing does not consistently improve the performance of SCUTTLE, CLM, and LEXIMAXIST on LIDR and DAL.

Overall, although somewhat modestly, preprocessing appears to have the most signific-
ant positive impact on linear SAT-UNSAT type algorithms, namely, the LSU variants of
BIOPTSAT and LEXIMAXIST. This finding is in fact in-line with [24] where, in the con-
text of MaxSAT, the strongest positive impact of preprocessing was observed for a linear
SAT-UNSAT (solution-improving) MaxSAT solver.

Finally, we investigate potential correlations between the impact of preprocessing on solver runtimes and the instance characteristics of number of clauses, number of variables, sum of objective coefficients, and number of Pareto-MCSes. As a metric for the impact of preprocessing on solver runtimes, we use *relative solver performance*, defined for a fixed instance and solver as $(t_{\text{no prepro}} - t_{\text{prepro}})/(t_{\text{no prepro}} + t_{\text{prepro}})$, where $t_{(\text{no}) \text{ prepro}}$ is the solving time with (without) preprocessing. This metric takes values from -1 to 1. A positive value implies that runtime with preprocessing was shorter than without preprocessing, and the value 1 (value -1) means that the solver was able to solve the instance with (without) preprocessing, but timed out without (with) it; the closer to 1 (-1), the more significant a positive (negative) effect preprocessing has on overall runtime. As a metric for the impact of preprocessing on instance characteristics, we use *fraction remaining*. For a specific instance and instance characteristic, let $f_{(\text{no}) \text{ prepro}}$ be the value of the feature with (without) preprocessing. The fraction remaining is then $f_{\text{prepro}}/f_{\text{no prepro}}$, taking values from 0 to 1. For some intuition, the closer to 0 the value is, the more significantly preprocessing affects the instance characteristic: e.g., the value 0 for the number of clauses means that preprocessing removes all clauses from an instance, and a value of 0.5 (1) means that the preprocessed instance contains half as many (exactly as many) clauses as the original instance.

Figure 2 relates relative solver performance and the fractions remaining for the four
instance characteristics for each solver using the configuration the runtimes of which were
improved the most by preprocessing: BIOPTSAT (LSU), SCUTTLE, and LEXIMAXIST (LSU),
focusing on “non-trivial” instances with runtimes > 60 seconds either with or without
preprocessing. We observe that a lower fraction of variables remaining (Figure 2 top left),
clauses (top right), or objective coefficient sum (bottom left) by preprocessing often also
somewhat tends to result in faster solver runtimes (i.e., a higher relative performance of the
solver), especially for LEXIMAXIST. Interestingly, the data for the LSU variant of BIOPTSAT
as well as for SCUTTLE are quite scattered, with no clear correlations observed between
relative solver performance and changes in instance characteristics. Finally, we note that the
number of Pareto-MCSes appears to have little to no impact on the relative performance
18:16 Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization

<figure><img src="image_158.png" /><figcaption>Figure 2 Relating solver runtimes with instance characteristic.</figcaption></figure>

of these specific solvers. One possible explanation for this observation is that none of these specific solvers explicitly enumerate Pareto-MCSes in their search. On the other hand, based on the data, reducing the sum of the objective coefficients by preprocessing may be beneficial for solver performance; also in light of this developing further techniques that are capable of reducing the objective ranges appears to be an interesting direction for further work.

7 Conclusions

Motivated by recent advances in (Max)SAT-based approaches to multi-objective optimization, we proposed redundancy notions and liftings of MaxSAT preprocessing techniques for the multi-objective setting. We showed that the redundancy notions capture different preprocessing techniques, with the (in)ability to remove Pareto-MCSes as the underlying differentiating property. We provided a stand-alone preprocessor implementation of the preprocessing techniques, and empirically evaluated the impact of preprocessing in multi-objective MaxSAT. The preprocessor can significantly reduce the size of real-world multi-objective MaxSAT instances and also has in cases a positive effect on runtimes of current state-of-the-art multi-objective MaxSAT solvers. Interesting directions for future work include developing redundancy notions that can capture changes to objectives; more fine-grained analysis of preprocessing for the restricted case of leximax optimization; and empirical evaluation of preprocessing on further problem settings with varying instance properties such as different distributions of objective coefficients.
References

1 Fahiem Bacchus, Matti Järvisalo, and Ruben Martins. Maximum satisfiability. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, *Handbook of Satisfiability-Second Edition*, volume 336 of *FAIA*, chapter 24, pages 929–991. IOS Press, 2021. doi: 10.3233/FAIA201008.

2 Olivier Bailleux and Yacine Boufkhad. Efficient CNF encoding of boolean cardinality constraints. In Francesca Rossi, editor, *Principles and Practice of Constraint Programming—9th International Conference, CP*, volume 2833 of LNCS, pages 108–122. Springer, 2003. doi:10.1007/978-3-540-45193-8_8.

3 Anton Belov, António Morgado, and João Marques-Silva. SAT-based preprocessing for MaxSAT. In Kenneth L. McMillan, Aart Middeldorp, and Andrei Voronkov, editors, *Logic for Programming, Artificial Intelligence, and Reasoning—19th International Conference, LPAR*, volume 8312 of LNCS, pages 96–111. Springer, 2013. doi:10.1007/978-3-642-45221-5_7.

4 Jeremias Berg and Matti Järvisalo. Unifying reasoning and core-guided search for maximum satisfiability. In Francesco Calimeri, Nicola Leone, and Marco Manna, editors, *Logics in Artificial Intelligence—16th European Conference, JELIA*, volume 11468 of LNCS, pages 287–303. Springer, 2019. doi:10.1007/978-3-030-19570-0_19.

5 Jeremias Berg, Paul Saikko, and Matti Järvisalo. Subsumed label elimination for maximum satisfiability. In Gal A. Kaminka, Maria Fox, Paolo Bouquet, Eyke Hüllermeier, Virginia Dignum, Frank Dignum, and Frank van Harmelen, editors, *22nd European Conference on Artificial Intelligence, ECAI 2016*, volume 285 of *FAIA*, pages 630–638. IOS Press, 2016. doi:10.3233/978-1-61499-672-9-630.

6 Pierre Bieber, Remi Delmas, and Christel Seguin. DALculus—Theory and tool for development assurance level allocation. In Francesco Flammini, Sandro Bologna, and Valeria Vittorini, editors, *Computer Safety, Reliability, and Security—30th International Conference, SAFECOMP*, volume 6894 of LNCS, pages 43–56. Springer, 2011. doi:10.1007/978-3-642-24270-0_4.

7 Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors. *Handbook of Satisfiability—Second Edition*, volume 336 of *FAIA*. IOS Press, 2021. doi:10.3233/FAIA336.

8 Armin Biere, Matti Järvisalo, and Benjamin Kiesl. Preprocessing in SAT solving. In Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, editors, *Handbook of Satisfiability—Second Edition*, volume 336 of *FAIA*, chapter 9, pages 391–435. IOS Press, 2021. doi: 10.3233/FAIA200992.

9 Ronen I. Brafman. A simplifier for propositional formulas with many binary clauses. *IEEE Trans. Syst. Man Cybern. Part B*, 34(1):52–59, 2004. doi:10.1109/TSMCB.2002.805807.

10 Miguel Cabral, Mikolás Janota, and Vasco M. Manquinho. SAT-based leximax optimisation algorithms. In Kuldeep S. Meel and Ofer Strichman, editors, *25th International Conference on Theory and Applications of Satisfiability Testing, SAT*, volume 236 of LIPIcs, pages 29:1–29:19. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.SAT.2022.29.

11 João Cortes, Inês Lynce, and Vasco M. Manquinho. New core-guided and hitting set algorithms for multi-objective combinatorial optimization. In Sriram Sankaranarayanan and Natasha Sharygina, editors, *Tools and Algorithms for the Construction and Analysis of Systems, 29th International Conference, TACAS*, volume 13994 of LNCS, pages 55–73. Springer, 2023. doi:10.1007/978-3-031-30820-8_7.

12 Niklas Eén and Armin Biere. Effective preprocessing in SAT through variable and clause elimination. In Fahiem Bacchus and Toby Walsh, editors, *Theory and Applications of Satisfiability Testing, 8th International Conference, SAT*, volume 3569 of LNCS, pages 61–75. Springer, 2005. doi:10.1007/11499107_5.

13 Niklas Eén and Niklas Sörensson. Temporal induction by incremental SAT solving. In Ofer Strichman and Armin Biere, editors, *First International Workshop on Bounded Model Checking, BMC@CAV*, volume 89 of Electronic Notes in Theoretical Computer Science, pages 543–560. Elsevier, 2003. doi:10.1016/S1571-0661(05)82542-3.
18:18 Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization

14 Matthias Ehrgott. Efficiency and nondominance. In *Multicriteria Optimization (2. ed.)*, chapter 2, pages 23–64. Springer, 2005.

15 Matthias Ehrgott. Multiobjective combinatorial optimization. In *Multicriteria Optimization (2. ed.)*, chapter 8, pages 197–220. Springer, 2005.

16 Matthias Ehrgott. Other definitions of optimality—nonscalarizing methods. In *Multicriteria Optimization (2. ed.)*, chapter 5, pages 127–150. Springer, 2005.

17 Matthias Ehrgott and Xavier Gandibleux. A survey and annotated bibliography of multiobjective combinatorial optimization. *OR Spectr.*, 22(4):425–460, 2000. doi:10.1007/s002910000046.

18 Jon William Freeman. *Improvements to Propositional Satisfiability Search Algorithms*. PhD thesis, University of Pennsylvania, USA, 1995. UMI Order No. GAX95-32175.

19 James F. Gimpel. A reduction technique for prime implicant tables. In *5th Annual Symposium on Switching Circuit Theory and Logical Design, SWCT*, pages 183–191. IEEE Computer Society, 1964. doi:10.1109/SWCT.1964.4.

20 Andreia P. Guerreiro, João Cortes, Daniel Vanderpooten, Cristina Bazgan, Inês Lynce, Vasco M. Manquinho, and José Rui Figueira. Exact and approximate determination of the pareto front using minimal correction subsets. *Comput. Oper. Res.*, 153:106153, 2023. doi:10.1016/j.cor.2023.106153.

21 Marijn Heule, Matti Järvisalo, Florian Lonsing, Martina Seidl, and Armin Biere. Clause elimination for SAT and QSAT. *J. Artif. Intell. Res.*, 53:127–168, 2015. doi:10.1613/jair.4694.

22 Marijn J. H. Heule, Benjamin Kiesl, and Armin Biere. Strong extension-free proof systems. *J. Autom. Reason.*, 64(3):533–554, 2020. doi:10.1007/s10817-019-09516-0.

23 Alexey Ignatiev, António Morgado, and João Marques-Silva. RC2: an efficient maxsat solver. *J. Satisf. Boolean Model. Comput.*, 11(1):53–64, 2019. doi:10.3233/SAT190116.

24 Hannes Ihalainen, Jeremias Berg, and Matti Järvisalo. Clause redundancy and preprocessing in maximum satisfiability. In Jasmin Blanchette, Laura Kovács, and Dirk Pattinson, editors, *Automated Reasoning—11th International Joint Conference, IJCAR*, volume 13385 of LNCS, pages 75–94. Springer, 2022. doi:10.1007/978-3-031-10769-6_6.

25 Christoph Jabs, Jeremias Berg, Andreas Niskanen, and Matti Järvisalo. MaxSAT-based bi-objective boolean optimization. In Kuldeep S. Meel and Ofer Strichman, editors, *25th International Conference on Theory and Applications of Satisfiability Testing, SAT*, volume 236 of LIPIcs, pages 12:1–12:23. Schloss Dagstuhl—Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.SAT.2022.12.

26 Mikolás Janota, Inês Lynce, Vasco M. Manquinho, and João Marques-Silva. PackUp: Tools for package upgradability solving. *J. Satisf. Boolean Model. Comput.*, 8(1/2):89–94, 2012. doi:10.3233/sat190090.

27 Matti Järvisalo, Armin Biere, and Marijn Heule. Blocked clause elimination. In Javier Esparza and Rupak Majumdar, editors, *Tools and Algorithms for the Construction and Analysis of Systems, 16th International Conference, TACAS 2010*, volume 6015 of LNCS, pages 129–144. Springer, 2010. doi:10.1007/978-3-642-12002-2_10.

28 Matti Järvisalo, Armin Biere, and Marijn Heule. Simulating circuit-level simplifications on CNF. *J. Autom. Reason.*, 49(4):583–619, 2012. doi:10.1007/s10817-011-9239-9.

29 Matti Järvisalo, Marijn Heule, and Armin Biere. Inprocessing rules. In Bernhard Gramlich, Dale Miller, and Uli Sattler, editors, *Automated Reasoning—6th International Joint Conference, IJCAR*, volume 7364 of LNCS, pages 355–370. Springer, 2012. doi:10.1007/978-3-642-31365-3_28.

30 Saurabh Joshi, Ruben Martins, and Vasco M. Manquinho. Generalized totalizer encoding for pseudo-boolean constraints. In Gilles Pesant, editor, *Principles and Practice of Constraint Programming—21st International Conference, CP*, volume 9255 of LNCS, pages 200–209. Springer, 2015. doi:10.1007/978-3-319-23219-5_15.
31 Tuukka Korhonen, Jeremias Berg, Paul Saikko, and Matti Järvisalo. MaxPre: An extended MaxSAT preprocessor. In Serge Gaspers and Toby Walsh, editors, *Theory and Applications of Satisfiability Testing—20th International Conference, SAT*, volume 10491 of LNCS, pages 449–456. Springer, 2017. doi:10.1007/978-3-319-66263-3_28.

32 Miyuki Koshimura, Hidetomo Nabeshima, Hiroshi Fujita, and Ryuzo Hasegawa. Minimal model generation with respect to an atom set. In Nicolas Peltier and Viorica Sofronie-Stokkermans, editors, *7th International Workshop on First-Order Theorem Proving, FTP*, volume 556 of CEUR Workshop Proceedings. CEUR-WS.org, 2009. URL: http://ceur-ws.org/Vol-556/paper06.pdf.

33 Oliver Kullmann. On a generalization of extended resolution. *Discret. Appl. Math.*, 96-97:149-176, 1999. doi:10.1016/S0166-218X(99)00037-2.

34 Daniel Le Berre. Exploiting the real power of unit propagation lookahead. *Electron. Notes Discret. Math.*, 9:59–80, 2001. doi:10.1016/S1571-0653(04)00314-2.

35 Chu Min Li. Integrating equivalency reasoning into davis-putnam procedure. In Henry A. Kautz and Bruce W. Porter, editors, *Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence*, pages 291–296. AAAI Press / The MIT Press, 2000. URL: http://www.aaai.org/Library/AAAI/2000/aaai00-045.php.

36 Mark H. Liffiton and Karem A. Sakallah. Algorithms for computing minimal unsatisfiable subsets of constraints. *J. Autom. Reason.*, 40(1):1–33, 2008.

37 Dmitry Malioutov and Kuldeep S. Meel. MLIC: A maxsat-based framework for learning interpretable classification rules. In John N. Hooker, editor, *Principles and Practice of Constraint Programming—24th International Conference, CP*, volume 11008 of LNCS, pages 312–327. Springer, 2018. doi:10.1007/978-3-319-98334-9_21.

38 Richard Ostrowski, Éric Grégoire, Bertrand Mazure, and Lakhdar Sais. Recovering and exploiting structural knowledge from CNF formulas. In Pascal Van Hentenryck, editor, *Principles and Practice of Constraint Programming—8th International Conference, CP*, volume 2470 of LNCS, pages 185–199. Springer, 2002. doi:10.1007/3-540-46135-3_13.

39 Tobias Paxian, Pascal Raiola, and Bernd Becker. On preprocessing for weighted MaxSAT. In *Verification, Model Checking, and Abstract Interpretation, VMCAI*, volume 12597 of LNCS, pages 556–577. Springer, 2021.

40 Takehide Soh, Mutsunori Banbara, Naoyuki Tamura, and Daniel Le Berre. Solving multiobjective discrete optimization problems with propositional minimal model generation. In J. Christopher Beck, editor, *Principles and Practice of Constraint Programming—23rd International Conference, CP*, volume 10416 of LNCS, pages 596–614. Springer, 2017. doi:10.1007/978-3-319-66158-2_38.

41 Sathiamoorthy Subbarayan and Dhiraj K. Pradhan. NiVER: Non-increasing variable elimination resolution for preprocessing SAT instances. In Holger H. Hoos and David G. Mitchell, editors, *Theory and Applications of Satisfiability Testing, 7th International Conference, SAT*, volume 3542 of LNCS, pages 276–291. Springer, 2004. doi:10.1007/11527695_22.

42 Miguel Terra-Neves, Inês Lynce, and Vasco M. Manquinho. Introducing pareto minimal correction subsets. In Serge Gaspers and Toby Walsh, editors, *Theory and Applications of Satisfiability Testing—20th International Conference, SAT*, volume 10491 of LNCS, pages 195–211. Springer, 2017. doi:10.1007/978-3-319-66263-3_13.

43 Miguel Terra-Neves, Inês Lynce, and Vasco M. Manquinho. Multi-objective optimization through pareto minimal correction subsets. In Jérôme Lang, editor, *27th Joint Conference on Artificial Intelligence, IJCAI*, pages 5379–5383. ijcai.org, 2018. doi:10.24963/ijcai.2018/757.

44 Ekunda L. Ulungu and Jacques Teghem. Multi-objective combinatorial optimization problems: A survey. *Journal of Multi-criteria Decision Analysis*, 3:83–104, 1994.

45 Allen Van Gelder. Toward leaner binary-clause reasoning in a satisfiability solver. *Ann. Math. Artif. Intell.*, 43(1):239–253, 2005. doi:10.1007/s10472-005-0433-5.
18:20 Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization

46 Ramin Zabih and David A. McAllester. A rearrangement search strategy for determining propositional satisfiability. In Howard E. Shrobe, Tom M. Mitchell, and Reid G. Smith, editors, *Proceedings of the 7th National Conference on Artificial Intelligence*, AAAI, pages 155–160. AAAI Press / The MIT Press, 1988. URL: http://www.aaai.org/Library/AAAI/1988/aaai88-028.php.
# An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling

Carla Juvin [x]

LAAS-CNRS, Université de Toulouse, France

Emmanuel Hebrard [x]

LAAS-CNRS, Université de Toulouse, France

Laurent Houssin [x]

ISAE-SUPAERO, Université de Toulouse, France

Pierre Lopez [x]

LAAS-CNRS, Université de Toulouse, France

## Abstract

Constraint Programming has been widely, and very successfully, applied to scheduling problems. However, the focus has been on uninterruptible tasks, and preemptive scheduling problems are typically harder for existing constraint solvers. Indeed, one usually needs to represent all potential task interruptions thus introducing many variables and symmetrical or dominated choices.

In this paper, building on mostly known results, we observe that a large class of preemptive disjunctive scheduling problems do not require an explicit model of task interruptions. We then introduce a new constraint programming approach for this class of problems that significantly outperforms state-of-the-art dedicated approaches in our experimental results.

**2012 ACM Subject Classification** Theory of computation → Constraint and logic programming; Computing methodologies → Planning and scheduling

**Keywords and phrases** Constraint Programming, Scheduling, Preemptive Resources

**Digital Object Identifier** 10.4230/LIPIcs.CP.2023.19

**Supplementary Material** Software (Source Code): https://github.com/ehebrard/Mistral-2.0.git, archived at swh:1:dir:90fe19df244134e5dfddd79360cd4b554fecabfb

**Funding** Emmanuel Hebrard: ANR Project AD-Lib (ANR-22-CE23-0014).

**Acknowledgements** We would like to thank Claude-Guy Quimper for the advice and discussions while writing this paper.

## 1 Introduction

Many applications involve scheduling a set of tasks subject to resource constraints. Constraint programming (CP) techniques lead to significant advances in this domain and, conversely, some of the early work on the propagation of global constraints originated from scheduling applications.

In preemptive scheduling problems, the processing of some tasks can be interrupted, to be resumed at a later time. CP is generally much more successful on non-preemptive rather than preemptive scheduling problems. The standard approach to modelling interruptible tasks in constraint programming, while preserving completeness<fnref n="1" />, is to decompose each task into as many unit-length tasks as its duration. A disjunctive resource can then be modelled as an ALLDIFFERENT constraint, a parallel-machine resource as a GLOBALCARDINALITY

<figure><img src="image_159.png" /></figure>

<footnote n="1">¹ Without this restriction, the range of possible approaches is significantly wider.</footnote>
constraint, and a cumulative resource as a general flow constraint. Another approach is to decompose the tasks into variable-size tasks. In this case, either the duration variables have a null lower bound, which severely hinders constraint propagation, or constraints have to be posted on the number of fragments and their duration, which entails searching over the different ways to split the tasks. As a result, the former approach is often the best. In either cases, the complexity of the methods heavily depends on the duration of the tasks, and therefore do not scale well in practice.

In this paper, we use the observation that when preemptive resources are disjoint, there is no need to compute the fragmentation of the tasks during search. In other words, the problem can be modelled as a constraint satisfaction problem (CSP) with two variables per task: one for its start time and one for its end time. Deciding whether a set of interruptible tasks with release and due dates can be processed on a disjunctive constraint is easy (e.g., via the *Jackson Preemptive Schedule*). Moreover, if some tentative release and due dates for the tasks pass the *overload check*<fnref n="2" /> [29], then a feasible fragmentation of the tasks is guaranteed to exist. Therefore, provided that the disjunctive resources are *disjoint* and that constraint propagation is at least as strong as the overload check, one can simply branch on start and end time variables for every task.

This condition of disjointness is true in many problems, and there is no further restriction on the constraint graph. For instance in this paper we focus on the preemptive Job Shop Scheduling Problem (pJSSP). In this problem, the resources are naturally disjoint, but tasks requiring distinct machines can be linked by precedence constraints. Our method can be applied to several other preemptive versions of disjunctive scheduling problems (e.g., open shop scheduling where job sequences are to be decided, job shop scheduling augmented with setup times, or generalised precedences, etc.).

The paper is organised as follows: In Section 2 we recall some background and define the disjunctive preemptive constraint as well as the preemptive Job shop Scheduling problem. In Section 3 we briefly review the existing CP models for preemptive scheduling. We show that the standard approach of using the constraints ALLDIFFERENT or NOOVERLOAD on unit-length tasks are weaker than the same approach using the ALLDIFFPREC constraint. Then we discuss the main observations, which are not original, but are key to our main result: it is often not necessary to introduce unit-length tasks, and without unit-length tasks Edge-Finding is sufficient to enforce bounds consistency. Then we introduce a novel constraint model for the preemptive Job Shop Scheduling Problem based on these observations in Section 4 and finally we discuss the state of the art for the pJSSP and experimentally compare our approach to it in Section 5.

## 2 Background and Related Work

### 2.1 CSP and bounds consistency

A constraint network is a triple $(\mathbf{x}, \mathcal{D}, \mathbf{c})$ where $\mathbf{x}$ is a finite totally ordered set of variables, $\mathcal{D}$ is a finite set, and $\mathbf{c}$ is a finite set of constraints. A constraint $c$ is a pair $(S_c, P_c)$ where the scope $S_c$ is a subset of $\mathbf{x}$ and $P_c$ is a predicate on the variables $S_c$. An assignment $\sigma: \mathbf{x} \mapsto \mathcal{D}$ is a mapping from variables in $\mathbf{x}$ to values in $\mathcal{D}$, and $\sigma(x)$ denotes the value assigned to variable $x$ by $\sigma$. Given a constraint network $(\mathbf{x}, \mathcal{D}, \mathbf{c})$, the *Constraint Satisfaction Problem (CSP)* asks whether there is an assignment $\sigma$ of values in $\mathcal{D}$ to the variables $\mathbf{x}$ such that for every constraint $c \in \mathbf{c}$, the predicate $P_c$ is true on the projection of $\sigma$ onto $S_c$.

<footnote n="2">² That the total duration of any set of tasks is not larger than their execution window.</footnote>
Most constraint solvers store a current domain $D(x) \subseteq \mathcal{D}$ for every variable $x \in \mathbf{x}$ and use some form of consistency reasoning to reduce these domains without losing solutions. We assume that the domain $\mathcal{D}$ is totally ordered and denote $\min(x)$ (resp. $\max(x)$) the minimum (resp. maximum) value in $D(x)$. Moreover, we denote $[l, u]$ the discrete interval containing every element in $\mathcal{D}$ that is larger than or equal to $l$ and lower than or equal to $u$.

**► Definition 1 (Bounds Consistency).** Let $c$ be a constraint and $x \in S_c$ be a variable constrained by $c$. An assignment $\sigma$ is a bound support of the pair $(x, v)$ in a current domain $D$ if and only if:

- $\sigma(x) = v$;

- the predicate $P_c$ is satisfied by $\sigma$ ($\sigma$ is said to be consistent and we write $P_c(\sigma) = true$);

- and for every variable $y \in \mathbf{x} \setminus x$, $\sigma(y) \in [\min(y), \max(y)]$ ($\sigma$ is said to be valid).

A constraint $c$ is bounds consistent (BC) for the current domain $D$ if and only if, for every $x \in S_c$, $(x, \min(x))$ and $(x, \max(x))$ have a bound support in $D$.

A constraint network $\mathcal{N} = (\mathbf{x}, \mathcal{D}, \mathbf{c})$ is BC in a current domain $D$ if and only if, for every $c \in \mathbf{c}$, $c$ is BC in $D$.

The notion of consistency can be used to compare constraint models, and in particular compare constraints to their decompositions.

**► Definition 2 (Pruning power).** Let $c$ be a constraint and $\mathcal{N} = (\mathbf{x}, \mathcal{D}, \mathbf{c})$ be a decomposition of the constraint, i.e., a constraint network such that:

- $S_c \subseteq \mathbf{x}$ and

- $\sigma$ satisfies $P_c$ if and only if, there is a solution $\sigma'$ of $\mathcal{N}$ such that the projection of $\sigma'$ onto $S_c$ is equal to $\sigma$.

We say that BC on the decomposition $\mathcal{N}$ is as strong as BC on the constraint $c$ if for any current domain $D$, it holds that $\mathcal{N}$ is BC in $D$ implies $c$ is BC in $D$. Otherwise, we say that BC on the decomposition is weaker than on the constraint.

## 2.2 Preemptive Scheduling

The constraint PREEMPTIVENOOVERLAP ensures that a set of interruptible tasks requiring a disjunctive resource do not overlap. Let $\mathcal{T} = \{t_1, \dots, t_n\}$ be a set of tasks, and let $\mathbf{s} = \{s_1, \dots, s_n\}$ and $\mathbf{e} = \{e_1, \dots, e_n\}$ be two sets of variables standing respectively for the earliest start and latest end times of the tasks, i.e., a task $t_i \in \mathcal{T}$ must be processed in the interval $[s_i, e_i)$ (closed at the start and opened at the end). Notice that although we will often use the terms “start (or end) variable” for convenience, these variables actually define an interval in which the task is processed. In particular, task $t_j$ might not be processed at all at time $s_j$ and may be finished at a time strictly earlier than $e_j$. This is apparent in Definitions 3 and 4, and the reasons for this choice are discussed in Section 3.2.1.

Moreover, let $p_i$ be the duration of task $t_i$. For a set of tasks $\Omega \subseteq \mathcal{T}$, we write $s_{\Omega}$ for the earliest start time of any task in $\Omega$ ($s_{\Omega} = \min(\{s_i \mid t_i \in \Omega\})$), $e_{\Omega}$ for the latest end time of any task in $\Omega$ ($e_{\Omega} = \max(\{e_i \mid t_i \in \Omega\})$), and $p_{\Omega} = \sum_{t_i \in \Omega} p_i$ for the total processing time of tasks in $\Omega$. Since the tasks are interruptible, there must exist a “fragmentation” function that maps at most one task to each time point. Let $\mathcal{H} = [0, ub)$ be a time interval where ub is some upper bound on the end times of tasks in $\mathcal{T}$, and let $\mathbf{a} = \{a_{i,\tau} \mid t_i \in \mathcal{T}, \tau \in \mathcal{H}\}$ be Boolean activation variables, where $a_{i,\tau}$ indicates whether task $t_i$ is active at time $\tau$.
19:4 An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling

► **Definition 3.** *PREEMPTIVE NO OVERLAP (on activation variables)*

$$ \mathit{PREEMPTIVE\NOOVERLAP}(\mathcal{T}, \mathbf{a}, \mathbf{s}, \mathbf{e}) $$

⇔

$$ \forall \tau \in \mathcal{H} \sum_{t_i \in \mathcal{T}} a_{i, \tau} \le 1 \land \forall t_i \in \mathcal{T} \sum_{\tau=s_i}^{e_i-1} a_{i, \tau} = p_i $$

In this paper we consider the case where we do not make the fragmentation function explicit (via activation variables), but rather only care about the start and end times of the tasks, while only making sure that some fragmentation function exists. This leads to Definition 4:

► **Definition 4.** *PREEMPTIVE NO OVERLAP (on start and end variables)*

$$ \mathit{PREEMPTIVE\NOOVERLAP}(\mathcal{T}, \mathbf{s}, \mathbf{e}) $$

⇔

$$ \exists f : \mathcal{H} \mapsto \mathcal{T} \cup \{\emptyset\}, \forall t_i \in \mathcal{T}, |\{\tau \in [s_i, e_i) | f(\tau) = t_i\}| = p_i $$

2.3 Preemptive Job Shop Scheduling (pJSSP)

In the pJSSP, a set $\mathcal{J}$ of $n$ jobs are to be processed on a set $\mathcal{M}$ of machines. Each job $J_i \in \mathcal{J}$ consists of a sequence of $n_i$ tasks that must be executed in order. Each task $t_{i,j} \in J_i$ must be executed on one machine $M_{i,j} \in \mathcal{M}$ with a processing time $p_{i,j} \in \mathbb{N}$. Preemption is allowed, i.e. tasks can use a machine for some time, stop to let another task be processed, and then resume at a later time. The objective is to minimise the total makespan, that is, the maximum completion time of any task (denoted $C_{\max}$).

The pJSSP is NP-hard even with two machines and three jobs ($J_2|n = 3, pmtn|C_{\max}$) [7] while the non-preemptive version ($J_2|n = 3|C_{\max}$) is solvable in polynomial time; an $O(r^4)$-algorithm with $r = \max_{i \in \mathcal{J}} n_i$ in given in [22]. We have observed that in most academic data sets used to benchmark job shop scheduling algorithms, there is “no recirculation”, that is, jobs have exactly one task per machine. However, this particular case is also NP-hard for as few as three machines since it generalises the flow shop problem which is itself NP-hard [16]. The approach introduced in this paper applies to job shop problems with or without recirculation, although all the instances used in the experiments belong to the latter class.

3 Constraint Programming for Preemptive Scheduling

Many propagation algorithms for reasoning on resources for non-interruptible tasks rely on relaxing non-preemption, and can therefore be applied to the preemptive case with very few changes, as observed for instance in [24].

The Edge-Finding rule is of particular interest in the preemptive case. It relies on the overload check implied by the disjunctive resource constraint:

► **Definition 5.** *NO OVERLOAD*

$$ \mathit{NOOVERLOAD}(\mathcal{T}) \iff \bigwedge_{\Omega \subseteq \mathcal{T}} p_{\Omega} \le e_{\Omega} - s_{\Omega} $$

In the preemptive case, the overload check is not only implied, it is equivalent to the PREEMPTIVE NO OVERLAP constraint. The following theorem is a direct corollary of Proposition 3 in [8]:
► **Theorem 6.** $\mathit{PREEMPTIVENOOVERLAP}(\mathcal{T}, \mathbf{s}, \mathbf{e}) \iff \mathit{NOOVERLOAD}(\mathcal{T}, \mathbf{s}, \mathbf{e})$

The Edge-Finding rule consists in detecting precedence constraints whose violation would in turn make the overload check false. In the non-preemptive case, they are defined as shown in Definition 7. They are written here as constraints, but notice that they can be directly translated to a propagation rule by considering “optimistic” values for variables in the left-hand side (minima for start times and maxima for end times). Of course both constraints have a symmetric version (by reflection).

► **Definition 7.** Edge-Finding (non-preemptive case)

$$s_{\Omega \cup \{t_i\}} + p_i + p_{\Omega} > e_{\Omega} \implies s_i \ge s_{\Omega} + p_{\Omega} \quad \forall \Omega \subseteq \mathcal{T}, \forall t_i \in \mathcal{T} \setminus \Omega$$

A slight adaptation is required for the preemptive case [4]. The precondition implies that task $t_i$ must end last among $\Omega \cup \{t_i\}$, which is not equivalent to starting last since the task can be interrupted:

► **Definition 8.** Edge-Finding (Preemptive case)

$$s_{\Omega \cup \{t_i\}} + p_i + p_{\Omega} > e_{\Omega} \implies e_i \ge s_{\Omega \cup \{t_i\}} + p_i + p_{\Omega} \quad \forall \Omega \subseteq \mathcal{T}, \forall t_i \in \mathcal{T} \setminus \Omega$$

The following theorem is a direct corollary of Proposition 9 in [4] concerning fully elastic schedules. A fully elastic schedule is one where tasks are preemptive and do not have a constant demand on the resource when active (however, their total energy, i.e., total resource demand integrated over time, is a constant). On disjunctive resource, since the demand is an integer and can only be equal to 0 (inactive) or 1 (active), fully elastic schedules and preemptive schedules are equivalent. Interestingly, this theorem shows that other rules that are useful on non-preemptive scheduling (such as the “not-first/not-last” rule) are useless in the preemptive case.

► **Theorem 9.** Edge-Finding constraints are all bounds consistent on a set of tasks $\mathcal{T}$ if and only if $\mathit{PREEMPTIVENOOVERLAP}(\mathcal{T})$ is bounds consistent.

## 3.1 Formulation with fragmentation

It is easy to see Definition 4 is not sufficient when the same preemptive task requires more than a single (disjunctive) resource. Consider the instance illustrated in Figure 1a. Task $t_1$ requires resources a and b while tasks $t_2$ and $t_3$ require resource a, and $t_4$ and $t_5$ require resource b. All start and end times are fixed, and under Definition 4, the constraint $\mathit{PREEMPTIVENOOVERLAP}$ is satisfied both for the scope ($s_1, s_2, s_3, e_1, e_2, e_3$) and ($s_1, s_4, s_5, e_1, e_4, e_5$). However, there is no assignment of the variables $\mathbf{a} = a_{1,0}, \dots, a_{1,5}$ which satisfies both constraints under Definition 3. In this section we review the existing formulations of the disjunctive constraint that model task fragmentation.

A standard way to model preemptive resources is to decompose each task $t_i$ into $p_i$ unit-length tasks, where variable $x_{i,k}$ stands for the processing time of the k-th unit of task $t_i$. Then a disjunctive resource can be represented as an ALLDIFFERENT constraint:

► **Definition 10.** ALLDIFFERENT decomposition of $\mathit{PREEMPTIVENOOVERLAP}$ (w.r.t. Definition 3)

$$\mathit{PREEMPTIVENOOVERLAP}(\mathcal{T}, \mathbf{a}, \mathbf{s}, \mathbf{e}) \iff \mathit{ALLDIFFERENT}(\{x_{i,k} \mid t_i \in \mathcal{T} \ \forall k \in [0, p_i]\}) \quad (1)$$

$$\forall t_i \in \mathcal{T} \ \forall k \in [0, p_i) \ \forall \tau \in \mathcal{H} \qquad x_{i,k} = \tau \iff a_{i,\tau} \quad (2)$$

$$\forall t_i \in \mathcal{T} \ \forall k \in [0, p_i) \qquad s_i \le x_{i,k} < e_i \quad (3)$$
19:6 An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling

<table><thead><tr><th></th><th>p<sub>i</sub></th><th>s<sub>i</sub></th><th>e<sub>i</sub></th><th>Res.</th></tr></thead><tbody><tr><td>t<sub>1</sub></td><td>3</td><td>0</td><td>6</td><td>a and b</td></tr><tr><td>t<sub>2</sub></td><td>1</td><td>1</td><td>2</td><td>a</td></tr><tr><td>t<sub>3</sub></td><td>1</td><td>3</td><td>4</td><td>a</td></tr><tr><td>t<sub>4</sub></td><td>1</td><td>2</td><td>3</td><td>b</td></tr><tr><td>t<sub>5</sub></td><td>1</td><td>4</td><td>5</td><td>b</td></tr></tbody></table>

(a) with vs. without fragmentation

<table><thead><tr><th></th><th>p<sub>i</sub></th><th>s<sub>i</sub></th><th>e<sub>i</sub></th></tr></thead><tbody><tr><td>t<sub>1</sub></td><td>2</td><td>0</td><td>3</td><td>2</td><td>5</td></tr><tr><td>t<sub>2</sub></td><td>2</td><td>0</td><td>3</td><td>2</td><td>5</td></tr><tr><td>t<sub>3</sub></td><td>2</td><td>0</td><td>5</td><td>2</td><td>7</td></tr></tbody></table>

(b) ALLDIFFERENT decomposition

Figure 1 An example showing that activation variables are necessary when a task requires several distinct resources (Figure 1a), and an example showing that the decomposition using the ALLDIFFERENT constraint hinders propagation (Figure 1b).

A similar decomposition holds for the constraint PREEMPTIVENOOVERLAP(s, e) when we ignore the activation variables, and hence Constraint (2).

These two decompositions hinder propagation, i.e., BC on the decomposition is not equivalent to BC on the global constraint.

**Theorem 11.** *Bounds consistency on Constraints 1, 2 and 3 is weaker than bounds consistency on PREEMPTIVENOOVERLAP($\mathcal{T}$, s, e).*

*Proof.* Consider the three tasks shown in Figure 1b. The ALLDIFFERENT constraint has 6 variables in both decompositions, and there is no Hall interval and hence is BC. Therefore, the channelling constraints are also BC. Yet the values 2 to 5 are not BC for $e_3$ in the global constraint, since that would produce an overload in the interval $[0, 5)$. ◀

The decomposition is weaker because the $p_i$ units of task $t_i$ are interchangeable. Indeed we may add the following symmetry breaking constraints:

$$ \forall t_i \in \mathcal{T} \quad \forall k \in [1, p_i) \qquad x_{i,k-1} < x_{i,k} \qquad (4) $$

However, there is a quadratic algorithm to achieve BC on the conjunction of an ALLDIFFERENT constraint and a set of binary precedence constraints (the ALLDIFFPREC constraint [5]), and which therefore be used to achieve BC on the conjunction of Constraints 1 and 4. Let this formulation be “the ALLDIFFPREC decomposition”.

**Theorem 12.** *Bounds consistency on the ALLDIFFPREC decomposition is as strong as bounds consistency on PREEMPTIVENOOVERLAP($\mathcal{T}$, s, e).*

*Proof.* Let $\mathcal{T}$ be a set of tasks with start and end variables s, e, and suppose that PREEMPTIVENOOVERLAP($\mathcal{T}$, s, e) is not BC. Then there exists a task $t_i \in \mathcal{T}$ whose upper bound is not BC. By Theorem 6, it means that there exist $v \le \max(e_i)$ and $\Omega \subset \mathcal{T}$ such that $p_\Omega + p_i > \max(e_\Omega, v) - \min(s_\Omega, \min(s_i))$. Now, consider the assignment $x_{i,p_i} \leftarrow v$ in the decomposition. In order to satisfy the precedences $x_{i,k-1} < x_{i,k}$ for $k \in [1, p_i)$, all these variables must take values less than or equal to $v$. Therefore, in the decomposition, there are $p_\Omega + p_i$ variables which must take a value in the interval $[\min(s_\Omega, \min(s_i)), \max(e_\Omega, v))$ which is unfeasible. It follows that the assignment $x_{i,p_i} \leftarrow v$ is not BC for the ALLDIFFPREC constraint. ◀

This decomposition, however, requires $O(N)$ variables with $N = \sum_{t_i \in \mathcal{T}} p_i$, and BC can be achieved in $O(N^2)$ time. However, it can be achieved in a time complexity that does not depend on $N$ by direct application of Theorem 9. Indeed, there are algorithms
in $O(n \log n)$ [29] or even in linear time (after sorting) [13] to achieve BC on at least one Edge-Finding constraint. Moreover, since there are at most $n^2$ precedences to enforce, achieving BC on the PREEMPTIVENOOVERLAP constraint can be done in time polynomial in $n$ only.<fnref n="3" />

## 3.2 Formulation without fragmentation

When resources are disjoint, that is, when no task requires more than a single resource, then the problem can be modelled without representing task fragmentation. Indeed, Definition 4 ensures that a fragmentation such that no two tasks requiring that resource are processed simultaneously, and each task $t_i$ is processed within the time interval $[s_i, e_i)$, in other words, we have:

$$ \exists \mathbf{a} \ \mathrm{PREEMPTIVENOOVERLAP}(\mathcal{T}, \mathbf{a}, \mathbf{s}, \mathbf{e}) \iff \mathrm{PREEMPTIVENOOVERLAP}(\mathcal{T}, \mathbf{s}, \mathbf{e}) $$

Therefore, when activation variables ($\mathbf{a}$) are not constrained otherwise, the two formulations are equivalent.

Checking this constraint can be done efficiently: the Jackson Preemptive Schedule algorithm [9, 18] finds a fragmentation, or proves that none exists in $O(n \log n)$ time. Moreover, Theorem 6 entails that one does not need to find a witness fragmentation if the constraint propagation of the disjunctive constraint involves the overload check.

### 3.2.1 Monotonicity

Notice that the definition of the PREEMPTIVENOOVERLAP constraint does not force a task $t_i$ to be in process at time $s_i$, nor at time $e_i - 1$. In other words, start and end times are simply bounds within which the task can be processed. It follows that this constraint is monotonic: decreasing the start time of a task (or increasing its end time) in a satisfying assignment can never make this assignment inconsistent.

**Definition 13 (Monotonic constraints).** Let $\sigma_{x \leftarrow v}$ be the assignment that associates value $v$ to variable $x$ and that is equal to $\sigma$ otherwise. We say that a constraint $c$ is monotonic with respect to a function $f: \mathbf{x} \times \mathcal{D} \to \mathcal{D}$ if and only if:

$$ P_c(\sigma) = true \implies (\forall x \in S_c, P_c(\sigma_{x \leftarrow f(x, \sigma(x))}) = true) $$

**Lemma 14.** The constraint $\mathrm{PREEMPTIVENOOVERLAP}(\mathcal{T}, \mathbf{s}, \mathbf{e})$ is monotonic with respect to any function that is non-increasing for start-time variables, or non-decreasing for end-time variables.

**Proof.** The fragmentation of a task remains valid if its start time is decreased or its end time is increased. ◀

**Corollary 15.** If the constraint $\mathrm{PREEMPTIVENOOVERLAP}(\mathcal{T}, \mathbf{s}, \mathbf{e})$ is satisfiable, then, for any $t_i \in \mathcal{T}$, the assignments $s_i \leftarrow \min(s_i)$ and $e_i \leftarrow \max(e_i)$ are bounds consistent.

**Proof.** If the constraint is satisfiable, there exists a consistent and valid assignment, and by Lemma 14, changing the value of $s_i$ to $\min(s_i)$ (resp. $e_i$ to $\max(e_i)$) is a non-increasing (resp. non-decreasing) operation and hence yields a consistent and valid assignment. ◀

<footnote n="3">³ In practice a fix-point can be reached in far fewer iterations.</footnote>
19:8 An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling

There are two consequences to the PREEMPTIVE NO OVERLAP constraint being monotonic.

Firstly, achieving bounds consistency on the PREEMPTIVE NO OVERLAP constraint can only prune the upper (resp. lower) bound of the start (resp. end) time variables. However, bounds of end time variables could be pruned beyond BC without losing solutions. For instance, assume that task $t_i$ is such that $s_i = 0, e_i = 3$ and $p_i = 3$. Clearly, this task requires the resource on the whole interval $[0, 3)$ and therefore no other task can start at a time point earlier than 3. This corresponds to achieving BC on a restriction of Definition 4 where we constrain every task $t_j \in \mathcal{T}$ to be in process at time $s_j$ and at time $e_j - 1$. We have experimented with this formulation, and BC can be achieved in the same time complexity as enforcing Edge-Finding, using a slight generalisation of the propagation algorithm for BC on the ALL DIFFERENT constraint [27]. However, besides complexifying the definitions and the algorithm, it turns out that achieving this extra pruning is counter-productive, at least on pJSSP benchmarks.

Secondly, in the job shop scheduling problem, the only constraints besides disjunctive resources are the chain of precedences to represent the job sequences. Therefore, the start time of a task can always be extended to the end time of the previous task on that job (or to 0 if it is the first task) without invalidating the schedule. Similarly, its end time can be extended to the start time of the next task in that job. As a result, we can assume that a task ends exactly when the next task of its job starts and forbid any idle gap between the tasks of a job.

4 A Constraint Programming Approach to pJSSP

From the observation made in Section 3.2, we can propose the following constraint model for the preemptive job shop scheduling problem, with $s_{i,j}$ (resp. $e_{i,j}$) standing for the start (resp. end) variable associated to the j-th task of job i, and with $\mathcal{T} = \{t_{i,j} | J_i \in \mathcal{J}, \forall j \in [1, n_i)\}$.

$$ \min C_{\max} \qquad (5) $$

$$ \text{s.t.} \quad C_{\max} \geq e_{i,n_i} \quad \forall J_i \in \mathcal{J} \qquad (6) $$

$$ e_{i,j} \geq s_{i,j} + p_{i,j} \quad \forall J_i \in \mathcal{J}, \forall j \in [1, n_i] \qquad (7) $$

$$ e_{i,j} \leq s_{i,j+1} \quad \forall J_i \in \mathcal{J}, \forall j \in [1, n_i) \qquad (8) $$

$$ \text{PREEMPTIVE NO OVERLAP}(\mathcal{T}_m, \mathbf{s}_m, \mathbf{e}_m) \quad \forall m \in \mathcal{M} \qquad (9) $$

The objective variable $C_{\max}$ represents the makespan, that is, the maximum completion time of any task (Constraint 6). Constraints 7 and 8 encode respectively the durations of the task, and the job sequences. As discussed in this section, Constraints 9 (with $\mathcal{T}_m = \{t_{i,j} | M_{i,j} = m, J_i \in \mathcal{J}\}$, $\mathbf{s}_m = \{s_{i,j} | t_{i,j} \in \mathcal{T}_m\}$ and $\mathbf{e}_m = \{e_{i,j} || t_{i,j} \in \mathcal{T}_m\}$) are sufficient to ensure that a preemptive schedule exists, and can be computed efficiently once all start and end time variables are fixed.

Moreover, because of Corollary 15, we know that extending the end time of a task cannot violate the resource constraints. Since the only other constraints are chains of precedences, extending the end time of task up to the start time of the next task in its job (or extending its start time to the end time of the preceding task in the job) cannot violate any constraint.

We can therefore replace Constraints 6 and 7 with the following constraints:

$$ s_{i,0} = 0 \quad \forall i \in \mathcal{J} \qquad (10) $$

$$ e_{i,j} = s_{i,j+1} \quad \forall i \in \mathcal{J}, \forall j \in [1, n_i) \qquad (11) $$

$$ e_{i,n_i} = C_{\max} \quad \forall i \in \mathcal{J} \qquad (12) $$
Constraints 10 and 12 force the start (resp. end) time of the first (resp. last) task of every job to be equal to 0 (resp. the makespan), and Constraint 11 ensures that there is no gap between the end of a task and the start of the next task on its job. With these constraints, dominated solutions that leave a gap between two consecutive tasks of the same job are pruned out.

# 5 Experimental Results

In this section we compare our approach with the state-of-the-art approaches for the pJSSP. We first describe the two comparison methods: a recent dedicated branch-and-bound algorithm and the commercial solver CP Optimizer.

## 5.1 State-of-the-art Approaches

Most solution methods for the pJSSP are approximation algorithms [3, 15, 20] and heuristics [31]. Among the exact methods, Dantzig [10] introduced a linear programming model based on time index. Le Pape and Baptiste [24, 25] proposed a branch-and-bound procedure using classical constraint propagation techniques (timetable, disjunctive constraints and Edge-Finding) extended to preemptive problems. Ebadi and Moslehi have recently proposed two exact solution methods for the pJSSP, a mixed-integer programming (MIP) approach [11], and a dedicated branch-and-bound algorithm [12]. As our method, the MIP model requires no activation variable. It only involves variables for the start and times of the tasks, with the same guarantee that feasible (resp. optimal) solutions of this MIP correspond to feasible (resp. optimal) complete schedules, which task fragmentation can be computed e.g., via application of the Jackson's preemptive algorithm. However, in order to guarantee that the overload check is satisfied for a given resource, the model involves a set of linear constraints of size exponential in the number of tasks requiring this resource. This MIP model is less efficient than the dedicated branch-and-bound method proposed by the same authors, and hence we used the latter as reference in our experimental evaluation.

We do not compare with the recent method introduced in [21] in our experiments since this approach deals with the more general preemptive *and flexible JSSP*. It uses a logic-based Benders decomposition that splits the problem into a master problem of assigning operations to machines and into non-flexible pJSSP subproblems. The master problem is solved by mixed-integer programming while the subproblems are solved by existing approaches, such as the one introduced in this paper.

### 5.1.1 Dedicated Branch-and-Bound

Ebadi and Moslehi's branch-and-bound procedure [12] employs a depth-first search strategy to explore the set of feasible schedules without *proactively* creating unit-length tasks.

However, since the propagation in their method is not as strong as the overload check, a different technique is used to ensure that the produced schedule follows the Jackson's preemptive rule on each machine: unit-length tasks are created lazily when branching. In the search tree, each node represents a partial schedule with a set of already scheduled unit-length tasks and a disjunctive graph representing the current precedence relations. At the root node, the set of scheduled tasks is empty, and the arcs of the graph are only the precedences between the tasks of the same job. At each decision point, the machine processing the non-scheduled unit-length task with the smallest availability date is selected. The branching strategy consists in creating a node for each such task on this machine, with
19:10 An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling

this task scheduled at its earliest possible start time. Moreover, dominance rules ensure that many unit-length tasks can be created and added to the partial schedule at once as edges in the disjunctive graph. Lower bounds are computed at each node, based on the disjunctive graph, for pruning the search tree.

This method improved the state of the art for this problem at time of publication, and in particular Le Pape and Baptiste's CP model. It was the first to solve large instances (up to 50 jobs and 10 machines) to optimality. To our knowledge, this is currently the most efficient method to solve the pJSSP problem.

5.1.2 CP Optimizer model

IBM CP Optimizer solver is the most efficient off-the-shelf tool in many scheduling problems. We describe in this section the standard model for the preemptive job shop scheduling problem in CP Optimizer.

CP Optimizer allows the use of specific decision variables and constraints. In particular, interval variables can be used to represent the time during which a task is processed. Interval variables are defined by a start value, an end value and a size, which are the decision variables of the problem. We denote $t_{i,j}$ this interval variable, whose start and end time variables correspond to $s_i$ and $e_i$ respectively. Moreover, in this model, each preemptive task is divided into unit-length parts. Therefore, for each task $t_{i,j}$, we introduce $p_{i,j}$ unit-length interval variables $x_{i,j,k}$ with $k \in [1, p_{i,j}]$ besides the interval variable $t_{i,j}$.

The problem is described as follows:

$$ \min C_{\max} \qquad (13) $$

$$ \text{s.t.} \quad C_{\max} \geq e_{i,n_i} \quad \forall J_i \in \mathcal{J} \qquad (14) $$

$$ \text{EndBeforeStart}(t_{i,j}, t_{i,j+1}) \quad \forall J_i \in \mathcal{J}, \forall j \in [1, n_i) \qquad (15) $$

$$ \text{EndBeforeStart}(x_{i,j,k}, x_{i,j,k+1}) \quad \forall J_i \in \mathcal{J}, \forall j \in [1, n_i], \forall k \in [1, p_{i,j}) \qquad (16) $$

$$ \text{Span}(t_{i,j}, x_{i,j,k} : \forall k \in [1, p_{i,j}]) \quad \forall J_i \in \mathcal{J}, \forall j \in [1, n_i] \qquad (17) $$

$$ \text{NOOVERLAP}(x_{i,j,k} : \forall J_i \in \mathcal{J}, \forall j \in [1, n_i], \forall k \in [1, p_{i,j}] | M_{i,j} = m) \quad \forall m \in \mathcal{M} \qquad (18) $$

The objective function (13) is to minimise the makespan. Constraints (14) define the makespan. The global constraint `EndBeforeStart` is used to model the precedence constraints, as in the two following constraint sets. Constraints (15) ensure that the tasks of the same job will be processed with respect to the job sequence. Constraints (16) aim at ordering the parts of the task and so avoid symmetries, and ensure that each part is treated one after the other. With the `Span` global constraint, Constraints (17) are used to ensure that task interval spans over all its processing parts (i.e., each task starts with its first part and ends with its last part). With the `NOOVERLAP` global constraint, Constraints (18) forbid the overlapping of tasks processed on the same machine. We denote this model $CPO^{p=1}$, and we experimented with several variants of this models where a task $t_j$ is cut in fewer than $p_j$ pieces. These variants are sound but incomplete: the optimal schedule on these models is feasible but not necessarily optimal for the original problem. However, the idea is that they should be easier to solve and hopefully approximate the optimal solution.

- $CPO^{p=\ell}$ refers to the model where each task $t_{i,j}$ is cut into $\lfloor \frac{p_{i,j}}{\ell} \rfloor$ subtasks of duration $\ell$ and one task of duration $p_{i,j} \mod \ell$.

- $CPO^{n=\ell}$ refers to the model where each task $t_{i,j}$ is cut into $\ell$ tasks of variable duration but whose total is constrained to be $p_{i,j}$ (Constraint 19).
$$ \sum_{k=1}^{\ell} \text{sizeOf}(x_{i,j,k}) = p_{i,j} \quad \forall J_i \in \mathcal{J}, \forall j \in [1, n_i] \qquad (19) $$

To avoid symmetries, we made sub-task interval variables optional and add the following constraints:

$$ \text{PresenceOf}(x_{i,j,k+1}) \implies \text{PresenceOf}(x_{i,j,k}) \quad \forall J_i \in \mathcal{J}, \forall j \in [1, n_i], \forall k \in [1, \ell) \quad (20) $$

$$ \text{EndOf}(x_{i,j,k}) < \text{StartOf}(x_{i,j,k+1}) \quad \forall J_i \in \mathcal{J}, \forall j \in [1, n_i], \forall k \in [1, \ell) \quad (21) $$

Constraints (20) ensure that a sub-task can only be present if the previous sub-task is also present. Constraints (21) guarantees that two successive pieces of the same task do not immediately follow each other (a task is split only if it has preemption).

Interestingly, the CP Optimizer model using the constraint ALLDIFFERENT (as shown in Definition 10, with the symmetry breaking Constraints 4) instead of NOOVERLAP turned out to be much less efficient in our experiments.<fnref n="4" /> This is surprising because the latter constraint is more general and yet equivalent when tasks are unit-length. We conjecture that this could be explained by some hidden preprocessing in CP Optimizer.

## 5.2 Experimental protocol

We used some standard benchmark instances available in the literature [1, 2, 14, 23, 28]. These instances were proposed for the JSSP without preemption, but are often used in the preemptive case as well. Characteristics of these benchmarks are summarised in Table 1. For each benchmark, we report the number of instances (63 in total) that compose it, the size of these instances (number of jobs × number of machines) as well as the intervals the processing times are generated from. Detailed information on these instances is presented in [19].

All experiments were performed on three cluster nodes with Intel Xeon E5-2695 v4 CPU at 2.1 GHz with a 1 hour time cutoff. The branch-and-bound algorithm is implemented in C++, the exact CPO<sup>p=1</sup> model and all of its variants (CPO<sup>p=ℓ</sup> and CPO<sup>n=ℓ</sup> for ℓ ∈ {3, 10}) are implemented with the C++ interface of CP Optimizer 12.10.

Our approach was implemented in C++ using MISTRAL [17]<sup>5</sup> with the following search strategy (corresponding to the default settings): the variable ordering uses the minimal ratio between domain size and weighted degree heuristic [6], with an exponential decay on the weights of 0.96 and with the last conflict procedure [26]. The value ordering uses binary branching with the constraints $x \le \lfloor \min(x) + \max(x) \rfloor/2$ and $x > \lfloor \min(x) + \max(x) \rfloor/2$, and a geometric restart policy [30] starting at 200 fails and increasing by a factor 1.05.

## 5.3 Numerical results

Figure 2a shows how many instances are optimally solved by each method as a function of time. We include the results of the incomplete variants (dashed lines) although these proofs are weaker: they show that there is no better solution for the restricted model. Nonetheless, CPO<sup>p=ℓ</sup> obtains fewer such proofs for ℓ < 10, and CPO<sup>n=ℓ</sup> can only prove a single instance.

<footnote n="4">⁴ Hence we only report results for the best model using NOOVERLAP.</footnote>

<footnote n="5">⁵ The source code of MISTRAL is available here: https://github.com/ehebrard/Mistral-2.0 and features the model used in our experiments.</footnote>
19:12 An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling

<table><caption>Table 1 JSSP instances characteristics.</caption><thead><tr><th>Data set</th><th>Reference</th><th>Number of instances</th><th>Sizes</th><th>Processing times</th></tr></thead><tbody><tr><td>ft6,10,20</td><td>[14]</td><td>3</td><td>6× 6, 10× 10, 20× 20<br>10× 5, 15× 5, 20× 5,</td><td>[1,10],[1,99]</td></tr><tr><td>la01-40</td><td>[23]</td><td>40</td><td>10× 10, 15× 10, 20× 10,<br>30× 10, 15× 15</td><td>[5,99]</td></tr><tr><td>abz5-9</td><td>[1]</td><td>5</td><td>10× 10, 20× 15</td><td>[50,100], [25,100], [11,40]</td></tr><tr><td>orb1-10</td><td>[2]</td><td>10</td><td>10× 10</td><td>[5,99]</td></tr><tr><td>swv16-20</td><td>[28]</td><td>5</td><td>50× 10</td><td>[1,100]</td></tr></tbody></table>

Essentially, among exact methods, CP Optimizer ($CPO^{p=1}$) solves far fewer instances than other methods in the time available and is slower on the instances it does solve. For the easiest 50% of instances, both the branch-and-bound method (B&B) and MISTRAL can solve them quickly, in about 10 seconds. For the other instances, MISTRAL is faster and manages to solve 80% of the instances to optimality against 60% for the branch-and-bound.

<figure><img src="image_160.png" /><figcaption>(a) Number of solved instances over time.</figcaption></figure>

<figure><img src="image_161.png" /><figcaption>(b) Gap over time.</figcaption></figure>

<caption>Figure 2 Number of proofs and gap to the best overall solution over time. Dashed lines correspond to incomplete methods.</caption>

Figure 2b shows the average gap to the best known solution over time for MISTRAL and four approximate methods namely $CPO^{p=3}$, $CPO^{p=10}$, $CPO^{n=3}$ and $CPO^{n=10}$. We observe that none of these variants can find better solutions than MISTRAL, even considering a short calculation time. We also notice that the variants that considers fixed subtasks duration ($CPO^{p=\ell}$) are more efficient than the variant that considers a fixed number of subtasks ($CPO^{n=\ell}$) and that for these two variants, the fewer the subtasks, the more efficient is the method. In fact $CPO^{p=10}$ finds better solutions than MISTRAL on two instances: abz7 and abz8.

Results on individual instances are reported in Table 2. Our approach is better than the branch-and-bound on all but one instance: orb01 where the latter method proves optimality in 2118 seconds whereas MISTRAL does not return a proof within one hour. Moreover, within the one hour cutoff, it finds the best solution over all of the methods considered in these experiments on all but two of the instances, for which approximate models are more efficient.
<table><caption>Table 2 Results on every benchmark instance, proven optimal schedules are marked with a “*”, best $C_{max}$ are in **bold font**.</caption><thead><tr><th rowspan="2">Inst.</th><th colspan="2">MISTRAL</th><th colspan="2">B&B</th><th colspan="2">CPO<sup>p=1</sup></th><th colspan="2">CPO<sup>p=10</sup></th><th colspan="2">CPO<sup>n=3</sup></th></tr><tr><th>C<sub>max</sub></th><th>time (s)</th><th>C<sub>max</sub></th><th>time (s)</th><th>C<sub>max</sub></th><th>time (s)</th><th>C<sub>max</sub></th><th>time (s)</th><th>C<sub>max</sub></th><th>time (s)</th></tr></thead><tbody><tr><td>abz5</td><td><b>1203</b>*</td><td>213.22</td><td>1212</td><td>3600.00</td><td>1299</td><td>3600.00</td><td>1204</td><td>817.51</td><td>1266</td><td>3600.00</td></tr><tr><td>abz6</td><td><b>924</b>*</td><td>27.28</td><td><b>924</b>*</td><td>185.14</td><td>961</td><td>3600.00</td><td><b>924</b></td><td>205.52</td><td>957</td><td>3600.00</td></tr><tr><td>abz7</td><td>681</td><td>3600.00</td><td>749</td><td>3600.00</td><td>723</td><td>3600.00</td><td><b>672</b></td><td>3600.00</td><td>746</td><td>3600.00</td></tr><tr><td>abz8</td><td>694</td><td>3600.00</td><td>750</td><td>3600.00</td><td>723</td><td>3600.00</td><td><b>677</b></td><td>3600.00</td><td>766</td><td>3600.00</td></tr><tr><td>abz9</td><td><b>691</b></td><td>3600.00</td><td>752</td><td>3600.00</td><td>751</td><td>3600.00</td><td>695</td><td>3600.00</td><td>817</td><td>3600.00</td></tr><tr><td>ft06</td><td><b>54</b>*</td><td>&lt; 0.01</td><td><b>54</b>*</td><td>&lt; 0.01</td><td><b>54</b>*</td><td>0.65</td><td>55</td><td>0.02</td><td><b>54</b></td><td>3600.00</td></tr><tr><td>ft10</td><td><b>900</b>*</td><td>238.81</td><td><b>900</b>*</td><td>1846.53</td><td>955</td><td>3600.00</td><td><b>900</b></td><td>526.71</td><td>1035</td><td>3600.00</td></tr><tr><td>ft20</td><td><b>1165</b>*</td><td>0.93</td><td><b>1165</b>*</td><td>6.89</td><td>1207</td><td>3600.00</td><td><b>1165</b></td><td>260.83</td><td>1204</td><td>3600.00</td></tr><tr><td>la01</td><td><b>666</b>*</td><td>&lt; 0.01</td><td><b>666</b>*</td><td>0.02</td><td><b>666</b>*</td><td>24.59</td><td><b>666</b></td><td>0.17</td><td>670</td><td>3600.00</td></tr><tr><td>la02</td><td><b>655</b>*</td><td>0.03</td><td><b>655</b>*</td><td>0.05</td><td><b>655</b>*</td><td>631.14</td><td><b>655</b></td><td>20.91</td><td>692</td><td>3600.00</td></tr><tr><td>la03</td><td><b>597</b>*</td><td>0.08</td><td><b>597</b>*</td><td>0.04</td><td><b>597</b></td><td>3600.00</td><td><b>597</b></td><td>19.64</td><td>635</td><td>3600.00</td></tr><tr><td>la04</td><td><b>567</b>*</td><td>0.06</td><td><b>567</b>*</td><td>0.14</td><td>583</td><td>3600.00</td><td><b>567</b></td><td>17.35</td><td>599</td><td>3600.00</td></tr><tr><td>la05</td><td><b>593</b>*</td><td>&lt; 0.01</td><td><b>593</b>*</td><td>&lt; 0.01</td><td><b>593</b>*</td><td>1.65</td><td><b>593</b></td><td>0.04</td><td><b>593</b></td><td>3600.00</td></tr><tr><td>la06</td><td><b>926</b>*</td><td>&lt; 0.01</td><td><b>926</b>*</td><td>0.02</td><td><b>926</b>*</td><td>5.52</td><td><b>926</b></td><td>0.1</td><td><b>926</b></td><td>3600.00</td></tr><tr><td>la07</td><td><b>890</b>*</td><td>0.03</td><td><b>890</b>*</td><td>0.05</td><td><b>890</b>*</td><td>38.49</td><td><b>890</b></td><td>3.05</td><td><b>890</b></td><td>3600.00</td></tr><tr><td>la08</td><td><b>863</b>*</td><td>0.04</td><td><b>863</b>*</td><td>0.04</td><td><b>863</b>*</td><td>144.41</td><td><b>863</b></td><td>2.81</td><td><b>863</b></td><td>3600.00</td></tr><tr><td>la09</td><td><b>951</b>*</td><td>0.04</td><td><b>951</b>*</td><td>0.02</td><td><b>951</b>*</td><td>23.18</td><td><b>951</b></td><td>0.64</td><td><b>951</b></td><td>3600.00</td></tr><tr><td>la10</td><td><b>958</b>*</td><td>&lt; 0.01</td><td><b>958</b>*</td><td>0.02</td><td><b>958</b>*</td><td>24.34</td><td><b>958</b></td><td>0.19</td><td><b>958</b></td><td>3600.00</td></tr><tr><td>la11</td><td><b>1222</b>*</td><td>0.03</td><td><b>1222</b>*</td><td>0.04</td><td><b>1222</b>*</td><td>1025.62</td><td><b>1222</b></td><td>3.15</td><td><b>1222</b></td><td>3600.00</td></tr><tr><td>la12</td><td><b>1039</b>*</td><td>0.03</td><td><b>1039</b>*</td><td>0.05</td><td><b>1039</b>*</td><td>396.78</td><td><b>1039</b></td><td>1.14</td><td><b>1039</b></td><td>3600.00</td></tr><tr><td>la13</td><td><b>1150</b>*</td><td>&lt; 0.01</td><td><b>1150</b>*</td><td>0.04</td><td><b>1150</b>*</td><td>99.89</td><td><b>1150</b></td><td>1.56</td><td><b>1150</b></td><td>3600.00</td></tr><tr><td>la14</td><td><b>1292</b>*</td><td>0.02</td><td><b>1292</b>*</td><td>0.04</td><td><b>1292</b>*</td><td>14.17</td><td><b>1292</b></td><td>0.23</td><td><b>1292</b></td><td>3600.00</td></tr><tr><td>la15</td><td><b>1207</b>*</td><td>0.18</td><td><b>1207</b>*</td><td>0.19</td><td><b>1207</b>*</td><td>1920.59</td><td><b>1207</b></td><td>12.38</td><td><b>1207</b></td><td>3600.00</td></tr><tr><td>la16</td><td><b>934</b>*</td><td>22.03</td><td><b>934</b></td><td>3600.00</td><td>961</td><td>3600.00</td><td><b>934</b></td><td>244.25</td><td>997</td><td>3600.00</td></tr><tr><td>la17</td><td><b>747</b>*</td><td>0.1</td><td>759</td><td>3600.00</td><td>794</td><td>3600.00</td><td><b>747</b></td><td>110.23</td><td>793</td><td>3600.00</td></tr><tr><td>la18</td><td><b>822</b>*</td><td>2.65</td><td><b>822</b>*</td><td>676.12</td><td>850</td><td>3600.00</td><td><b>822</b></td><td>185.64</td><td>864</td><td>3600.00</td></tr><tr><td>la19</td><td><b>812</b>*</td><td>318.24</td><td><b>812</b>*</td><td>1469.22</td><td>825</td><td>3600.00</td><td>814</td><td>902.75</td><td>894</td><td>3600.00</td></tr><tr><td>la20</td><td><b>871</b>*</td><td>3.21</td><td>892</td><td>3600.00</td><td>922</td><td>3600.00</td><td>875</td><td>342.32</td><td>926</td><td>3600.00</td></tr><tr><td>la21</td><td><b>1033</b>*</td><td>2179</td><td>1110</td><td>3600.00</td><td>1121</td><td>3600.00</td><td><b>1033</b></td><td>2674.68</td><td>1122</td><td>3600.00</td></tr><tr><td>la22</td><td><b>913</b>*</td><td>2.92</td><td>930</td><td>3600.00</td><td>982</td><td>3600.00</td><td><b>913</b></td><td>1695.98</td><td>1005</td><td>3600.00</td></tr><tr><td>la23</td><td><b>1032</b>*</td><td>0.38</td><td><b>1032</b>*</td><td>1.04</td><td>1054</td><td>3600.00</td><td><b>1032</b></td><td>221.06</td><td>1039</td><td>3600.00</td></tr><tr><td>la24</td><td><b>909</b></td><td>3600.00</td><td>939</td><td>3600.00</td><td>973</td><td>3600.00</td><td>910</td><td>3600.00</td><td>1001</td><td>3600.00</td></tr><tr><td>la25</td><td><b>947</b></td><td>3600.00</td><td>983</td><td>3600.00</td><td>1071</td><td>3600.00</td><td><b>947</b></td><td>2428.74</td><td>1073</td><td>3600.00</td></tr><tr><td>la26</td><td><b>1218</b>*</td><td>3.45</td><td>1232</td><td>3600.00</td><td>1386</td><td>3600.00</td><td><b>1218</b></td><td>733</td><td>1272</td><td>3600.00</td></tr><tr><td>la27</td><td><b>1235</b>*</td><td>116.59</td><td>1346</td><td>3600.00</td><td>1360</td><td>3600.00</td><td><b>1235</b></td><td>2458.09</td><td>1337</td><td>3600.00</td></tr><tr><td>la28</td><td><b>1216</b>*</td><td>2.72</td><td>1255</td><td>3600.00</td><td>1402</td><td>3600.00</td><td><b>1216</b></td><td>1282.21</td><td>1299</td><td>3600.00</td></tr><tr><td>la29</td><td><b>1173</b></td><td>3600.00</td><td>1225</td><td>3600.00</td><td>1325</td><td>3600.00</td><td>1196</td><td>3600.00</td><td>1283</td><td>3600.00</td></tr><tr><td>la30</td><td><b>1355</b>*</td><td>0.58</td><td><b>1355</b>*</td><td>0.51</td><td>1499</td><td>3600.00</td><td><b>1355</b></td><td>143.42</td><td>1396</td><td>3600.00</td></tr><tr><td>la31</td><td><b>1784</b>*</td><td>1.91</td><td><b>1784</b>*</td><td>2.13</td><td>1835</td><td>3600.00</td><td><b>1784</b></td><td>60.13</td><td>1790</td><td>3600.00</td></tr><tr><td>la32</td><td><b>1850</b>*</td><td>1.12</td><td><b>1850</b>*</td><td>0.21</td><td>1874</td><td>3600.00</td><td><b>1850</b></td><td>104.93</td><td>1850</td><td>3600.00</td></tr><tr><td>la33</td><td><b>1719</b>*</td><td>2.06</td><td><b>1719</b>*</td><td>0.35</td><td>1817</td><td>3600.00</td><td><b>1719</b></td><td>59.96</td><td>1719</td><td>3600.00</td></tr><tr><td>la34</td><td><b>1721</b>*</td><td>2.1</td><td><b>1721</b>*</td><td>0.92</td><td>1836</td><td>3600.00</td><td><b>1721</b></td><td>397.13</td><td>1768</td><td>3600.00</td></tr></tbody></table>
<table><caption>Table 2: continued from previous page</caption><thead><tr><th rowspan="2">Inst.</th><th colspan="2">MISTRAL</th><th colspan="2">B&B</th><th colspan="2">CPO<sup>p=1</sup></th><th colspan="2">CPO<sup>p=10</sup></th><th colspan="2">CPO<sup>n=3</sup></th></tr><tr><th>C<sub>max</sub></th><th>time (s)</th><th>C<sub>max</sub></th><th>time (s)</th><th>C<sub>max</sub></th><th>time (s)</th><th>C<sub>max</sub></th><th>time (s)</th><th>C<sub>max</sub></th><th>time (s)</th></tr></thead><tbody><tr><td>la35</td><td><b>1888</b>*</td><td>1.37</td><td><b>1888</b>*</td><td>0.48</td><td>1944</td><td>3600.00</td><td><b>1888</b></td><td>587.35</td><td>1894</td><td>3600.00</td></tr><tr><td>la36</td><td><b>1252</b></td><td>3600.00</td><td>1297</td><td>3600.00</td><td>1358</td><td>3600.00</td><td><b>1252</b></td><td>3600.00</td><td>1360</td><td>3600.00</td></tr><tr><td>la37</td><td><b>1397</b>*</td><td>2.72</td><td>1411</td><td>3600.00</td><td>1500</td><td>3600.00</td><td><b>1397</b></td><td>2609.27</td><td>1503</td><td>3600.00</td></tr><tr><td>la38</td><td><b>1175</b></td><td>3600.00</td><td>1255</td><td>3600.00</td><td>1308</td><td>3600.00</td><td>1191</td><td>3600.00</td><td>1350</td><td>3600.00</td></tr><tr><td>la39</td><td><b>1221</b>*</td><td>2.98</td><td>1362</td><td>3600.00</td><td>1389</td><td>3600.00</td><td>1221</td><td>2119.53</td><td>1378</td><td>3600.00</td></tr><tr><td>la40</td><td><b>1199</b></td><td>3600.00</td><td>1311</td><td>3600.00</td><td>1357</td><td>3600.00</td><td>1234</td><td>3600.00</td><td>1332</td><td>3600.00</td></tr><tr><td>orb01</td><td><b>1035</b></td><td>3600.00</td><td><b>1035</b>*</td><td>2118.7</td><td>1115</td><td>3600.00</td><td>1036</td><td>3600.00</td><td>1114</td><td>3600.00</td></tr><tr><td>orb02</td><td><b>864</b>*</td><td>174.17</td><td>869</td><td>3600.00</td><td>887</td><td>3600.00</td><td>865</td><td>621.22</td><td>943</td><td>3600.00</td></tr><tr><td>orb03</td><td><b>973</b></td><td>3600.00</td><td>1054</td><td>3600.00</td><td>1043</td><td>3600.00</td><td>975</td><td>1191.62</td><td>1093</td><td>3600.00</td></tr><tr><td>orb04</td><td><b>980</b>*</td><td>266.45</td><td><b>980</b>*</td><td>182.2</td><td>1023</td><td>3600.00</td><td>981</td><td>382.11</td><td>1045</td><td>3600.00</td></tr><tr><td>orb05</td><td><b>849</b>*</td><td>28.81</td><td>852</td><td>3600.00</td><td>870</td><td>3600.00</td><td>853</td><td>339.27</td><td>977</td><td>3600.00</td></tr><tr><td>orb06</td><td><b>985</b></td><td>3600.00</td><td>997</td><td>3600.00</td><td>1109</td><td>3600.00</td><td><b>985</b></td><td>870.98</td><td>1079</td><td>3600.00</td></tr><tr><td>orb07</td><td><b>389</b>*</td><td>355.36</td><td><b>389</b>*</td><td>439.51</td><td>395</td><td>3600.45</td><td>390</td><td>127.81</td><td><b>389</b></td><td>1511.23</td></tr><tr><td>orb08</td><td><b>894</b>*</td><td>0.26</td><td><b>894</b>*</td><td>55.94</td><td>959</td><td>3600.00</td><td><b>894</b></td><td>169.13</td><td>960</td><td>3600.00</td></tr><tr><td>orb09</td><td><b>917</b>*</td><td>2.67</td><td><b>917</b>*</td><td>214.58</td><td>969</td><td>3600.00</td><td>920</td><td>154.89</td><td>988</td><td>3600.00</td></tr><tr><td>orb10</td><td><b>930</b>*</td><td>15.36</td><td>941</td><td>3600.00</td><td>1011</td><td>3600.00</td><td><b>930</b></td><td>211.73</td><td>986</td><td>3600.00</td></tr><tr><td>swv16</td><td><b>2924</b>*</td><td>2.03</td><td><b>2924</b>*</td><td>0.69</td><td><b>2924</b>*</td><td>191.93</td><td><b>2924</b></td><td>1.94</td><td><b>2924</b></td><td>3600.00</td></tr><tr><td>swv17</td><td><b>2794</b>*</td><td>0.41</td><td><b>2794</b>*</td><td>0.7</td><td><b>2794</b>*</td><td>3203.24</td><td><b>2794</b></td><td>9.5</td><td><b>2794</b></td><td>3600.00</td></tr><tr><td>swv18</td><td><b>2852</b>*</td><td>2</td><td><b>2852</b>*</td><td>0.74</td><td><b>2852</b>*</td><td>232.57</td><td><b>2852</b></td><td>70.48</td><td><b>2852</b></td><td>3600.00</td></tr><tr><td>swv19</td><td><b>2843</b>*</td><td>5.08</td><td><b>2843</b>*</td><td>3.09</td><td>2970</td><td>3600.00</td><td><b>2843</b></td><td>141.85</td><td><b>2843</b></td><td>3600.00</td></tr><tr><td>swv20</td><td><b>2823</b>*</td><td>1.14</td><td><b>2823</b>*</td><td>0.75</td><td><b>2823</b>*</td><td>226.14</td><td><b>2823</b></td><td>204.49</td><td><b>2823</b></td><td>3600.00</td></tr></tbody></table>

## 5.4 Evaluation of the compact model

Finally, we conducted further experiments to assess the gain attributable to the addition of Constraints 10, 11 and 12 in order to reduce the number of variables and eliminate solutions that leave a gap between two consecutive tasks of the same job. We ran MISTRAL on the basic model (i.e., without Constraints 10, 11 and 12) on the same benchmark instances. We only present aggregated data here.

The conclusion of these experiments is that both models (with or without) those constraints are fairly equivalent when considering the objective value only. The average gain, on the data set *I* containing only instances that are not proven optimal by both models, is:

$$ \frac{1}{|I|} \sum_{i \in I} \frac{C_{\max}(i) - C_{\max}^{*}(i)}{C_{\max}(i)} = 0.03 $$

where $C_{\max}^{*}(i)$ denote the objective value for instance *i* with the extra constraints and $C_{\max}(i)$ the objective value without these constraints. The difference is extremely small, and either model can be best on a given instance.

On instances that were proven optimal, however, the difference is clear and significant: proving optimality is done in 32.76 seconds on average with the extra constraints, whereas it takes 81.42 seconds on average without them. Moreover, one instance (la21) can only be proven optimal within the 1h time cutoff when the extra constraints are used.
# 6 Conclusion

In this paper, we introduced a CP model for the preemptive job shop scheduling problem, and our experimental evaluation shows that it significantly improves the state of the art for this problem. The key aspect of this approach is the observation that when resources are disjoint, the Edge-Finding propagation algorithm guarantees that a preemptive schedule exists, without the need to explicitly compute a fragmentation of the tasks. This approach generalises to all disjunctive scheduling problems where resources are disjoint.

Extending this approach to general resource hypergraphs is an interesting avenue for future work. It could for instance be done in a decomposition scheme whereby after solving the model described in this paper, unit-length tasks are added, however only for those tasks whose fragmentations on two resources are in conflict.

## References

1. Joseph Adams, Egon Balas, and Daniel Zawack. The Shifting Bottleneck Procedure for Job shop Scheduling. Management science, 34(3):391–401, 1988.

2. David Applegate and William Cook. A Computational Study of the Job-shop Scheduling Problem. ORSA Journal on computing, 3(2):149–156, 1991.

3. Nikhil Bansal, Tracy Kimbrel, and Maxim Sviridenko. Job Shop Scheduling with Unit Processing Times. Mathematics of Operations Research, 31(2):381–389, 2006.

4. Philippe Baptiste, Claude Pape, and Wim Nuijten. Constraint-Based Scheduling. Kluwer Academic Publishers, 2001.

5. Christian Bessiere, Nina Narodytska, Claude-Guy Quimper, and Toby Walsh. The AllDifferent Constraint with Precedences. In Proceedings of CPAIOR 2011, pages 36–52, 2011.

6. Frédéric Boussemart, Fred Hemery, Christophe Lecoutre, and Lakhdar Sais. Boosting Systematic Search by Weighting Constraints. In Ramón López de Mántaras and Lorenza Saitta, editors, Proceedings of ECAI 2004, pages 146–150, 2004.

7. Peter Brucker, Svetlana A. Kravchenko, and Yuri N. Sotskov. Preemptive Job-shop Scheduling Problems with a Fixed Number of Jobs. Mathematical Methods of Operations Research, 49(1):41–76, 1999.

8. Jacques Carlier. The One-machine Sequencing Problem. European Journal of Operational Research, 11(1):42–47, 1982.

9. Jacques Carlier and Eric Pinson. A Practical Use of Jackson's Preemptive Schedule for Solving the Job-Shop Problem. Annals of Operations Research, 26:269–287, 1990.

10. George B. Dantzig. A Machine-job Scheduling Model. Management Science, 6(2):191–196, 1960.

11. Abbas Ebadi and Ghasem Moslehi. Mathematical Models for Preemptive Shop Scheduling Problems. Computers & Operations Research, 39(7):1605–1614, 2012.

12. Abbas Ebadi and Ghasem Moslehi. An Optimal Method for the Preemptive Job Shop Scheduling Problem. Computers & Operations Research, 40(5):1314–1327, 2013.

13. Hamed Fahimi and Claude-Guy Quimper. Linear-Time Filtering Algorithms for the Disjunctive Constraint. In Proceedings of AAAI'2014, pages 2637–2643, 2014.

14. Henry Fisher and G.L. Thompson. Probabilistic Learning Combinations of Local Job-shop Scheduling Rules. In J.F. Muth and G.L. Thompson, editors, Industrial scheduling, pages 225–251. Prentice-Hall, Englewood Cliffs, N.J., 1963.

15. Leslie Ann Goldberg, Mike Paterson, Aravind Srinivasan, and Elizabeth Sweedyk. Better Approximation Guarantees for Job-shop Scheduling. SIAM Journal on Discrete Mathematics, 14(1):67–92, 2001.

16. Teofilo Gonzalez and Sartaj Sahni. Flowshop and Jobshop Schedules: Complexity and Approximation. Operations research, 26(1):36–52, 1978.
19:16 An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling

17 Emmanuel Hebrard. Mistral, a Constraint Satisfaction Library. *Third International CSP Solver Competition*, pages 31–39, 2008. URL: http://www.cril.univ-artois.fr/CPAI08/Competition-08.pdf.

18 W.A. Horn. Some Simple Scheduling Algorithms. *Naval Research Logistics Quarterly*, 21(1):177–185, 1974.

19 Anant Singh Jain and Sheik Meeran. Deterministic Job-shop Scheduling: Past, Present and Future. *European journal of operational research*, 113(2):390–434, 1999.

20 Klaus Jansen, Roberto Solis-Oba, and Maxim Sviridenko. Makespan Minimization in Job Shops: A Linear Time Approximation Scheme. *SIAM Journal on Discrete Mathematics*, 16(2):288–300, 2003.

21 Carla Juvin, Laurent Houssin, and Pierre Lopez. Logic-based Benders decomposition for the preemptive flexible job-shop scheduling problem. *Comput. Oper. Res.*, 152:106156, 2023. doi:10.1016/j.cor.2023.106156.

22 Svetlana A. Kravchenko and Yuri N. Sotskov. Complexity of the Two Machine Job-shop Scheduling Problem with a Fixed Number of Jobs. *Central European Journal for Operations Research and Economics*, 1995.

23 Stephen Lawrence. Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques (Supplement). *Graduate School of Industrial Administration, Carnegie-Mellon University*, 1984.

24 Claude Le Pape and Philippe Baptiste. Resource Constraints for Preemptive Job-shop Scheduling. *Constraints*, 3:263–287, 1998.

25 Claude Le Pape and Philippe Baptiste. Heuristic Control of a Constraint-based Algorithm for the Preemptive Job-shop Scheduling Problem. *Journal of Heuristics*, 5:305–325, 1999.

26 Christophe Lecoutre, Lakhdar Sais, Sébastien Tabary, and Vincent Vidal. Last Conflict Based Reasoning. In *Proceedings of ECAI 2006*, pages 133–137, 2006.

27 Alejandro López-Ortiz, Claude-Guy Quimper, John Tromp, and Peter van Beek. A Fast and Simple Algorithm for Bounds Consistency of the AllDifferent Constraint. In Georg Gottlob and Toby Walsh, editors, *Proceedings IJCAI 2003*, pages 245–250. Morgan Kaufmann, 2003. URL: http://ijcai.org/Proceedings/03/Papers/036.pdf.

28 Robert H. Storer, S. David Wu, and Renzo Vaccari. New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling. *Management science*, 38(10):1495–1509, 1992.

29 Petr Vilím. *O(n log n)* Filtering Algorithms for Unary Resource Constraint. In *Proceedings of CPAIOR 2004*, pages 335–347, 2004.

30 Toby Walsh. Search in a Small World. In Thomas Dean, editor, *Proceedings of IJCAI 1999*, pages 1172–1177, 1999.

31 Young Su Yun. Genetic Algorithm with Fuzzy Logic Controller for Preemptive and Non-preemptive Job-shop Scheduling Problems. *Computers & Industrial Engineering*, 43(3):623–644, 2002.
# Horizontally Elastic Edge Finder Rule for Cumulative Constraint Based on Slack and Density

Roger Kameugne

<figure><img src="image_162.png" /></figure>

<figure><img src="image_163.png" /></figure>

Faculty of Sciences, Department of Mathematics and Computer Science, University of Maroua, Cameroon

Sévérine Fetgo Betmbe

<figure><img src="image_164.png" /></figure>

<figure><img src="image_165.png" /></figure>

Faculty of Sciences, Department of Mathematics and Computer Science, University of Dschang, Cameroon

Thierry Noulamo

<figure><img src="image_166.png" /></figure>

<figure><img src="image_167.png" /></figure>

UIT Fotso Victor of Bandjoun, Department of Computer Engineering, University of Dschang, Cameroon

Clémentin Tayou Djamegni

<figure><img src="image_168.png" /></figure>

<figure><img src="image_169.png" /></figure>

Faculty of Sciences, Department of Mathematics and Computer Science, University of Dschang, Cameroon

UIT Fotso Victor of Bandjoun, Department of Computer Engineering, University of Dschang, Cameroon

## Abstract

In this paper, we propose an enhancement of the filtering power of the edge finding rule, based on the *Profile* and the *TimeTable* data structures. The minimal slack and the maximum density criteria are used to select potential task intervals for the edge finding rule. The strong detection rule of the horizontally elastic edge finder of Fetgo and Tayou is then applied on those intervals, which results in a new filtering rule, named *Slack-Density Horizontally Elastic Edge Finder*. The new rule subsumes the edge finding rule and it is not comparable to the Gingras and Quimper horizontally elastic edge finder rule and the *TimeTable* edge finder rule. A two-phase filtering algorithm of complexity $O(n^2)$ (where *n* is the number of tasks sharing the resource) is proposed for the new rule. Improvements based on the *TimeTable* are obtained by considering fix part of external tasks which overlap with the potential task intervals. The detection and the adjustment of the improve algorithm are further increased, while the algorithm remains quadratic. Experimental results, on a well-known suite of benchmark instances of Resource-Constrained Project Scheduling Problems, show that the propounded algorithms are competitive with the state-of-the-art algorithms, in terms of running time and tree search reduction.

**2012 ACM Subject Classification** Computing methodologies → Planning and scheduling; Theory of computation → Constraint and logic programming

**Keywords and phrases** Horizontally Elastic Scheduling, Edge Finder Rule, Profile, TimeTable, Resource-Constrained Project Scheduling Problem

**Digital Object Identifier** 10.4230/LIPIcs.CP.2023.20

**Acknowledgements** The authors thank Dr. Dany Nantchouang and Prof. Emmanuel Hebrard for their proofreading.

## 1 Introduction

Scheduling is the allocation of scarce resources to tasks or activities over time. The economic impact of the scheduling in industries and organizations [6] makes it an important combinatorial optimization problem. Industrial resources are workers, machines, electricity power and raw materials, etc. In computer science, the resources are processors while tasks are processes to be proceeded. The success of constraint programming on scheduling problems

<figure><img src="image_170.png" /></figure>

© Roger Kameugne, Sévérine Fetgo Betmbe, Thierry Noulamo, and Clémentin Tayou Djamegni; licensed under Creative Commons License CC-BY 4.0

29th International Conference on Principles and Practice of Constraint Programming (CP 2023).

Editor: Roland H. C. Yap; Article No. 20; pp. 20:1–20:17

<figure><img src="image_171.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany
## 20:2 Horizontally Elastic Edge Finder Rule Based on Slack and Density

is due to the existence of specific global constraints like **UNARY** [28] and **CUMULATIVE** [1] combined with special search strategies [2, 3, 28]. The global constraint is repeatedly called at each node of the tree search, to remove values from the variables domains when there are inconsistent by resource constraint. It is NP-hard [12] to remove all such inconsistent values from the variables domain.

The filtering algorithms used to prune the domain of variables are generally based on the relaxation of the problem. It can be called many times at each node of the tree search. Therefore, each filtering algorithm has to be fast, sound, and powerful. The global constraint **CUMULATIVE** [1] generally embeds timetabling [14, 21, 4] and edge finding [29, 19, 22] as basis. Some extensions and enhancement of the edge-finding filtering power have been proposed for more pruning of the domains of variables [18, 23, 30, 15, 11]. Energetic reasoning [24, 2, 7] and not-first/not-last rules [9, 16, 17, 27] are two other rules generally embedded in the **CUMULATIVE** constraint when the problem is highly cumulative [2]. The energetic reasoning rule subsumes all other rules except the not-first / not-last rule [2, 30, 11].

In this paper, we propose a new enhancement of the edge finder rule with the *Profile* [15] and to the *TimeTable* [30] data structures. The new rule called *Slack-Density Horizontally Elastic Edge Finder* uses the minimum slack and the maximum density criteria of [19] to select the potential edge finding task intervals on which the detection rule of [11] is going to be applied. This new rule subsumes the edge finding rule, is not comparable to the *Gingras and Quimper rule* [15], and the *TimeTable edge finding rule* [30]. A quadratic algorithm of two-phase (Detection and Adjustment) is proposed for the new rule. To further enhance the algorithm, we improve the new algorithm by considering the fix part of external tasks, which overlap with the intervals during the horizontally elastic scheduling of the task intervals. The final algorithm remains with a quadratic complexity. Experimental results on a well-known suite of benchmark instances of Resource-Constrained Project Scheduling Problems (RCPSPs) from the BL set [2] and the PSPLib set [20] show that, the propounded algorithms are competitive to the state-of-the-art algorithms, in terms of running time and tree search reduction.

The remaining part of the paper is organized as follows: Section 2 is devoted to preliminary notions and related works on previous enhancement of the edge finder rule with data structures; Section 3 presents the new rule based on the global minimum slack and maximum density criteria; Section 4 proposes an $O(n^2)$ algorithm (where *n* is the number of tasks sharing the resource) for the new rule; Section 5 uses the *TimeTable* data structure to improve the detection and the adjustment of the previous algorithm; Section 6 consists of an empirical evaluation of the propounded algorithms with the state-of-the-art algorithms on RCPSP instances; and Section 7 concludes the paper.

# 2 Preliminaries

This section specifies the Cumulative Scheduling Problem (CuSP) and reviews the edge finder rule and its enhancements based on data structures.

## 2.1 A Cumulative Scheduling Problem (CuSP)

In a Cumulative Scheduling Problem (CuSP), a set of tasks *T* has to be executed on a resource of capacity *C*. Each task *i* ∈ *T* is executed without interruption during *p*ᵢ time units and uses *c*ᵢ ≤ *C* units of the resource. For a task *i* ∈ *T*, the earliest starting time estᵢ and the latest completion time lctᵢ are specified. A solution of a CuSP instance is an assignment of a valid starting time sᵢ to each task *i* ∈ *T* such that the resource constraint is
satisfied, i.e.,

$$ \forall i \in T, \quad \text{est}_i \le s_i \le s_i + p_i \le \text{lct}_i \qquad (1) $$

$$ \forall \tau, \quad \sum_{i \in T, s_i \le \tau < s_i + p_i} c_i \le C \qquad (2) $$

Inequalities in (1) ensure that each task is assigned a feasible starting and ending time, while (2) enforces the resource constraint. We use the notation $e_i$ to denote the energy of a task $i \in T$ and it is computed with $e_i = c_i \cdot p_i$. Each task $i \in T$ has an earliest completion time $ect_i = est_i + p_i$ and a latest starting time $lst_i = lct_i - p_i$. These notations can be extended to nonempty sets of tasks as follows:

$$ e_{\Omega} = \sum_{j \in \Omega} e_j, \quad \text{est}_{\Omega} = \min_{j \in \Omega} \text{est}_j, \quad \text{lct}_{\Omega} = \max_{j \in \Omega} \text{lct}_j. \qquad (3) $$

By convention, for empty sets, we have: $e_{\emptyset} = 0$, $est_{\emptyset} = +\infty$ and $lct_{\emptyset} = -\infty$. Throughout the paper, we assume that for any task $i \in T$, $ect_i \le lct_i$ and $c_i \le C$, otherwise the problem has no solution. We let $n = |T|$ denote the number of tasks and $k = |\{c_i, i \in T\}|$ denote the number of distinct capacity demands of the tasks. The global constraint CUMULATIVE [1] is used to solve the CuSP problem, which is a NP-Hard problem [12]. The constraint removes inconsistent values from the domain of starting time variable $s_i \in [est_i, lst_i]$ and it is NP-Hard to remove all such values.

## 2.2 Task Interval, Minimum Slack and Maximum Density

Given two tasks $l$ and $u$ with $est_l < lct_u$. A task interval denoted $\Omega_u^l$ is a set of tasks that must run entirely within the interval $[est_l, lct_u]$. It is formally specified in the following definition.

**Definition 1.** $[\emptyset]$ Let $u$ and $l$ be two tasks that satisfy $est_l < lct_u$. The task interval $\Omega_u^l$ is a set of tasks specified by $\Omega_u^l = \{j \in T \mid est_l \le est_j \wedge lct_j \le lct_u\}$.

When the condition $est_l \le est_j$ is released in the definition of the task interval, it is called in [29] the left cut of $T$ by task $u$ denoted $LCut(T, u)$, i.e., $LCut(T, u) = \{j \in T \mid lct_j \le lct_u\}$. The slack and the density of a task interval are concepts that are useful when designing an edge-finding algorithm [19].

**Definition 2.** Let $l$ and $u$ be two tasks that satisfy $est_l < lct_u$.

1. The slack of the task interval $\Omega_u^l$ is the integer denoted $sl(\Omega_u^l)$ and defined by

$$ sl(\Omega_u^l) = C \cdot (lct_u - est_l) - e_{\Omega_u^l}. \qquad (4) $$

2. The density of the task interval $\Omega_u^l$ is the real number denoted $ds(\Omega_u^l)$ and defined by

$$ ds(\Omega_u^l) = \frac{e_{\Omega_u^l}}{lct_u - est_l}. \qquad (5) $$

In [19], the minimum slack and the maximum density criteria are successfully used to design a fast edge-finding algorithm.

**Definition 3.** $[19]$ Let $u \in T$ be a task.

1. The task interval of minimum slack $\Omega_u^{\tau(u)}$ (where $\tau(u)$ is a task depending on task $u$) is the task interval satisfying the condition:

$$ sl(\Omega_u^{\tau(u)}) \le sl(\Omega_u^l), \quad \forall l \in T \text{ with } est_l < lct_u. \qquad (6) $$
## 20:4 Horizontally Elastic Edge Finder Rule Based on Slack and Density

2. The task interval of maximum density $\Omega_u^{\rho(u)}$ (where $\rho(u)$ is a task depending on task u) is the task interval satisfying the condition:

$$ds(\Omega_u^{\rho(u)}) \ge ds(\Omega_u^l), \quad \forall l \in T \text{ with } est_l < lct_u. \quad (7)$$

These two concepts are used in [19, 18] to select the task intervals that are of interest for the (extended) edge-finder rule.

## 2.3 (Extended) Edge Finding Rule

Let $\Omega \subset T$ be a set of tasks, and $i \notin \Omega$ be a task. If the scheduling of the set of tasks $\Omega$ and the contribution of task $i$ in the interval $[est_{\Omega}, lct_{\Omega})$ when task $i$ starts at $est_i$ cause an overload of the interval $[est_{\Omega}, lct_{\Omega})$, then it is deduced that all tasks in $\Omega$ end before the end of $i$ and is denoted $\Omega < i$. The detection rules are specified by the formulas: $\forall \Omega \subset T$, $\forall i \in T \setminus \Omega$

$$e_{\Omega} + e_i > C \cdot (lct_{\Omega} - est_{\Omega \cup \{i\}}) \Rightarrow \Omega < i \quad (EF)$$

$$\left\{ \begin{array}{ll} est_i < est_{\Omega} & \Rightarrow \Omega < i \\ \wedge & \\ e_{\Omega} + c_i \cdot (ect_i - est_{\Omega}) > C \cdot (lct_{\Omega} - est_{\Omega}) & \end{array} \right. \quad (EEF)$$

The rule (EF) is called edge-finder detection rule, while (EEF) is known as its extension. After each detection, the adjustment follows, using this rule:

$$\Omega < i \Rightarrow est_i \ge \max_{\Theta \subseteq \Omega \wedge rest(\Theta, c_i) > 0} est_{\Theta} + \left\lfloor \frac{rest(\Theta, c_i)}{c_i} \right\rfloor \quad (Adj)$$

where $rest(\Theta, c_i) = e_{\Theta} - (C - c_i) \cdot (lct_{\Theta} - est_{\Theta})$ is the energy of $e_{\Theta}$ that disables the starting time of task $i$ when scheduled on a resource of capacity $C - c_i$ in the interval $[est_{\Theta}, lct_{\Theta})$. A two-phase algorithm of complexity $O(kn \log(n))$ (where $n$ is the number of tasks and $k$ the different number of resource demands of tasks) based on $\Theta$-A-tree data structure was proposed in [29]. A quadratic algorithm based on the minimum slack and the maximum density of task intervals is proposed in [19].

## 2.4 TimeTable Edge Finding Rule

Research revealed that, the first enhancement of the filtering power of the edge finder rule was made with the *TimeTable* data structure in [30]. The fix part of the task is taken into account in the computation of the energy of the set of tasks, resulting in a strengthened rule. If $i \in T$ is a task satisfying $lst_i < ect_i$, then the interval $[lst_i, ect_i)$ determines the mandatory spanning interval of $i$. We denote by $f(\Omega, t)$ the aggregate of the fix parts over time $t$ by tasks in $\Omega$, and $f(\Omega, [a, b))$ the fix parts aggregation over the time interval $[a, b)$ by the tasks in $\Omega$.

$$f(\Omega, t) = \sum_{i \in \Omega | \text{lst}_i \le t < \text{ect}_i} c_i; \quad (8)$$

$$f(\Omega, [a, b)) = \sum_{t \in [a, b)} f(\Omega, t). \quad (9)$$

Let $e_{\Omega}^{TT}$ be the *TimeTable* energy of tasks in $\Omega$. This energy is equal to the energy of $\Omega$ plus the fix energy of the tasks in $T \setminus \Omega$ spent within the interval $[est_{\Omega}, lct_{\Omega})$, i.e., $e_{\Omega}^{TT} = e_{\Omega} + f(T \setminus \Omega, [est_{\Omega}, lct_{\Omega}))$. The *TimeTable* edge finder rule, denoted (TT-EF), is obtained from (EF), (EEF) and (Adj) by substituting $e_{\Omega}$ and $e_{\Theta}$ by $e_{\Omega}^{TT}$ and $e_{\Theta}^{TT}$ respectively.
A quadratic algorithm was proposed in [30] and later refined in [23]. This algorithm was used in [26] with the lazy clause generation approach, where the explanation of its propagation is incorporated as nogoods.

## 2.5 Horizontally Elastic Earliest Completion Time of Tasks Set

The computation of the earliest completion time of a set of tasks for scheduling problems with resource constraints is known to be NP-hard [12]. Depending on the way tasks are scheduled, a lower bound of the earliest completion time can be computed. According to [2], the set of tasks $\Omega$ is said to be fully elastic scheduled, if each task $i \in \Omega$ starts at est$_{\Omega}$ and occupies a total area of $e_i = c_i \cdot p_i$. At any time $t \in [est_{\Omega}, lct_{\Omega})$, a task $i$ can occupy more or less $c_i$ units of height and when time $t$ reaches the height $C$, time $t+1$ starts being occupied. The fully elastic earliest completion time of $\Omega$ (denoted ect$_{\Omega}^F$) occurs when all tasks are completed. It is computed in [29] with the formula.

$$ect_{\Omega}^F = \left[ \frac{\max\{Cest_{\Omega'} + e_{\Omega'} | \Omega' \subseteq \Omega\}}{C} \right] \quad (10)$$

In [15], a new way of scheduling a set of tasks called horizontally elastic scheduling is introduced. A set of tasks $\Omega$ is said to be horizontally elastic scheduled, when each task $i \in \Omega$ starts at its earliest starting time est$_i$ and cannot consume more than its required capacity at any time during the time interval $[est_i, lct_i)$. At any time $t \in [est_{\Omega}, lct_{\Omega})$, the energy that cannot be executed, due to the limited capacity, is accumulated as an overflow and released when the resource is no longer saturated. The horizontally elastic earliest completion time of $\Omega$ denoted ect$_{\Omega}^H$ occurs when all tasks are completed. The computation of the horizontally elastic earliest completion time of tasks set is done with a data structure called Profile that stores the resource utilization over time. The tuples $(time, cap, \Delta_{max}, \Delta_{req})$ (where time is the starting time, cap is the remaining capacity of the resource at the starting time, $\Delta_{max}$ is the maximum resource available at starting time, and $\Delta_{req}$ is the maximum resource required by tasks at starting time) are stored in a sorted linked-list whose nodes are called time points. The Profile is initialized with a time point of capacity $C$ for every distinct value of est, ect and lct. A sufficiently large time point is added to act as a sentinel. Finally, while initializing the data structure, the pointers $t.est_i$, $t.ect_i$ and $t.lct_i$ are used to return the time point associated with est$_i$, ect$_i$, and lct$_i$ for each task $i \in T$. The horizontally elastic earliest completion time of a set of tasks $\Omega$ denoted ect$_{\Omega}^H$ is computed using the functions $c_{req}(t)$, $c_{max}(t)$, $c_{cons}(t)$ and $ov(t)$ on the Profile $P$.

- $c_{max}(t) = \min \left( \sum_{i \in \Omega | est_i \le t < lct_i} c_i, C \right)$ is the amount of resource that can be allocated to the tasks in $\Omega$ at time $t$;

- $c_{req}(t) = \sum_{i \in \Omega | est_i \le t < lct_i} c_i$ is the amount of resource required at time $t$ by the tasks in $\Omega$ if they were all starting at their earliest starting times;

- $ov(t)$ is the overflow of energy from $c_{req}(t)$ that cannot be executed at time $t$ due to the limited capacity $c_{max}(t)$, and

- $c_{cons}(t)$ is the amount of resource that is actually consumed at time $t$ with $c_{cons}(t) = \min(c_{req}(t) + ov(t-1), c_{max}(t)); ov(t) = ov(t-1) + c_{req}(t) - c_{cons}(t)$ and $ov(-1) = 0$.

The horizontally elastic earliest completion time occurs when all tasks are completed. Given a set of tasks $\Omega$, the horizontally elastic schedule of $\Omega$ uses in [15] the function ScheduleTasks($\Omega, C$) of Algorithm 1 to compute the horizontally elastic earliest completion
20:6 Horizontally Elastic Edge Finder Rule Based on Slack and Density

time of Ω. The properties of this data structure is the linearity of the function ScheduleTasks,
since the Profile contains at most 4n + 1 time points. For a set of tasks Ω, it is proved in
[15] that ect<sup>F</sup><sub>Ω</sub> ≤ ect<sup>H</sup><sub>Ω</sub> ≤ ect<sub>Ω</sub> where ect<sub>Ω</sub> is the earliest completion time of Ω.

■ Algorithm 1 ScheduleTasks(Ω, C) algorithm in O(n) time from [15].

Input: All time point t of the profile P, Ω a set of tasks, C the resource capacity.

Output: the earliest completion time ect^H of the set Ω

1 **forall** $t \in P$ **do**

2 $t \cdot \Delta_{\max} \leftarrow 0$ and $t \cdot \Delta_{req} \leftarrow 0$

3 **for** $i \in \Omega$ **do**

4 Increase $t.est_i \cdot \Delta_{\max}$ and $t.est_i \cdot \Delta_{req}$ by $c_i$

5 Decrease $t.lct_i \cdot \Delta_{\max}$ and $t.ect_i \cdot \Delta_{req}$ by $c_i$

6 $ect \leftarrow -\infty$; $ov \leftarrow 0$; $c_{req} \leftarrow 0$; $S \leftarrow 0$

7 $t \leftarrow P.first$

8 **while** $t.time < lct_{\Omega}$ **do**

9 $l \leftarrow t.next.time - t.time$; $S \leftarrow S + t \cdot \Delta_{\max}$; $c_{max} \leftarrow \min(S, C)$; $c_{req} \leftarrow c_{req} + t \cdot \Delta_{req}$; $c_{cons} \leftarrow \min(c_{req} + ov, c_{max})$

10 **if** $ov > 0 \land ov < (c_{cons} - c_{req}) * l$ **then**

11 $l \leftarrow \lceil \frac{ov}{c_{cons} - c_{req}} \rceil$

12 $t.insertAfter(t.time + l, t.cap)$

13 $ov \leftarrow ov + (c_{req} - c_{cons}) * l$

14 $t.cap = C - c_{cons}$

15 **if** $t.cap < C$ **then**

16 $ect \leftarrow t.next.time$;

17 $t \leftarrow t.next$

18 **if** $ov > 0$ **then**

19 **return** $+\infty$;

20 **return** $ect$

2.6 Existing Horizontally Elastic Edge Finder

The Profile data structure is used in [15] to enhance the edge finding rule with the detection
rule: for all $i, j \in T$ with $lct_i > lct_j$,

$$
\mathrm{ect}_{\mathrm{LCut}(T,j) \cup \{i\}}^{H} > \mathrm{lct}_j \Rightarrow \mathrm{LCut}(T,j) < i. \qquad (\mathrm{GQHE-EF})
$$

where LCut(T, j) = {k ∈ T | lct_k ≤ lct_j}. The detection proceeds by batching of tasks of the
same height (capacity demand) and all precedences are made in O(kn²) where k ≤ n is the
number of distinct capacities required by the tasks, and n the number of tasks that share the
resource [15]. If the free energy of height cᵢ of the profile of LCut(T, j) from lctⱼ to estᵢ is
less than the contribution of task i in the interval [estᵢ, lctⱼ) when i starts at estᵢ, then it is
deducted that LCut(T, j) < i. When the relation LCut(T, j) < i is detected, the adjustment
phase schedules the tasks of LCut(T, j) on the lower part of the resource of capacity C − cᵢ.
Because of the capacity restriction, it results in an overflow, scheduled on the upper part of
the resource of capacity cᵢ. The ending time of the scheduling is where the earliest starting
time of task i (estᵢ) is adjusted. A quadratic algorithm is presented in [15] for the adjustment
phase.
In the horizontally elastic edge finder of [11], task i is more constrained than in the previous one [15] (preemption is allowed to task i). The new rule is based on the formulation: for all $i, j \in T$ with $lct_i > lct_j$,

$$ \mathrm{ect}_{\mathrm{LCut}(T,j) \cup \{i'\}}^{H} > lct_j \Rightarrow \mathrm{LCut}(T, j) < i \qquad (\mathrm{FTHE-EF}) $$

where $i'$ is a task derived from tasks i and j whose parameters $\langle \mathrm{est}_i, \mathrm{lct}_i, p_{i'}, c_{i'} \rangle$ are

$$ \langle \mathrm{est}_i, \min(\mathrm{ect}_i, \mathrm{lct}_j), \min(\mathrm{ect}_i, \mathrm{lct}_j) - \mathrm{est}_i, c_i \rangle. $$

It is proved in [11] that this rule is stronger than rule (GQHE-EF). Its authors propose an algorithm of complexity $O(kn^2)$ (where $k \le n$ is the number of distinct capacities required by the tasks and $n$ the number of tasks sharing the resource) for the detection. A quadratic algorithm was proposed for the adjustment of this rule for an overall complexity of $O(kn^2)$ [11].

## 3 Slack-Density Horizontally Elastic Edge Finder Detection Rule

According to [15, 10, 11], the most challenging part of the strengthening of edge finding rule with Profile is the detection phase. The rule (GQHE-EF) proposed in [15] is a relaxation of the rule (FTHE-EF) proposed in [11]. In this section, we propose another relaxation of this rule based on the notions of minimum slack and maximum density. In fact, in [19], it is proved that a complete edge finder can be designed using the minimum slack and the maximum density of task intervals.

For a given task $i \in T$ and for a given task $u \in T$ with $lct_i > lct_u$, there exists a task $\tau(u, i)$ such that $\mathrm{est}_{\tau(u,i)} \le \mathrm{est}_i$ and for all $l \in T$ with $\mathrm{est}_l \le \mathrm{est}_i$ we have $sl(\Omega_u^{\tau(u,i)}) \le sl(\Omega_u^l)$ (See Definition 6 of [19]). We denote by $\Omega_{\beta(i)}^{\alpha(i)}$ the task interval of minimum slack among the task interval $\Omega_u^{\tau(u,i)}$ for all $u \in T$ with $lct_i > lct_u$, i.e.,

$$ \Omega_{\beta(i)}^{\alpha(i)} = \mathrm{argmin}\{sl(\Omega_u^{\tau(u,i)}) \mid \forall u \in T \text{ with } lct_i > lct_u\}. \qquad (11) $$

In the following lemma, we are going to prove that each detection of the rule (EF) with pair $(\Omega, i)$ is realized by the rule (FTHE-EF) with pair $(\mathrm{LCut}(T, \beta(i)), i)$.

**Lemma 4.** Let $i$ be a task and $\Omega$ be a set of tasks such that $i \notin \Omega$. If the edge finding rule (EF) holds with the set $\Omega$ and task $i$, then the rule (FTHE-EF) holds also with $\mathrm{LCut}(T, \beta(i))$ and task $i$.

*Proof.* Let $u$ be the task such that $lct_u = lct_\Omega$. We have $sl(\Omega_{\beta(i)}^{\alpha(i)}) \le sl(\Omega_u^{\tau(u,i)}) \le sl(\Omega)$ by definition of $\Omega_{\beta(i)}^{\alpha(i)}$ and $\Omega_u^{\tau(u,i)}$. The rule (EF) applies to $\Omega$ and $i$ (i.e., $e_\Omega + e_i > C(lct_\Omega - \mathrm{est}_\Omega)$) is equivalent to $sl(\Omega) < e_i$ which implies $sl(\Omega_{\beta(i)}^{\alpha(i)}) < e_i$. According to [11, 15], we have the following dominance properties (FTHE-EF) $\succeq$ (GQHE-EF) $\succeq$ (EF) + (EEF) where $(A) \succeq (B)$ means that rule $(A)$ subsumes rule $(B)$ and $(A) + (B)$ means the conjunction of rules $(A)$ and $(B)$. Therefore, from the inequalities $\mathrm{ect}_{\mathrm{LCut}(T,\beta(i)) \cup \{i'\}}^{H} \ge \mathrm{ect}_{\mathrm{LCut}(T,\beta(i)) \cup \{i\}}^{H} \ge \mathrm{ect}_{\mathrm{LCut}(T,\beta(i)) \cup \{i\}}^{F} > lct_{\beta(i)}$, it follows that the rule (FTHE-EF) holds for $\mathrm{LCut}(T, \beta(i))$ and task $i$. $\blacksquare$

**Example 5.** Consider the CuSP instance of Figure 1a where four tasks share a resource of capacity 2. The rule (EF) holds for $\Omega = \{b, c\}$ and $i = d$. The tasks interval of minimum slack $\Omega_{\beta(d)}^{\alpha(d)}$ is the set $\Omega_{\beta(d)}^{\alpha(d)} = \{b, c\}$ and $\mathrm{LCut}(T, \beta(d)) = \{a, b, c\}$. The profile of the set $\mathrm{LCut}(T, \beta(d)) \cup \{d'\}$ is depicted in Figure 1b. The overflow remaining after time 6 allows to detect that $\mathrm{LCut}(T, \beta(d)) < d$.
<figure><img src="image_172.png" /><figcaption>(a) CuSP instance of four tasks sharing a resource of capacity 2</figcaption></figure>

<figure><img src="image_173.png" /><figcaption>(b) The profile of the set LCut(T, β(d)) ∪ {d'} = {a, b, c, d'}</figcaption></figure>

Figure 1 la: CuSP instance of four tasks sharing a resource of capacity 2 where (EF) detects {b, c} < d; lb: The profile of the set LCut(T, β(d)) ∪ {d'} = {a, b, c, d'} and it is detected that LCut(T, β(d)) < d.

For a given task $i \in T$ and for a given task $u \in T$ with $lct_i > lct_u$, there exists a task $\rho(u, i)$ such that $est_i < est_\rho(u, i)$ and for all $l \in T$ with $est_i < est_l$ we have $ds(\Omega_u^{\rho(u,i)}) \ge ds(\Omega_u^l)$ (See Definition 8 of [19]). We denote by $\Omega_{\delta(i)}^{\gamma(i)}$ the task interval of maximum density among the task interval $\Omega_u^{\rho(u,i)}$ for all $u \in T$ with $lct_i > lct_u$, i.e.,

$$ \Omega_{\delta(i)}^{\gamma(i)} = \argmax\{ds(\Omega_u^{\rho(u,i)}) \mid \forall u \in T \text{ with } lct_i > lct_u\}. \quad (12) $$

If the extended edge finding rule (EEF) holds with a set $\Omega$ and a task $i$, then the rule (FTHE-EF) holds also with LCut(T, $\delta(i)$) and task $i$ as it is proved in the following lemma.

**Lemma 6.** Let $i$ be a task and $\Omega$ be a set of tasks such that $i \notin \Omega$. If the extended edge finding rule (EEF) holds with the set $\Omega$ and task $i$, then the rule (FTHE-EF) holds also with LCut(T, $\delta(i)$) and task $i$.

**Proof.** Let $i$ be a task and $\Omega$ be a set of tasks such that $i \notin \Omega$. We assume that the extended edge finding rule (EEF) holds with the set $\Omega$ and task $i$. Let $\Theta$ be the set of tasks used to update the earliest starting time of task $i$ by rule (Adj). The proof of this lemma will distinguish the case $ect_i \ge lct_{\delta(i)}$ from the case $ect_i < lct_{\delta(i)}$.

- If $ect_i \ge lct_{\delta(i)}$ then $ds(\Omega_{\delta(i)}^{\gamma(i)}) \ge ds(\Theta) > C - c_i$ since rest($\Theta$, $c_i$) > 0. The rule (EEF) is detected by $\Omega_{\delta(i)}^{\gamma(i)}$ and task $i$ since the contribution of task $i$ in the interval $[est_{\gamma(i)}, lct_{\delta(i)})$ is $c_i(lct_{\delta} - est_{\gamma(i)})$. Thus, $ect_{LCut(T, \delta(i)) \cup \{i'\}}^H \ge \text{ect}_{LCut(T, \delta(i)) \cup \{i'\}}^H \ge \text{ect}_{LCut(T, \delta(i)) \cup \{i\}}^F > lct_{\delta(i)}$, and the rule (FTHE-EF) holds for LCut(T, $\delta(i)$) and task $i$.

- We assume that $ect_i < lct_{\delta(i)}$. Let $u$ be a task such that $lct_u = lct_\Omega$. The task interval $\Omega_{\delta(i)}^{\gamma(i)}$ has the highest resource consumption spike. Therefore, the set of tasks LCut(T, $\delta(i)$) is the most indicated to disable the start time of task $i$. The rest of the proof is going to distinguish two cases: $lct_\delta < lct_u$ and $lct_\delta \ge lct_u$.

- If $lct_{\delta(i)} < lct_u$ then, LCut(T, $\delta(i)$) $\subseteq$ LCut(T, $u$) and the horizontally elastic scheduling of $\omega = LCut(T, u) \setminus LCut(T, \delta(i))$ is not enough to fill the profile from $lct_u$ to $lct_{\delta(i)}$. Therefore, the slack of LCut(T, $u$) is greater than the one of LCut(T, $\delta(i)$). Task $i$ has the same contribution in both intervals LCut(T, $u$) and LCut(T, $\delta(i)$). When this contribution is considered during the horizontally elastic scheduling of LCut(T, $u$), it results to in an overload. The same overload happens when the contribution of task $i$ is considered during the scheduling of the interval LCut(T, $\delta(i)$). Thus, the rule (FTHE-EF) holds for LCut(T, $\delta(i)$) and task $i$.

- If $lct_{\delta(i)} \ge lct_u$ then, LCut(T, $u$) $\subseteq$ LCut(T, $\delta(i)$) and the horizontally elastic scheduling of $\omega = LCut(T, \delta(i)) \setminus LCut(T, u)$ is not enough to fill the profile from $lct_{\delta(i)}$ to $lct_u$.