Function: propagate()

propagate(model: Model, parameters?: Parameters, log?: null | WritableStream): Promise <PropagationResult>

Computes domains after constraint propagation.

Parameters

Parameter	Type	Description
model	Model	The model to propagate.
parameters?	Parameters	The parameters to use for propagation.
log?	null | WritableStream	The stream to which the solver output should be redirected. When
undefined then the output is printed to the standard output. When null
then the output is suppressed.

Returns

Promise <PropagationResult>

The result of propagation.

Remarks

Propagation removes infeasible values from variable domains. In general, it shrinks the domains but it doesn't fix variables to values. In some cases propagation can prove that the model is infeasible.

Sometimes it may be useful to check what the solver can compute by constraint propagation and what it cannot. For example, if some obviously infeasible values are not removed from variable domains then some redundant constraint can be added.

Example

In the following example, we have 4 tasks task[0], task[1], task[2], task[3], and 2 workers. Each task can be assigned to any worker and the tasks can be processed in any order. All tasks have length 10 and must finish before time 19.

In the first model we will use constraints Model.alternative to chose a worker for each tasks. And we check that constraint propagation correctly propagates the length of the tasks to the workers.

let model = new CP.Model();
const nbTasks = 4;

// For each task we will create three interval variables:
//   * tasks[i]: the task itself
//   * tasksWorker1[i]: the task if executed by worker1
//   * tasksWorker2[i]: the task if executed by worker2
let tasks: CP.IntervalVar[] = [];
let tasksWorker1: CP.IntervalVar[] = [];
let tasksWorker2: CP.IntervalVar[] = [];

for (let i = 0; i < nbTasks; i++) {
  // Create the task itself. It has length 10 and must finish before 19:
  tasks.push(model.intervalVar({ name: "Task" + (i + 1), length: 10, end: [, 19] }));
  // Create the variables for workers. Those variables are optional
  // since we don't know which worker will execute the task.
  // Notice that we don't specify the length of those interval variables.
  tasksWorker1.push(model.intervalVar({ name: "Task" + (i + 1) + "Worker1", optional: true }));
  tasksWorker2.push(model.intervalVar({ name: "Task" + (i + 1) + "Worker2", optional: true }));
  // Alternative constraint between the task and the two worker variables
  // makes sure that exactly one of the two workers executes the task:
  model.alternative(tasks[i], [tasksWorker1[i], tasksWorker2[i]]);
  // All tasks must finish before the time 19:
  model.constraint(model.le(tasks[i].end(), 19));
}

// Tasks of each worker cannot overlap:
model.noOverlap(tasksWorker1);
model.noOverlap(tasksWorker2);

try {

  // Propagate using the maximum propagation on noOverlap constraint:
  let result = await CP.propagate(model, { noOverlapPropagationLevel: 4 });
  if (typeof result.domains === "string") {
    // The model is infeasible or a timeout occurred:
    console.log("The result of the propagation is: " + result.domains);
  } else {
    // Check computed length of one of the optional tasks:
    console.log("Length of Task1Worker1 is: " +
      result.domains.getLengthMin(tasksWorker1[0]) + ".." + result.domains.getLengthMax(tasksWorker1[0]));
  }

} catch (e) {
  // In case of an error CP.propagate returns a rejected promise so an exception is thrown
  console.log("Error caught: " + e);
}

The output of the program is:

Length of Task1Worker1 is: 10..10

As we can see, the length 10 is correctly propagated from Task1 to Task1Worker1. However propagation did not prove that the model is infeasible: there is no way to execute four tasks of length 10 before time 19 using only 2 workers.

Let's remodel this problem using a cumulative constraint. The idea is that the workers are interchangeable and we can assign tasks to workers in postprocessing.

let model = new CP.Model();
const nbTasks = 4;

// For each task we will create an interval variable
// and also a pulse for cumulative constraint:
let tasks: CP.IntervalVar[] = [];
let pulses: CP.CumulExpr[] = [];

for (let i = 0; i < nbTasks; i++) {
  // Create the task. It has length 10 and must finish before 19:
  tasks.push(model.intervalVar({ name: "Task" + (i + 1), length: 10, end: [, 19] }));
  // And its pulse:
  pulses.push(tasks[i].pulse(1));
}

// Cumulative constraint makes sure that we don't use more than 2 workers at a time:
model.cumulSum(pulses).cumulLe(2);

try {

  // Propagate using the maximum propagation for cumul constraints:
  let result = await CP.propagate(model, { cumulPropagationLevel: 3});
  if (typeof result.domains === "string") {
    // The model is infeasible or a timeout occurred:
    console.log("The result of the propagation is: " + result.domains);
  } else
    console.log("The propagation did not detect infeasibility.");

} catch (e) {
  // In case of an error CP.propagate returns a rejected promise so an exception is thrown
  console.log("Error caught: " + e);
}

This time the output is:

The result of the propagation is: infeasible

As we can see, this model propagates more then the previous one.