# Forall and sets

After completing this module the student should:

• Understand forall statements
• Understand sets

## Transcript

For this module, assume that you are in charge of evacuating a set of resources (persons, cargo and wheelchair bound people) from a a small town due to a coming flood. At you disposal you may hire big taxis, busses and trucks, each associated with a cost.

### Sets

Let us represent each vehicle and resource as a string, thus creating two sets:

{string} vehicles = {"Trucks","Taxis","Busses"};
{string} toBeTransported = {"Cargo","Passenger","Wheelchairs"};


These sets can be used in much the same way as ranges. This we will use to describe how much each vehicle can carry.

• Trucks can carry 100 units of cargo and 1 passenger.
• Taxis can transport one unit of cargo, four passengers and two wheelchairs.
• Busses can carry 10 units of cargo, 50 passengers and one wheelchair user.

There is a need to transport 1000 units of cargo, 800 passengers and 20 wheelchair users. This is represented as an array:

int neededCapacity[toBeTransported] = [1000,800,20];


Note how we used the set of strings just as we would have a range. Contrary to mathematical sets, when defining them, the order of the items will matter.

For the capacities of the vehicles, we need to map a vehicle and a resource to be transported to a number. This is usually done using matrices, and will in practice be done using an array of arrays.

int capacities[toBeTransported][vehicles] = [
[100 ,1, 10],
[1   ,4, 50],
[0   ,2,  1]];


The spaces and new lines in the above can be removed costing only readability.

The final data we need to define is an array of costs. One for each vehicle.

int cost[vehicles] = [10000, 1100, 10000];


As you can see by matching this with the definition of vehicles, that taxis are somewhat cheaper than trucks and busses.

Finally we need to define what decisions we want to make. In this case it is how many of each type of vehicles to use:

dvar int+ nUsed[vehicles];


As you can see, the type int+ as we need an integer number of vehicles greater than zero.

At this stage you should be able to define the objective function as:

minimize
sum(v in vehicles) cost[v]*nUsed[v];


But for the constraints we need a new tool.

### Foralls

We need a constraint for all the resources to be transported:

subject to {
forall(t in toBeTransported)
sum(v in vehicles) nUsed[v]*capacities[t][v] >= neededCapacity[t];
};


The forall will create a new constraint for each value of t selected from toBeTransported, inserted into the following line/block of code. In this case three copies of the following line will be generated behind the scenes:

sum(v in vehicles) nUsed[v]*capacities[t][v] >= neededCapacity[t];


One for t="Cargo" one for t="Passenger" and finally one for t="Wheelchairs". If needed, foralls can be nested. That is to say, a forall can contain another forall.

forall(t in toBeTransported)
forall(v in vehicles)
// Some constraint


Or equivalent (and preferred):

forall(t in toBeTransported, v in vehicles)
// Some constraints


The final model will look like this:

// Sets of vehicles and resources
{string} vehicles = {"Trucks","Taxis","Busses"};
{string} toBeTransported = {"Cargo","Passenger","Wheelchairs"};

// Problem data
int capacities[toBeTransported][vehicles] = [[100,1,10],[1,4,50],[0,2,1]];
int neededCapacity[toBeTransported] = [1000,800,20];

// A list of the costs of the vehicles. One entry per "vehicle"
int cost[vehicles] = [10000, 1100, 10000];

// How many vehicles to use of each type?
dvar int+ nUsed[vehicles];

minimize
sum(v in vehicles) cost[v]*nUsed[v];
subject to {
forall(t in toBeTransported)
sum(v in vehicles) nUsed[v]*capacities[t][v] >= neededCapacity[t];
};


### Conditional operator

As with sums, foralls can contain the conditional operator :.

forall(t in toBeTransported: neededCapacity[t]>10)


would make the forall ignore any resource for which the needed amount is 10 or less.

## Test

Implement an solve the following model.

$\textrm{maximize } \sum_{i=0}^{20} i \cdot x_i$

$\textrm{subject to }$

$\sum_{i=j}^{j+4} x_i \geq 2 \quad \quad \forall j \in ( 1,4,6,5,9,15 )$

$\sum_{i \in (1,3,5,7,9,11,13,15,17,19) } x_i \geq 7$

$\sum_{i=0}^{20} x_i \leq 15$

$x \in {0,1}$