# Basic concepts

## Intervals​

Interval variables (or just intervals) are the main decision variable in scheduling. They represent a task to be performed.

OptalCP decides the start and length of all interval variables, based on the parameters provided by the user

• bounds : min / max start time, min / max end time, min / max length
• constraints to be satisfied
• objective function

Here is an example with

• start in [0 .. 50]
• end in [100 .. 250]
• length in [25 .. 175]

Because of the equation $length = end - start$ only two out of the three variables need to be fixed.

FIXME : SVG scale and html scale differ: labels move when zoom in/out in browser
start
end

Decision variables

Different optimization engines may manipulate different types of variables (and different types of constraints). In general one can expect that

• SAT engines use boolean variables
• SMT engines use the type of variables that are available in the theories they implement. Typical theories are bit-vectors, arrays, rationals and integers
• CP based scheduling engines use interval variables and integer variables
• MIP engines use floating point and integer variables
• LS engines use floating point and integer variables

## Propagation​

While playing with the widget, you may have noticed that not all start times, end times or lengths can be achieved.

• The minimum length is 50 (with start = 50 and end = 100)
• The maximum end time is 225 (with start = 50 and length = 175)

Constraint propagation is the reduction of the variable bounds (or domains) based on deductions that can be made from the problem constraints. Here the only constraint is the implicit constraint start + end = length.

FIXME: Scales of first and second gantt differ (automatic rescaling by browser) hence they have same length when they shouldn't

The engine will propagate all constraints till fix point that is until it is not able to make any further reduction.

Deductions

There are may forms of deductions. The terms domain reduction and bound propagation are synonyms. Terms like cut generation, conflict generation or symmetry breaking all refer to some more advanced types of deductions that can also result directly or indirectly in a reductio nof the variable domains

## Precedences​

A precedence is an inequality between the start end end times of two interval variables

Consider the following pseudo-code in OPtaL (a language similar to OPL)

dvar interval A in 0 .. 10 length 5 .. 10dvar interval B in 0 .. 20 length 5 .. 10constraints {    end A <= start B}

The code requests the creation of

• an interval A with start in [0 .. 10], end in [0 .. 10] and length in [5..10]
• an interval B with start in [0 .. 20], end in [0 .. 20] and length in [5..10]
• a constraint end A <= start B

It is common that a global domain is given for both start and end variables rather than individual domains for each one. That means the task needs to fit in the range 0 .. 10.

The engine will adjust the individual bounds as follows

• start A in [0 .. 10] and length A in [5 .. 10] => end A in [5 .. 10]
• end A in [5 .. 10] and length A in [5 .. 10] => start A in [0 .. 5]
• end A in [5 .. 10] and end A <= start B => start B in [5 .. 20]
• start B in [5 .. 20] and length B in [5 .. 10] => start B in [5 .. 15]
• start B in [5 .. 15] and length B in [5 .. 10] => end B in [10 .. 20]

Precedences may contain constants start A <= start B + 10 or even arbitrary arithmetic operations start A <= 2 * (start B) + 3 * (length B) or logic operators end A <= start B || end B <= start A.

You may also have noticed that even after propagation, there is not enough information to fix the variables : a large variety of start times and lengths are still possible.

Engines decide appropriate values for the variables (here start time and length). They will consider many combinations of values and retain the best one they have found. In this context the best is the one that has the best objective value (which we explain below)

Everything else being equal, OptalCP with always choose the smallest starting time and length possible. That's the leftmost schedule

Yes
No
No

Search strategies

The common types of search strategies are tree search and local search. OptalCP just like most engines uses a combination of local and tree search:

• Large Neighborhood Search (LNS) [Shaw 1997] is a local search technique that uses a tree search as a subroutine to search neighborhoods
• Failure Directed Search (FDS) [Vilim 2015] is a nogood-directed tree search useful for proving optimality

## Objectives​

An objective is a function that the engine has to maximize or minimize.

Common objectives include

• makespan is the maximum of the completion time of tasks
• tardiness is the sum of the difference between the time a task was completed and its due date
• lateness is the sum of the delays between a task completion and its due date

### Makespan​

The makespan is the time of completion of the last task

$\max_k \mathrm{end}\ T_k$

### Lateness​

When tasks have an ideal completion time, the lateness measures the distance between the ideal completion of each task and its real completion time

$\sum_k (\mathrm{end}\ T_k - \mathrm{due}_k)$

The due dates can be grouped into a constant and only the sum of end times remains

$C + \sum_k \mathrm{end}\ T_k$

Very often we just ignore the constant term $C$ and call lateness the sum of end times.

### Tardiness​

Tasks have a due date but no penalty is incurred unless the task is completed after the due date.

$\sum_k \max(0, \mathrm{end}\ T_k - \mathrm{due}_k)$

Multi-objective optimization

OptalCP doesn't support yet multiple objectives. Lexicographic objectives can be simulated for now as a weighted sum.

## APIs​

As of today the main way of using the engine is via TypeScript or JavaScript on top of NodeJS.

A typical JavaScript / Typescript model has the following structure

import * as CP from '@optal/cp' // include the libconst model = new CP.Model // create an empty modelconst x = <IntervalVar> Array (10) // create decision variablesfor (let i = 0; i < 10; i++)     x[i] = model.intervalVar({ length: 2, name: x\${i} })model.minimize(model.max(x)) // define objectivefor (let i = 1; i < 10; i++) x[i-1].endBeforeStart(x[i]) // add constraintsCP.solve(model) // solve

We also provide all models in a pseudo-code we call OPtaL for convenience, as OPtaL models tend to be significantly shorter than their TypeScript / JavaScript counterpart.

dvar interval x [1 .. 10] length 2 // create and initialize decision variablesminimize max (i in 1 .. 10) end x[i] // define objectiveconstraints {    forall (i in 2 .. 10) end x[i - 1] <= start x[i] // add constraints}
tip

In programmatic APIs like JavaScript the order of the model declarations is rather free. For instance instead of declaring all the variables at one point, then initializing them all and later adding all the constraints, you could do multiple small blocks with declaration-initialization-constraints. But we strongly recommend to stick to a style that is close to OPtaL pseudocode and the examples provided, as it is very easy to get lost and confused in a large JavaScript model otherwise.

## Project Scheduling Problem (PSP)​

The project scheduling problem (PSP) consists in scheduling all tasks needed to complete a project in the minimum time possible.

There are many variants that model different ways to allocate the resources needed to perform said tasks. We will consider here the simplest version that only involves tasks and precedences.

### Construction of the Millau Viaduct​

Image: Foster and partners The construction of the Millau viaduct required

• Erecting 7 piers
• Building 2 abutments, one on each side
• Setting up a construction site on each abutment to manufacture the steel decks
• Manufacturing the decks (transportation of parts, assembly, welding)
• Moving the decks into place using temporary intermediate piers for support
• Joining the decks in the middle
• Installing the pylons and attaching the stays
Image: Foster and partners ### Modeling​

Every optimization problem requires a modeling phase where assumptions and simplifications are made in order to map the reality into decision variables and constraints.

For instance we could choose to

• merge the construction of the abutments and deck manufacturing sites into a single interval, or keep them separate
• ignore the transportation of the parts and only create an interval for the manufacturing of the decks
• cut the deck manufacturing into independently managed sections, each one having its corresponding interval, or treat the whole manufacturing as a single interval

All these modeling decisions are equally valid and represent different levels of granularity of the problem. Depending on the customer, the data, the constraints needed and performance expectations, a higher or lower level of granularity may be required.

Modeling is crucial

Modeling is a crucial step in solving real life optimization problems. Most of the time problems seen in optimization manuals have been stripped of this phase and are presented in a way where there is a single obvious model. This makes the exercise simpler to handle (only one "solution"), but hides a very important aspect of the work.

Diving straight into coding without considering different ways of mapping the problem into scheduling concepts will inevitably lead to problems (poor performance, excessively complex models, inability to add some constraints)

### A model only with precedences​

In this model we ignore all resources and just focus on scheduling the large tasks to have an idea of the order in which they should be done, and the total completion time for the project. We also solve the problem as if the construction was proceeding from left to right (in reality the bridge is built from both sides at the same time)

The core of the problem is the precedence relationship between the deck sections and the piers.

We introduce intervals for the piers, the temporary piers and the deck sections with the following precedences

dvar interval pier [0 .. n - 1] length build_pierdvar interval temp_pier [0 .. n - 1] length build_temp_pierdvar interval deck [0 .. n - 1] length position_deckforall (i in 0 .. n - 1) {    if (i > 0) start deck[i] >= end deck [i - 1]     start deck[i] >= end pier[i]    start deck[i] >= end temp_pier[i]    if (i > 0) start deck[i] >= end pier[i - 1] // pier[-1] is the abutment}

Now we want to model the fact that temporary piers are a unique resource, that is they need to be disassembled in position n before being remounted in position n + 1. To do so, we will introduce a new interval disassemble_temp_pier[1..n] and constrain the disassembling operations to be interleaved with the mounting operations.

We also can only disassemble the temp_pier[i] once the deck[i] is installed

dvar interval disassemble_temp_pier [0 .. n - 1] length unbuild_temp_pierforall (i in 0 .. n - 1) {    end temp_pier[i] <= start disassemble_temp_pier[i]    end desk[i] <= start disassemble_temp_pier[i]    if (i > 0) end disassemble_temp_pier[i - 1] <= start temp_pier[i]}   

Finally we add an activity for the abutment and setting up of the construction site, and another one for the deck junction (last deck), installing the pylons and attaching the stays

dvar interval abutment length setup_abutmentdvar interval everything_else length othersforall (i in 0 .. n - 1) end abutment <= start deck[i]forall (i in 0 .. n - 1) end deck[i] <= start everything_else

We can now assemble everything into a single model and add a makespan objective and translate into JavaScript / TypeScript

int build_pier = 10int build_temp_pier = 4int unbuild_temp_pier = 2int position_deck = 4int setup_abutment = 2int others = 10int n = 7range phases = 1 .. ndvar interval pier [phases] length build_pierdvar interval temp_pier [phases] length build_temp_pierdvar interval disassemble_temp_pier [phases] length unbuild_temp_pierdvar interval deck [phases] length position_deckdvar interval abutment length setup_abutmentdvar interval everything_else length othersminimize end everything_elseconstraints {    // Deck is built on top of piers and after previous deck    forall (i in phases) {        start deck[i] >= end pier[i]        start deck[i] >= end temp_pier[i]    }    forall (i in phases : i - 1 in phases) {        start deck[i] >= end deck [i - 1]         start deck[i] >= end pier[i - 1]    }    // Temporary pier is a unique resource    forall (i in phases) {        end temp_pier[i] <= start disassemble_temp_pier[i]        end deck[i] <= start disassemble_temp_pier[i]    }    forall (i in phases : i - 1 in phases)        end disassemble_temp_pier[i - 1] <= start temp_pier[i]     // Setup abutment and construction side before decks are built    forall (i in phases) end abutment <= start deck[i]    // Pylons and stays    forall (i in phases) end deck[i] <= start everything_else}

### Exercise​

Move the the tasks in the gantt chart until you find the optimal schedule for the Millau viaduct with a minimum lateness objective. We have limited the problem to 3 decks to make it simpler and make the gantt smaller.

### Benchmarks​

There are many variants of the project scheduling problem. The bechmmark section of the website explains the context in which each variant appears, and provides benchmark data as well as the current OptalCP results.