Optimization in or-tools (reminder)

Branch and Bound in or-tools works via a search monitor

In detail:

m = slv.Minimize(<variable>, <step>) # Minimization
m = slv.Maximize(<variable>, <step>) # Maximization
...
slv.NewSearch(<dec builder>, [m, <other mon.>])

Instead of a cost function, we have a cost variable

• Cost function implemented by posting a constraint

The <step> parameter represents the required improvement

• Bounding constraint (minimization): $z \leq zbest - step$

Meta-constraints in or-tools (reminder)

Reified constraints in or-tools

• Not all constraints can be reified!
• But many of them can

We just need to use the constraint as a term in an expression

• Usually, this requires adding brackets

expr = 2 * (x <= y)

• (x <= y) represents the feasibility state of $x \leq y$
• It can be used like any other expression

Max/Min operators in or-tools (reminder)

Just a word of warning:

The sum function in python repeatedl applies +

• Since + is redefined in or-tools...
• ...we can use sum to build expressions

In python min and max are functions, not operators

• Hence, they are not redefined in or-tools
• Istead, we have ad-hoc functions in the solver API

slv.Min(<expr/var>, <expr/var>) # Binary min
slv.Min(<list of vars>) # Min with many terms
slv.Max(<expr/var>, <expr/var>) # Binary max
slv.Max(<list of vars>) # Max with many terms

Constraint Systems

Lab 3 - A Production Scheduling Problem

Production Line Scheduling

A small company can produce a number of product types

Production Line Scheduling

A small company can produce a number of product types

• Every time unit, only a single product unit can be manufactured

The company has received a number of orders

• Each order refers to a single product type
• Each order requires a certain number of product units
• Each order has a deadline, which cannot be exceeded

Some pairs of products $\langle p1, p2 \rangle$ are associated to a setup time:

• After manufacturing a unit of $p1$, before switching to $p2$
• We need to wait 1 time unit, or to manufacture another product type

Production Line Scheduling

A small company can produce a number of product types

Goal:

• Model & solve the problem using CP
• Satisfy all constraints
• Minimize the makespan