# Formulation as Constraint Program (CP)

We formulate the **RLSP** into a constraint program using constructs available in **OR-Tools**.

## Definition of Variables

For operations, we use **interval variables**. An interval variable is defined as:

$$
i = (i_s, i_d, i_e, i_p)
$$

consisting of integer values for:

- start: $i_s$
- duration: $i_d$
- end: $i_e$
- presence: $i_p \in \{0, 1\}$

The presence variable indicates whether the interval is active (i.e., part of the solution) or ignored by all constraints. Introducing an interval variable implicitly enforces:

$$
i_s + i_d = i_e
$$

To handle the assignment of machines (especially with multiple identical machines) and to simplify constraint formulation, we introduce **roles** of machines in operations.

Let $o \in O$ be an operation. The roles in $o$ are defined as:

$$
R(o) :=
\begin{cases}
  (\text{origin, main, target}) & \text{if } o \in \hat{O} \text{ (move operations)} \\
  (\text{main}) & \text{if } o \notin \hat{O}
\end{cases}
$$

The set of machines in a machine configuration $L$ that can fulfill the **main** role is denoted:

- If $\hat{M}(o)$ is defined:

$$
\tilde{M}(o, \text{main}) = \{ \hat{M}(o) \}
$$

- Otherwise:

$$
\tilde{M}(o, \text{main}) = \{ M \in L \mid T(M) = T(o) \}
$$

We now formalize the assignment of machines to roles in an operation.

For each operation $o \in O$ with roles $R(o)$, define the set of **feasible role assignments** in machine configuration $L$:

$$
R_L(o) := \prod_{R \in R(o)} \tilde{M}(o, R)
$$

Each $r \in R_L(o)$ is a mapping:

$$
r: R(o) \to \tilde{M}(o, R)
$$

assigning each role $R$ to a machine $r(R) \in \tilde{M}(o, R)$. Each assignment represents one way to execute the operation using available machines.

Each operation $o \in O$ is represented by a **finite set of interval variables**:

$$
I_o = \{ (s_o, d_o, e_o, p_r) \mid r \in R_L(o) \}
$$

- $s_o$, $e_o$: start and end variables of $o$
- $d_o$: known duration
- $p_r \in \{0,1\}$: presence variable for assignment $r$

## Explanation of Used Constraints

### Consistency Constraints

Only one assignment of machines to roles must be chosen:

$$
\sum_{r} p_r = 1 \quad \text{for all } o \in O
$$

In OR-Tools:

```python
model.AddExactlyOne(p_r_list)
```

If operations $o_i$ and $o_j$ are connected and share a role, presence variables must agree:

$$
p_{r_i} = p_{r_j}
$$

In OR-Tools:

```python
model.Add(p1 == p2)
```

### Precedence Constraints

For each edge $e = (o_i, o_j) \in E$:

$$
w_{\min}(e) \leq s_{o_j} - e_{o_i} \leq w_{\max}(e)
$$

In OR-Tools:

```python
model.Add(end_i <= start_j)
model.Add(start_j - end_i >= wmin)
model.Add(start_j - end_i <= wmax)
```

### Processing Capacity Constraints

Each machine $M \in L$ has capacity $c_p(M)$:

- If $c_p(M) = 1$: enforce no overlap:

  ```python
  model.AddNoOverlap(intervals)
  ```

- If $c_p(M) > 1$: allow overlaps up to capacity:

  ```python
  model.AddCumulative(intervals, demands, capacity)
  ```

### Spatial Capacity Constraints

Machines have spatial capacity $c_s(M)$. Model storage via **reservoir constraints**:

- Transport into $M$: increase level at $s_o$
- Transport out of $M$: decrease level at $e_o$

In OR-Tools:

```python
model.AddReservoirConstraintWithActive(
    times, level_changes, actives, min, max
)
```

### No Load-While-Processing Constraints

Machines with $l(M) = 0$ can't load/unload during processing:

$$
[s_1, e_1) \cap [s_2, e_2) = \emptyset
$$

In OR-Tools:

```python
model.AddNoOverlap([I_1, I_2])
```

### Objective Function and Waiting Costs

Objective: minimize weighted sum of waiting costs and makespan:

$$
\text{Cost}_\alpha(S) := \text{WaitCost}(S) + \alpha \cdot \text{Makespan}(S)
$$

**Makespan**:

$$
\text{makespan} := \max_{o \in O} e_o
$$

```python
model.AddMaxEquality(makespan, [e_o])
```

**Waiting Costs**:

- For edge $(o_i, o_j)$:

  $$
  w_{ij} := c(e) \cdot (s_{o_j} - e_{o_i})
  $$

- For initial operation:

  $$
  w_o := c_o \cdot s_o
  $$

Total:

$$
\text{wait_cost} := \sum w_{ij} + \sum w_o
$$

Final objective:

```python
model.Minimize(alpha * makespan + wait_cost)
```

### Soft Constraints (Optional)

To allow bounded violations:

$$
\xi_k \geq (s_{o_j} - e_{o_i}) - w_{\max}(e)
\quad \text{or} \quad
\xi_k \geq w_{\min}(e) - (s_{o_j} - e_{o_i})
$$

Final objective (with penalties $\beta$):

```python
model.Minimize(alpha * makespan + wait_cost + beta * sum(aux_vars))
```

---

## Discussion of the CP Model

### Rescheduling

It is possible to reoptimize partially executed schedules after for example durations differed from the expectation.
This can be done by simply fixing the starting and ending time as well as machine assignments of corresponding intervals.

### Including Heuristics

Ortools offers the syntax of solution hints.
That allows attempts to compute sulotions with different heuristics and feed the solutions into ortools
which then tries to improve that solution.

### Performance

CP has proven to be better than MIP.
One can roughly expect reasonable solutions on a average computer within 1 minute to problems of up to 80 operations.