Forall and sets

After completing this module the student should:


Video

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.

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}$