# 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.

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`

.

After propagation the task becomes

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

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 .. 10`

dvar interval B in 0 .. 20 length 5 .. 10

constraints {

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`

.

## Search

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**

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:

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

## 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)$

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 lib`

const model = new CP.Model // create an empty model

const x = <IntervalVar> Array (10) // create decision variables

for (let i = 0; i < 10; i++)

x[i] = model.intervalVar({ length: 2, name: `x${i}` })

model.minimize(model.max(x)) // define objective

for (let i = 1; i < 10; i++) x[i-1].endBeforeStart(x[i]) // add constraints

CP.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 variables`

minimize max (i in 1 .. 10) end x[i] // define objective

constraints {

forall (i in 2 .. 10) end x[i - 1] <= start x[i] // add constraints

}

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

**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.**

*strongly*## 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 partnersThe 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

### 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 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_pier`

dvar interval temp_pier [0 .. n - 1] length build_temp_pier

dvar interval deck [0 .. n - 1] length position_deck

forall (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_pier`

forall (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_abutment`

dvar interval everything_else length others

forall (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

- OPtaL
- TypeScript

`int build_pier = 10`

int build_temp_pier = 4

int unbuild_temp_pier = 2

int position_deck = 4

int setup_abutment = 2

int others = 10

int n = 7

range phases = 1 .. n

dvar interval pier [phases] length build_pier

dvar interval temp_pier [phases] length build_temp_pier

dvar interval disassemble_temp_pier [phases] length unbuild_temp_pier

dvar interval deck [phases] length position_deck

dvar interval abutment length setup_abutment

dvar interval everything_else length others

minimize end everything_else

constraints {

// 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

}

Explicitly marking sections in the source code (Data, Model, variables, Objective, Constraints, Solve) may seem overkill for small pieces of code but will allow you to quickly understand what you are looking at in larger models. Hence we recommend getting used to adding them

`import * as CP from '@optal/cp'`

//////////

// Data //

//////////

// Parameters

const build_pier = 10

const build_temp_pier = 4

const unbuild_temp_pier = 2

const position_deck = 4

const setup_abutment = 2

const others = 10

const n = 7

///////////

// Model //

///////////

const model = new CP.Model

////////////////////////

// Decision variables //

////////////////////////

const pier = <IntervalVar> Array (n)

const temp_pier = <IntervalVar> Array (n)

const disassemble_temp_pier = <IntervalVar> Array (n)

const deck = <IntervalVar> Array (n)

const abutment = IntervalVar ({ length: setup_abutment })

const everything_else = IntervalVar ({ length: others })

// Initializations

for (let i = 0; i < n; i++) {

pier[n] = IntervalVar({ length: build_pier })

temp_pier[n] = IntervalVar({ length: build_temp_pier })

disassemble_temp_pier[n] = IntervalVar({ length: unbuild_temp_pier })

deck[n] = IntervalVar({ length: position_deck })

}

///////////////

// Objective //

///////////////

model.minimize(everything_else.end)

/////////////////

// Constraints //

/////////////////

// Deck is built on top of piers and after previous deck

for (let i = 0; i < n; i++) {

if (i > 0) deck[i - 1].endBeforeStart(deck[i])

pier[i].endBeforeStart(deck[i])

temp_pier[i].endBeforeStart(deck[i])

if (i > 0) pier[i - 1].endBeforeStart(deck[i]) // pier[-1] is the abutment

}

// Temporary pier is a unique resource

for (let i = 0; i < n; i++) {

temp_pier[i].endBeforeStart(disassemble_temp_pier[i])

deck[i].endBeforeStart(disassemble_temp_pier[i])

if (i > 0) disassemble_temp_pier[i].endBeforeStart(temp_pier[i])

}

// Setup abutment and construction side before decks are built

for (let i = 0; i < n; i++) abutment.endBeforeStart(deck[i])

// Pylons and stays

for (let i = 0; i < n; i++) deck[i].endBeforeStart(everything_else)

///////////

// Solve //

///////////

CP.solve(model)

It is very tempting in JavaScript to write the constraints in an enormous single `for`

loop given that it each constraint start with one. We strongly recommend not doing it.
The performance improvement is negligible for an important loss of readability

It just as tempting to adopt an *interleaved style* that
alternates between variable definitions and constraints. We strongly
advice against it, per experience people get lost in larger models written this way.

Generally speaking the free form and verbosity of JavaScript / Typescript models is a lurking danger that comes back to bite you once the project has grown and multiple people are working on it.

### 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.