Scheduling with IBM ILOG CPLEX Optimization Studio

The model files

Model files (.mod extension) contain all of the OPL statements. The following components are usually present in a model file:

• the declarations of data

• the declarations of decision variables

• the declaration of engine

• an objective function

• the constraints

• script statements.

The data, the objective function, and scripting statements are not mandatory.

Declarations of data

Data declarations allow you to name your data so that you can reference it easily in your model. For example, if your data in a table defines the cost of shipping one unit of material from location i to location j, you might want to call your item of data costij where i=1,..., n, j=1,..., n, and n is the number of locations in your model. You tell OPL that your model uses this data by declaring:

   int n = ... ;
   float cost[1..n][1..n] = ... ;

The … (ellipsis) means that the actual values for your table are located in a data file, which must be listed in the current project.

You could also list the data explicitly in the model file. However, it is recommended that you construct model files without specifying values for data so that you can later easily solve many instances of the same model by simply changing the data file.

Declarations of decision variables

Variable declarations name and define the type of each variable in the model. For example, if you want to create a variable that equals the amount of material shipped from location i to location j, you can create a variable named shipij:

   dvar int+ ship[1..n][1..n];

The dvar keyword indicates that you are declaring a decision variable. Since int+ indicates that the variables are nonnegative, this statement declares an array of nonnegative integer variables.

There is a restriction for constraint programming in OPL; float decision variables cannot be used. Instead, if you need to set constraints on float expressions, you should use float dexpr; see the section Integer and float expressions in the Language Reference Manual.

For scheduling there are specific additional decision variables, namely:

• interval

• sequence

In OPL, activities, operations and tasks are represented as interval decision variables.

An interval has a start, an end, a length, and a size. An interval variable allows for these values to be variable within the model. The start is the lower endpoint of the interval and the end is the upper endpoint of the interval. By default, the size is equal to the length, which is the difference between the end and the start of the interval. In general, the size is a lower bound on the length.

Also, an interval variable may be optional, and whether or not an interval is present in the solution is represented by a decision variable. If an interval is not present in the solution, this means that any constraints on this interval acts like the interval is “not there.” The exact semantics will depend on the specific constraint.

The following example contains a two-dimensional array of interval decision variables where the sizes of the interval variables are fixed:

dvar interval itvs  [h in Houses][t in TaskNames] size Duration[t];

Declaration of engine

A scheduling model starts with the declaration of the engine as follows:

using CP;

This declaration tells OPL to use the CP engine to solve the problem. In addition, it allows the use of constraints that are specific to constraint programming or to scheduling.

Objective function

The objective function is an expression that you want to optimize. This function must consist of variables and data that you have declared earlier in the model file. The objective function is introduced by either the minimize or the maximize keyword. For example:

   minimize endOf(tasks["moving"]);

This statement indicates that you want to minimize the end of the interval variable tasks["moving"].

Constraints

Constraints indicate the conditions necessary for a feasible solution to your model. You declare constraints within a subject to block. For example:

   subject to {
     forall(t in Tasks)
       forall(s in successors[t])
         endBeforeStart(tasks[t], tasks[s]);
   }

This statement declares one set of precedence constraints.

Several types of constraints can be placed on interval variables:

• precedence constraints, which ensure that relative positions of intervals in the solution (For example a precedence constraint can model a requirement that an interval a must end before interval b starts, optionally with some minimum delay z);

• no overlap constraints, which ensure that positions of intervals in the solution are disjointed in time;

• span constraints, which ensure that one interval to cover those intervals in a set of intervals;

• alternative constraints, which ensure that exactly one of a set of intervals be present in the solution;

• synchronize constraints, which ensure that a set of intervals start and end at the same time as a given interval variable if it is present in the solution;

• cumulative expression constraints, which restrict the bounds on the domains of cumulative expressions.

Script statements

Between the various blocks of a model (declaration of data, declaration of variables, constraints) or after the constraints, it is possible to add some script statements. This is useful for instance to preprocess input data, display it, or to display result data. These statements are written in IBM ILOG Script, an extension of the JavaScript language for OPL.

IBM ILOG Script for OPL enables you to:

• add preprocessing instructions to prepare data for the model;

• control the flow while the model is solved;

• set CPLEX parameters, CP Optimizer parameters, CP Optimizer search phases, and OPL options;

• add postprocessing instructions to aggregate, transform, and format data (including results data) for display or for sending to another application, for example, a spreadsheet;

• solve repeated instances of the same model;

• create algorithmic solutions where the output of one model instance is used as the input of a second model instance.

When you use IBM ILOG Script for OPL, you avoid having to compile and link; you just add script statements to your model file.

There are two possible top-level statements:

• the main statement for a flow control script, and

• the execute statement for preprocessing and postprocessing scripts.

   minimize endOf(tasks["moving"]);
   subject to {
     ...
   }
   
   execute DISPLAY {
     writeln("end=", tasks["moving"].end);
   }

Data files

You can organize large problems better by separating the model of the problem from the instance data. In this case, you store the instance data in one or more data files (.dat extension). Data files store the actual values of the data used in the model. A data file will look something like this:

  n = 3;

  c = [[0.0 1.5 2.3]
      [1.5 0.0 3.7]
      [2.3 3.7 0.0]];

Each data file may specify one or more connections to data sources, such as a relational database or a spreadsheet, to read and write data. From the IDE, you can export external data and internal data to a .dat file, which you can later use as input. Only the data actually used in the model is exported to data files.

Description of the problem

The problem is a house building problem in which there are ten tasks of fixed size, each of which needs to be assigned a starting time. The statements for creating the interval variables that represent the tasks are:

using CP;

dvar interval masonry    size 35;
dvar interval carpentry  size 15;
dvar interval plumbing   size 40;
dvar interval ceiling    size 15;
dvar interval roofing    size 5;
dvar interval painting   size 10;
dvar interval windows    size 5;
dvar interval facade     size 10;
dvar interval garden     size 5;
dvar interval moving     size 5;

Adding the constraints

The constraints in this problem are precedence constraints; some tasks cannot start until other tasks have ended. For example, the ceilings must be completed before painting can begin. The set of precedence constraints for this problem can be added to the model with the block:

subject to {
  endBeforeStart(masonry,   carpentry);
  endBeforeStart(masonry,   plumbing);
  endBeforeStart(masonry,   ceiling);
  endBeforeStart(carpentry, roofing);
  endBeforeStart(ceiling,   painting);
  endBeforeStart(roofing,   windows);
  endBeforeStart(roofing,   facade);
  endBeforeStart(plumbing,  facade);
  endBeforeStart(roofing,   garden);
  endBeforeStart(plumbing,  garden);
  endBeforeStart(windows,   moving);
  endBeforeStart(facade,    moving);
  endBeforeStart(garden,    moving);
  endBeforeStart(painting,  moving);
}

Here there is a special constraint, endBeforeStart, which ensures that one interval variable ends before the other starts. This constraint has a special treatment in the engine. One reason is to correctly treat the presence of intervals so that if one of the interval variables is not present, the constraint is automatically satisfied, and another reason is for stronger inference in constraint propagation.

Displaying the solution

The interval variables and precedence constraints completely describe this simple problem. An execute block is used to display a solution to the model, after values have been assigned to the start and end of each of the interval variables in the model. The last part of the code for this example is:

execute {
  writeln("Masonry  : " + masonry.start   + ".." + masonry.end);
  writeln("Carpentry: " + carpentry.start + ".." + carpentry.end);
  writeln("Plumbing : " + plumbing.start  + ".." + plumbing.end);
  writeln("Ceiling  : " + ceiling.start   + ".." + ceiling.end);
  writeln("Roofing  : " + roofing.start   + ".." + roofing.end);
  writeln("Painting : " + painting.start  + ".." + painting.end);
  writeln("Windows  : " + windows.start   + ".." + windows.end);
  writeln("Facade   : " + facade.start    + ".." + facade.end);
  writeln("Garden   : " + garden.start    + ".." + garden.end);
  writeln("Moving   : " + moving.start    + ".." + moving.end);
}

Executing the example

Run the example model <Install_dir>/opl/examples/opl/sched_intro/sched_intro.mod either by loading it in the IDE or by using the executable oplrun. When you run the model, you should get results similar to this output:

<<< setup


<<< generate

 ! ----------------------------------------------------------------------------
 ! Satisfiability problem - 10 variables, 14 constraints
 ! Initial process time : 0.00s (0.00s extraction + 0.00s propagation)
 !  . Log search space  : 300.0 (before), 300.0 (after)
 !  . Memory usage      : 283.0 Kb (before), 283.0 Kb (after)
 ! ----------------------------------------------------------------------------
 !   Branches  Non-fixed                Branch decision
 *         13      0.00s                         -
 ! ----------------------------------------------------------------------------
 ! Solution status        : Terminated normally, solution found
 ! Number of branches     : 13
 ! Number of fails        : 0
 ! Total memory usage     : 432.3 Kb (315.0 Kb CP Optimizer + 117.3 Kb Concert)
 ! Time spent in solve    : 0.00s (0.00s engine + 0.00s extraction)
 ! Search speed (br. / s) : 1300.0
 ! ----------------------------------------------------------------------------

<<< solve



OBJECTIVE: no objective
Masonry  : 0..35
Carpentry: 35..50
Plumbing : 35..75
Ceiling  : 35..50
Roofing  : 50..55
Painting : 50..60
Windows  : 55..60
Facade   : 75..85
Garden   : 75..80
Moving   : 85..90

<<< post process

To understand the solution found by OPL to this satisfiability scheduling problem, consider the line:

  Masonry  : 0..35

The interval variable representing the masonry task, which has size 35, has been assigned the interval [0,35). Masonry starts at time 0 and ends at the time point 35.

In subsequent sections, the log output is not included. You can view the log information when you run the completed projects.