| home | boolean logic | integer arithmetic | channeling constraints | scheduling | Using the CP-SAT solver | Model manipulation | Troubleshooting | Python API |
|---|
https://developers.google.com/optimization/
Scheduling in Operations Research involves problems of tasks, resources and times. In general, scheduling problems have the following features: fixed or variable durations, alternate ways of performing the same task, mutual exclusivity between tasks, and temporal relations between tasks.
Intervals are constraints containing three constant of affine expressions
(start, size, and end). Creating an interval constraint will enforce that
start + size == end.
The more general API uses three expressions to define the interval. If the size is fixed, a simpler API uses the start expression and the fixed size.
Creating these intervals is illustrated in the following code snippets.
#!/usr/bin/env python3
"""Code sample to demonstrates how to build an interval."""
from ortools.sat.python import cp_model
def interval_sample_sat():
"""Showcases how to build interval variables."""
model = cp_model.CpModel()
horizon = 100
# An interval can be created from three affine expressions.
start_var = model.new_int_var(0, horizon, "start")
duration = 10 # Python cp/sat code accept integer variables or constants.
end_var = model.new_int_var(0, horizon, "end")
interval_var = model.new_interval_var(start_var, duration, end_var + 2, "interval")
print(f"interval = {repr(interval_var)}")
# If the size is fixed, a simpler version uses the start expression and the
# size.
fixed_size_interval_var = model.new_fixed_size_interval_var(
start_var, 10, "fixed_size_interval_var"
)
print(f"fixed_size_interval_var = {repr(fixed_size_interval_var)}")
# A fixed interval can be created using the same API.
fixed_interval = model.new_fixed_size_interval_var(5, 10, "fixed_interval")
print(f"fixed_interval = {repr(fixed_interval)}")
interval_sample_sat()#include <stdlib.h>
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/util/sorted_interval_list.h"
namespace operations_research {
namespace sat {
void IntervalSampleSat() {
CpModelBuilder cp_model;
const int kHorizon = 100;
const Domain horizon(0, kHorizon);
// An interval can be created from three affine expressions.
const IntVar x = cp_model.NewIntVar(horizon).WithName("x");
const IntVar y = cp_model.NewIntVar({2, 4}).WithName("y");
const IntVar z = cp_model.NewIntVar(horizon).WithName("z");
const IntervalVar interval_var =
cp_model.NewIntervalVar(x, y, z + 2).WithName("interval");
LOG(INFO) << "start = " << interval_var.StartExpr()
<< ", size = " << interval_var.SizeExpr()
<< ", end = " << interval_var.EndExpr()
<< ", interval_var = " << interval_var;
// If the size is fixed, a simpler version uses the start expression and the
// size.
const IntervalVar fixed_size_interval_var =
cp_model.NewFixedSizeIntervalVar(x, 10).WithName(
"fixed_size_interval_var");
LOG(INFO) << "start = " << fixed_size_interval_var.StartExpr()
<< ", size = " << fixed_size_interval_var.SizeExpr()
<< ", end = " << fixed_size_interval_var.EndExpr()
<< ", fixed_size_interval_var = " << fixed_size_interval_var;
// A fixed interval can be created using the same API.
const IntervalVar fixed_interval =
cp_model.NewFixedSizeIntervalVar(5, 10).WithName("fixed_interval");
LOG(INFO) << "start = " << fixed_interval.StartExpr()
<< ", size = " << fixed_interval.SizeExpr()
<< ", end = " << fixed_interval.EndExpr()
<< ", fixed_interval = " << fixed_interval;
}
} // namespace sat
} // namespace operations_research
int main() {
operations_research::sat::IntervalSampleSat();
return EXIT_SUCCESS;
}package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.IntervalVar;
import com.google.ortools.sat.LinearExpr;
/** Code sample to demonstrates how to build an interval. */
public class IntervalSampleSat {
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
CpModel model = new CpModel();
int horizon = 100;
// An interval can be created from three affine expressions.
IntVar startVar = model.newIntVar(0, horizon, "start");
IntVar endVar = model.newIntVar(0, horizon, "end");
IntervalVar intervalVar = model.newIntervalVar(
startVar, LinearExpr.constant(10), LinearExpr.newBuilder().add(endVar).add(2), "interval");
System.out.println(intervalVar);
// If the size is fixed, a simpler version uses the start expression and the size.
IntervalVar fixedSizeIntervalVar =
model.newFixedSizeIntervalVar(startVar, 10, "fixed_size_interval_var");
System.out.println(fixedSizeIntervalVar);
// A fixed interval can be created using another method.
IntervalVar fixedInterval = model.newFixedInterval(5, 10, "fixed_interval");
System.out.println(fixedInterval);
}
}using System;
using Google.OrTools.Sat;
public class IntervalSampleSat
{
static void Main()
{
CpModel model = new CpModel();
int horizon = 100;
// C# code supports constant of affine expressions.
IntVar start_var = model.NewIntVar(0, horizon, "start");
IntVar end_var = model.NewIntVar(0, horizon, "end");
IntervalVar interval = model.NewIntervalVar(start_var, 10, end_var + 2, "interval");
Console.WriteLine(interval);
// If the size is fixed, a simpler version uses the start expression, the size and the
// literal.
IntervalVar fixedSizeIntervalVar = model.NewFixedSizeIntervalVar(start_var, 10, "fixed_size_interval_var");
Console.WriteLine(fixedSizeIntervalVar);
// A fixed interval can be created using the same API.
IntervalVar fixedInterval = model.NewFixedSizeIntervalVar(5, 10, "fixed_interval");
Console.WriteLine(fixedInterval);
}
}// The interval_sample_sat_go command is a simple example of the Interval variable.
package main
import (
"fmt"
"github.com/golang/glog"
"ortools/sat/go/cpmodel"
)
const horizon = 100
func intervalSampleSat() error {
model := cpmodel.NewCpModelBuilder()
domain := cpmodel.NewDomain(0, horizon)
x := model.NewIntVarFromDomain(domain).WithName("x")
y := model.NewIntVar(2, 4).WithName("y")
z := model.NewIntVarFromDomain(domain).WithName("z")
// An interval can be created from three affine expressions.
intervalVar := model.NewIntervalVar(x, y, cpmodel.NewConstant(2).Add(z)).WithName("interval")
// If the size is fixed, a simpler version uses the start expression and the size.
fixedSizeIntervalVar := model.NewFixedSizeIntervalVar(x, 10).WithName("fixedSizeInterval")
// A fixed interval can be created using the same API.
fixedIntervalVar := model.NewFixedSizeIntervalVar(cpmodel.NewConstant(5), 10).WithName("fixedInterval")
m, err := model.Model()
if err != nil {
return fmt.Errorf("failed to instantiate the CP model: %w", err)
}
fmt.Printf("%v\n", m.GetConstraints()[intervalVar.Index()])
fmt.Printf("%v\n", m.GetConstraints()[fixedSizeIntervalVar.Index()])
fmt.Printf("%v\n", m.GetConstraints()[fixedIntervalVar.Index()])
return nil
}
func main() {
if err := intervalSampleSat(); err != nil {
glog.Exitf("intervalSampleSat returned with error: %v", err)
}
}An interval can be marked as optional. The presence of this interval is controlled by a literal. The no overlap and cumulative constraints understand these presence literals, and correctly ignore inactive intervals.
#!/usr/bin/env python3
"""Code sample to demonstrates how to build an optional interval."""
from ortools.sat.python import cp_model
def optional_interval_sample_sat():
"""Showcases how to build optional interval variables."""
model = cp_model.CpModel()
horizon = 100
# An interval can be created from three affine expressions.
start_var = model.new_int_var(0, horizon, "start")
duration = 10 # Python cp/sat code accept integer variables or constants.
end_var = model.new_int_var(0, horizon, "end")
presence_var = model.new_bool_var("presence")
interval_var = model.new_optional_interval_var(
start_var, duration, end_var + 2, presence_var, "interval"
)
print(f"interval = {repr(interval_var)}")
# If the size is fixed, a simpler version uses the start expression and the
# size.
fixed_size_interval_var = model.new_optional_fixed_size_interval_var(
start_var, 10, presence_var, "fixed_size_interval_var"
)
print(f"fixed_size_interval_var = {repr(fixed_size_interval_var)}")
# A fixed interval can be created using the same API.
fixed_interval = model.new_optional_fixed_size_interval_var(
5, 10, presence_var, "fixed_interval"
)
print(f"fixed_interval = {repr(fixed_interval)}")
optional_interval_sample_sat()#include <stdlib.h>
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/util/sorted_interval_list.h"
namespace operations_research {
namespace sat {
void OptionalIntervalSampleSat() {
CpModelBuilder cp_model;
const int kHorizon = 100;
const Domain horizon(0, kHorizon);
// An optional interval can be created from three affine expressions and a
// BoolVar.
const IntVar x = cp_model.NewIntVar(horizon).WithName("x");
const IntVar y = cp_model.NewIntVar({2, 4}).WithName("y");
const IntVar z = cp_model.NewIntVar(horizon).WithName("z");
const BoolVar presence_var = cp_model.NewBoolVar().WithName("presence");
const IntervalVar interval_var =
cp_model.NewOptionalIntervalVar(x, y, z + 2, presence_var)
.WithName("interval");
LOG(INFO) << "start = " << interval_var.StartExpr()
<< ", size = " << interval_var.SizeExpr()
<< ", end = " << interval_var.EndExpr()
<< ", presence = " << interval_var.PresenceBoolVar()
<< ", interval_var = " << interval_var;
// If the size is fixed, a simpler version uses the start expression and the
// size.
const IntervalVar fixed_size_interval_var =
cp_model.NewOptionalFixedSizeIntervalVar(x, 10, presence_var)
.WithName("fixed_size_interval_var");
LOG(INFO) << "start = " << fixed_size_interval_var.StartExpr()
<< ", size = " << fixed_size_interval_var.SizeExpr()
<< ", end = " << fixed_size_interval_var.EndExpr()
<< ", presence = " << fixed_size_interval_var.PresenceBoolVar()
<< ", interval_var = " << fixed_size_interval_var;
}
} // namespace sat
} // namespace operations_research
int main() {
operations_research::sat::OptionalIntervalSampleSat();
return EXIT_SUCCESS;
}package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.IntervalVar;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.Literal;
/** Code sample to demonstrates how to build an optional interval. */
public class OptionalIntervalSampleSat {
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
CpModel model = new CpModel();
int horizon = 100;
// An interval can be created from three affine expressions, and a literal.
IntVar startVar = model.newIntVar(0, horizon, "start");
IntVar endVar = model.newIntVar(0, horizon, "end");
Literal presence = model.newBoolVar("presence");
IntervalVar intervalVar = model.newOptionalIntervalVar(startVar, LinearExpr.constant(10),
LinearExpr.newBuilder().add(endVar).add(2), presence, "interval");
System.out.println(intervalVar);
// If the size is fixed, a simpler version uses the start expression, the size and the literal.
IntervalVar fixedSizeIntervalVar =
model.newOptionalFixedSizeIntervalVar(startVar, 10, presence, "fixed_size_interval_var");
System.out.println(fixedSizeIntervalVar);
// A fixed interval can be created using another method.
IntervalVar fixedInterval = model.newOptionalFixedInterval(5, 10, presence, "fixed_interval");
System.out.println(fixedInterval);
}
}using System;
using Google.OrTools.Sat;
public class OptionalIntervalSampleSat
{
static void Main()
{
CpModel model = new CpModel();
int horizon = 100;
// C# code supports constant of affine expressions.
IntVar start_var = model.NewIntVar(0, horizon, "start");
IntVar end_var = model.NewIntVar(0, horizon, "end");
BoolVar presence_var = model.NewBoolVar("presence");
IntervalVar interval = model.NewOptionalIntervalVar(start_var, 10, end_var + 2, presence_var, "interval");
Console.WriteLine(interval);
// If the size is fixed, a simpler version uses the start expression, the size and the
// literal.
IntervalVar fixedSizeIntervalVar =
model.NewOptionalFixedSizeIntervalVar(start_var, 10, presence_var, "fixed_size_interval_var");
Console.WriteLine(fixedSizeIntervalVar);
// A fixed interval can be created using the same API.
IntervalVar fixedInterval = model.NewOptionalFixedSizeIntervalVar(5, 10, presence_var, "fixed_interval");
Console.WriteLine(fixedInterval);
}
}// The optional_interval_sample_sat command is an example of an Interval variable that is
// marked as optional.
package main
import (
"fmt"
"github.com/golang/glog"
"ortools/sat/go/cpmodel"
)
const horizon = 100
func optionalIntervalSampleSat() error {
model := cpmodel.NewCpModelBuilder()
domain := cpmodel.NewDomain(0, horizon)
x := model.NewIntVarFromDomain(domain).WithName("x")
y := model.NewIntVar(2, 4).WithName("y")
z := model.NewIntVarFromDomain(domain).WithName("z")
presenceVar := model.NewBoolVar().WithName("presence")
// An optional interval can be created from three affine expressions and a BoolVar.
intervalVar := model.NewOptionalIntervalVar(x, y, cpmodel.NewConstant(2).Add(z), presenceVar).WithName("interval")
// If the size is fixed, a simpler version uses the start expression and the size.
fixedSizeIntervalVar := model.NewOptionalFixedSizeIntervalVar(x, 10, presenceVar).WithName("fixedSizeInterval")
m, err := model.Model()
if err != nil {
return fmt.Errorf("failed to instantiate the CP model: %w", err)
}
fmt.Printf("%v\n", m.GetConstraints()[intervalVar.Index()])
fmt.Printf("%v\n", m.GetConstraints()[fixedSizeIntervalVar.Index()])
return nil
}
func main() {
if err := optionalIntervalSampleSat(); err != nil {
glog.Exitf("optionalIntervalSampleSat returned with error: %v", err)
}
}Temporal relations between intervals can be expressions using linear inequalities involving the start and end expressions of the intervals.
As seen above, the factory methods on the model used to build intervals accept 1-var affine expression (a * var + b, a, b integer constants) as arguments to the start, size, and end parameters.
Once the interval is build, these same expressions can be queries using
StartExpr(), SizeExpr() and EndExpr() in C++ and C#, start_expr(), size_expr(), and end_expr() in python, and getStartExpr(), getSizeExpr(), and getEndExpr() in Java.
If one or both intervals are optional, then these inequalities must be reified by the presence literals of the optional intervals used.
#!/usr/bin/env python3
"""Builds temporal relations between intervals."""
from ortools.sat.python import cp_model
def interval_relations_sample_sat():
"""Showcases how to build temporal relations between intervals."""
model = cp_model.CpModel()
horizon = 100
# An interval can be created from three 1-var affine expressions.
start_var = model.new_int_var(0, horizon, "start")
duration = 10 # Python CP-SAT code accept integer variables or constants.
end_var = model.new_int_var(0, horizon, "end")
interval_var = model.new_interval_var(start_var, duration, end_var, "interval")
# If the size is fixed, a simpler version uses the start expression and the
# size.
fixed_size_start_var = model.new_int_var(0, horizon, "fixed_start")
fixed_size_duration = 10
fixed_size_interval_var = model.new_fixed_size_interval_var(
fixed_size_start_var,
fixed_size_duration,
"fixed_size_interval_var",
)
# An optional interval can be created from three 1-var affine expressions and
# a literal.
opt_start_var = model.new_int_var(0, horizon, "opt_start")
opt_duration = model.new_int_var(2, 6, "opt_size")
opt_end_var = model.new_int_var(0, horizon, "opt_end")
opt_presence_var = model.new_bool_var("opt_presence")
opt_interval_var = model.new_optional_interval_var(
opt_start_var, opt_duration, opt_end_var, opt_presence_var, "opt_interval"
)
# If the size is fixed, a simpler version uses the start expression, the
# size, and the presence literal.
opt_fixed_size_start_var = model.new_int_var(0, horizon, "opt_fixed_start")
opt_fixed_size_duration = 10
opt_fixed_size_presence_var = model.new_bool_var("opt_fixed_presence")
opt_fixed_size_interval_var = model.new_optional_fixed_size_interval_var(
opt_fixed_size_start_var,
opt_fixed_size_duration,
opt_fixed_size_presence_var,
"opt_fixed_size_interval_var",
)
# Simple precedence between two non optional intervals.
model.add(interval_var.start_expr() >= fixed_size_interval_var.end_expr())
# Synchronize start between two intervals (one optional, one not)
model.add(
interval_var.start_expr() == opt_interval_var.start_expr()
).only_enforce_if(opt_presence_var)
# Exact delay between two optional intervals.
exact_delay: int = 5
model.add(
opt_interval_var.start_expr()
== opt_fixed_size_interval_var.end_expr() + exact_delay
).only_enforce_if(opt_presence_var, opt_fixed_size_presence_var)
interval_relations_sample_sat()A no_overlap constraint simply states that all intervals are disjoint. It is built with a list of interval variables. Fixed intervals are useful for excluding part of the timeline.
In the following examples, you want to schedule 3 tasks on 3 weeks excluding weekends, making the final day as early as possible.
#!/usr/bin/env python3
"""Code sample to demonstrate how to build a NoOverlap constraint."""
from ortools.sat.python import cp_model
def no_overlap_sample_sat():
"""No overlap sample with fixed activities."""
model = cp_model.CpModel()
horizon = 21 # 3 weeks.
# Task 0, duration 2.
start_0 = model.new_int_var(0, horizon, "start_0")
duration_0 = 2 # Python cp/sat code accepts integer variables or constants.
end_0 = model.new_int_var(0, horizon, "end_0")
task_0 = model.new_interval_var(start_0, duration_0, end_0, "task_0")
# Task 1, duration 4.
start_1 = model.new_int_var(0, horizon, "start_1")
duration_1 = 4 # Python cp/sat code accepts integer variables or constants.
end_1 = model.new_int_var(0, horizon, "end_1")
task_1 = model.new_interval_var(start_1, duration_1, end_1, "task_1")
# Task 2, duration 3.
start_2 = model.new_int_var(0, horizon, "start_2")
duration_2 = 3 # Python cp/sat code accepts integer variables or constants.
end_2 = model.new_int_var(0, horizon, "end_2")
task_2 = model.new_interval_var(start_2, duration_2, end_2, "task_2")
# Weekends.
weekend_0 = model.new_interval_var(5, 2, 7, "weekend_0")
weekend_1 = model.new_interval_var(12, 2, 14, "weekend_1")
weekend_2 = model.new_interval_var(19, 2, 21, "weekend_2")
# No Overlap constraint.
model.add_no_overlap([task_0, task_1, task_2, weekend_0, weekend_1, weekend_2])
# Makespan objective.
obj = model.new_int_var(0, horizon, "makespan")
model.add_max_equality(obj, [end_0, end_1, end_2])
model.minimize(obj)
# Solve model.
solver = cp_model.CpSolver()
status = solver.solve(model)
if status == cp_model.OPTIMAL:
# Print out makespan and the start times for all tasks.
print(f"Optimal Schedule Length: {solver.objective_value}")
print(f"Task 0 starts at {solver.value(start_0)}")
print(f"Task 1 starts at {solver.value(start_1)}")
print(f"Task 2 starts at {solver.value(start_2)}")
else:
print(f"Solver exited with nonoptimal status: {status}")
no_overlap_sample_sat()#include <stdlib.h>
#include <cstdint>
#include "absl/types/span.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/sat/model.h"
#include "ortools/util/sorted_interval_list.h"
namespace operations_research {
namespace sat {
void NoOverlapSampleSat() {
CpModelBuilder cp_model;
const int64_t kHorizon = 21; // 3 weeks.
const Domain horizon(0, kHorizon);
// Task 0, duration 2.
const IntVar start_0 = cp_model.NewIntVar(horizon);
const int64_t duration_0 = 2;
const IntVar end_0 = cp_model.NewIntVar(horizon);
const IntervalVar task_0 =
cp_model.NewIntervalVar(start_0, duration_0, end_0);
// Task 1, duration 4.
const IntVar start_1 = cp_model.NewIntVar(horizon);
const int64_t duration_1 = 4;
const IntVar end_1 = cp_model.NewIntVar(horizon);
const IntervalVar task_1 =
cp_model.NewIntervalVar(start_1, duration_1, end_1);
// Task 2, duration 3.
const IntVar start_2 = cp_model.NewIntVar(horizon);
const int64_t duration_2 = 3;
const IntVar end_2 = cp_model.NewIntVar(horizon);
const IntervalVar task_2 =
cp_model.NewIntervalVar(start_2, duration_2, end_2);
// Week ends.
const IntervalVar weekend_0 = cp_model.NewIntervalVar(5, 2, 7);
const IntervalVar weekend_1 = cp_model.NewIntervalVar(12, 2, 14);
const IntervalVar weekend_2 = cp_model.NewIntervalVar(19, 2, 21);
// No Overlap constraint.
cp_model.AddNoOverlap(
{task_0, task_1, task_2, weekend_0, weekend_1, weekend_2});
// Makespan.
IntVar makespan = cp_model.NewIntVar(horizon);
cp_model.AddLessOrEqual(end_0, makespan);
cp_model.AddLessOrEqual(end_1, makespan);
cp_model.AddLessOrEqual(end_2, makespan);
cp_model.Minimize(makespan);
// Solving part.
Model model;
const CpSolverResponse response = SolveCpModel(cp_model.Build(), &model);
LOG(INFO) << CpSolverResponseStats(response);
if (response.status() == CpSolverStatus::OPTIMAL) {
LOG(INFO) << "Optimal Schedule Length: " << response.objective_value();
LOG(INFO) << "Task 0 starts at " << SolutionIntegerValue(response, start_0);
LOG(INFO) << "Task 1 starts at " << SolutionIntegerValue(response, start_1);
LOG(INFO) << "Task 2 starts at " << SolutionIntegerValue(response, start_2);
}
}
} // namespace sat
} // namespace operations_research
int main() {
operations_research::sat::NoOverlapSampleSat();
return EXIT_SUCCESS;
}package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.IntervalVar;
import com.google.ortools.sat.LinearExpr;
/**
* We want to schedule 3 tasks on 3 weeks excluding weekends, making the final day as early as
* possible.
*/
public class NoOverlapSampleSat {
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
CpModel model = new CpModel();
// Three weeks.
int horizon = 21;
// Task 0, duration 2.
IntVar start0 = model.newIntVar(0, horizon, "start0");
int duration0 = 2;
IntervalVar task0 = model.newFixedSizeIntervalVar(start0, duration0, "task0");
// Task 1, duration 4.
IntVar start1 = model.newIntVar(0, horizon, "start1");
int duration1 = 4;
IntervalVar task1 = model.newFixedSizeIntervalVar(start1, duration1, "task1");
// Task 2, duration 3.
IntVar start2 = model.newIntVar(0, horizon, "start2");
int duration2 = 3;
IntervalVar task2 = model.newFixedSizeIntervalVar(start2, duration2, "task2");
// Weekends.
IntervalVar weekend0 = model.newFixedInterval(5, 2, "weekend0");
IntervalVar weekend1 = model.newFixedInterval(12, 2, "weekend1");
IntervalVar weekend2 = model.newFixedInterval(19, 2, "weekend2");
// No Overlap constraint. This constraint enforces that no two intervals can overlap.
// In this example, as we use 3 fixed intervals that span over weekends, this constraint makes
// sure that all tasks are executed on weekdays.
model.addNoOverlap(new IntervalVar[] {task0, task1, task2, weekend0, weekend1, weekend2});
// Makespan objective.
IntVar obj = model.newIntVar(0, horizon, "makespan");
model.addMaxEquality(obj,
new LinearExpr[] {LinearExpr.newBuilder().add(start0).add(duration0).build(),
LinearExpr.newBuilder().add(start1).add(duration1).build(),
LinearExpr.newBuilder().add(start2).add(duration2).build()});
model.minimize(obj);
// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.solve(model);
if (status == CpSolverStatus.OPTIMAL) {
System.out.println("Optimal Schedule Length: " + solver.objectiveValue());
System.out.println("Task 0 starts at " + solver.value(start0));
System.out.println("Task 1 starts at " + solver.value(start1));
System.out.println("Task 2 starts at " + solver.value(start2));
}
}
}using System;
using Google.OrTools.Sat;
public class NoOverlapSampleSat
{
static void Main()
{
CpModel model = new CpModel();
// Three weeks.
int horizon = 21;
// Task 0, duration 2.
IntVar start_0 = model.NewIntVar(0, horizon, "start_0");
int duration_0 = 2;
IntVar end_0 = model.NewIntVar(0, horizon, "end_0");
IntervalVar task_0 = model.NewIntervalVar(start_0, duration_0, end_0, "task_0");
// Task 1, duration 4.
IntVar start_1 = model.NewIntVar(0, horizon, "start_1");
int duration_1 = 4;
IntVar end_1 = model.NewIntVar(0, horizon, "end_1");
IntervalVar task_1 = model.NewIntervalVar(start_1, duration_1, end_1, "task_1");
// Task 2, duration 3.
IntVar start_2 = model.NewIntVar(0, horizon, "start_2");
int duration_2 = 3;
IntVar end_2 = model.NewIntVar(0, horizon, "end_2");
IntervalVar task_2 = model.NewIntervalVar(start_2, duration_2, end_2, "task_2");
// Weekends.
IntervalVar weekend_0 = model.NewIntervalVar(5, 2, 7, "weekend_0");
IntervalVar weekend_1 = model.NewIntervalVar(12, 2, 14, "weekend_1");
IntervalVar weekend_2 = model.NewIntervalVar(19, 2, 21, "weekend_2");
// No Overlap constraint.
model.AddNoOverlap(new IntervalVar[] { task_0, task_1, task_2, weekend_0, weekend_1, weekend_2 });
// Makespan objective.
IntVar obj = model.NewIntVar(0, horizon, "makespan");
model.AddMaxEquality(obj, new IntVar[] { end_0, end_1, end_2 });
model.Minimize(obj);
// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
if (status == CpSolverStatus.Optimal)
{
Console.WriteLine("Optimal Schedule Length: " + solver.ObjectiveValue);
Console.WriteLine("Task 0 starts at " + solver.Value(start_0));
Console.WriteLine("Task 1 starts at " + solver.Value(start_1));
Console.WriteLine("Task 2 starts at " + solver.Value(start_2));
}
}
}// The no_overlap_sample_sat command is an example of the NoOverlap constraints.
package main
import (
"fmt"
"github.com/golang/glog"
cmpb "ortools/sat/cp_model_go_proto"
"ortools/sat/go/cpmodel"
)
const horizon = 21 // 3 weeks
func noOverlapSampleSat() error {
model := cpmodel.NewCpModelBuilder()
domain := cpmodel.NewDomain(0, horizon)
// Task 0, duration 2.
start0 := model.NewIntVarFromDomain(domain)
duration0 := cpmodel.NewConstant(2)
end0 := model.NewIntVarFromDomain(domain)
task0 := model.NewIntervalVar(start0, duration0, end0)
// Task 1, duration 4.
start1 := model.NewIntVarFromDomain(domain)
duration1 := cpmodel.NewConstant(4)
end1 := model.NewIntVarFromDomain(domain)
task1 := model.NewIntervalVar(start1, duration1, end1)
// Task 2, duration 3
start2 := model.NewIntVarFromDomain(domain)
duration2 := cpmodel.NewConstant(2)
end2 := model.NewIntVarFromDomain(domain)
task2 := model.NewIntervalVar(start2, duration2, end2)
// Weekends.
weekend0 := model.NewFixedSizeIntervalVar(cpmodel.NewConstant(5), 2)
weekend1 := model.NewFixedSizeIntervalVar(cpmodel.NewConstant(12), 2)
weekend2 := model.NewFixedSizeIntervalVar(cpmodel.NewConstant(19), 2)
// No Overlap constraint.
model.AddNoOverlap(task0, task1, task2, weekend0, weekend1, weekend2)
// Makespan.
makespan := model.NewIntVarFromDomain(domain)
model.AddLessOrEqual(end0, makespan)
model.AddLessOrEqual(end1, makespan)
model.AddLessOrEqual(end2, makespan)
model.Minimize(makespan)
// Solve.
m, err := model.Model()
if err != nil {
return fmt.Errorf("failed to instantiate the CP model: %w", err)
}
response, err := cpmodel.SolveCpModel(m)
if err != nil {
return fmt.Errorf("failed to solve the model: %w", err)
}
if response.GetStatus() == cmpb.CpSolverStatus_OPTIMAL {
fmt.Println(response.GetStatus())
fmt.Println("Optimal Schedule Length: ", response.GetObjectiveValue())
fmt.Println("Task 0 starts at ", cpmodel.SolutionIntegerValue(response, start0))
fmt.Println("Task 1 starts at ", cpmodel.SolutionIntegerValue(response, start1))
fmt.Println("Task 2 starts at ", cpmodel.SolutionIntegerValue(response, start2))
}
return nil
}
func main() {
if err := noOverlapSampleSat(); err != nil {
glog.Exitf("noOverlapSampleSat returned with error: %v", err)
}
}A cumulative constraint takes a list of intervals, and a list of demands, and a capacity. It enforces that at any time point, the sum of demands of tasks active at that time point is less than a given capacity.
Modeling a non constant max profile can be done using fixed (interval, demand) to occupy the capacity between the actual profile and it max capacity.
Modeling a non zero min profile can be done using fixed (interval, demand) on the complementary cumulative constraint.
#!/usr/bin/env python3
"""Solves a scheduling problem with a min and max profile for the work load."""
import io
from absl import app
import pandas as pd
from ortools.sat.python import cp_model
def create_data_model() -> tuple[pd.DataFrame, pd.DataFrame, pd.DataFrame]:
"""Creates the dataframes that describes the model."""
max_load_str: str = """
start_hour max_load
0 0
2 0
4 3
6 6
8 8
10 12
12 8
14 12
16 10
18 6
20 4
22 0
"""
min_load_str: str = """
start_hour min_load
0 0
2 0
4 0
6 0
8 3
10 3
12 1
14 3
16 3
18 1
20 1
22 0
"""
tasks_str: str = """
name duration load priority
t1 60 3 2
t2 180 2 1
t3 240 5 3
t4 90 4 2
t5 120 3 1
t6 300 3 3
t7 120 1 2
t8 100 5 2
t9 110 2 1
t10 300 5 3
t11 90 4 2
t12 120 3 1
t13 250 3 3
t14 120 1 2
t15 40 5 3
t16 70 4 2
t17 90 8 1
t18 40 3 3
t19 120 5 2
t20 60 3 2
t21 180 2 1
t22 240 5 3
t23 90 4 2
t24 120 3 1
t25 300 3 3
t26 120 1 2
t27 100 5 2
t28 110 2 1
t29 300 5 3
t30 90 4 2
"""
max_load_df = pd.read_table(io.StringIO(max_load_str), sep=r"\s+")
min_load_df = pd.read_table(io.StringIO(min_load_str), sep=r"\s+")
tasks_df = pd.read_table(io.StringIO(tasks_str), index_col=0, sep=r"\s+")
return max_load_df, min_load_df, tasks_df
def check_solution(
tasks: list[tuple[int, int, int]],
min_load_df: pd.DataFrame,
max_load_df: pd.DataFrame,
period_length: int,
horizon: int,
) -> bool:
"""Checks the solution validity against the min and max load constraints."""
minutes_per_hour = 60
actual_load_profile = [0 for _ in range(horizon)]
min_load_profile = [0 for _ in range(horizon)]
max_load_profile = [0 for _ in range(horizon)]
# The complexity of the checker is linear in the number of time points, and
# should be improved.
for task in tasks:
for t in range(task[1]):
actual_load_profile[task[0] + t] += task[2]
for row in max_load_df.itertuples():
for t in range(period_length):
max_load_profile[row.start_hour * minutes_per_hour + t] = row.max_load
for row in min_load_df.itertuples():
for t in range(period_length):
min_load_profile[row.start_hour * minutes_per_hour + t] = row.min_load
for time in range(horizon):
if actual_load_profile[time] > max_load_profile[time]:
print(
f"actual load {actual_load_profile[time]} at time {time} is greater"
f" than max load {max_load_profile[time]}"
)
return False
if actual_load_profile[time] < min_load_profile[time]:
print(
f"actual load {actual_load_profile[time]} at time {time} is"
f" less than min load {min_load_profile[time]}"
)
return False
return True
def main(_) -> None:
"""Create the model and solves it."""
max_load_df, min_load_df, tasks_df = create_data_model()
# Create the model.
model = cp_model.CpModel()
# Get the max capacity from the capacity dataframe.
max_load = max_load_df.max_load.max()
print(f"Max capacity = {max_load}")
print(f"#tasks = {len(tasks_df)}")
minutes_per_hour: int = 60
horizon: int = 24 * 60
# Variables
starts = model.new_int_var_series(
name="starts",
lower_bounds=0,
upper_bounds=horizon - tasks_df.duration,
index=tasks_df.index,
)
performed = model.new_bool_var_series(name="performed", index=tasks_df.index)
intervals = model.new_optional_fixed_size_interval_var_series(
name="intervals",
index=tasks_df.index,
starts=starts,
sizes=tasks_df.duration,
are_present=performed,
)
# Set up the max profile. We use fixed (intervals, demands) to fill in the
# space between the actual max load profile and the max capacity.
time_period_max_intervals = model.new_fixed_size_interval_var_series(
name="time_period_max_intervals",
index=max_load_df.index,
starts=max_load_df.start_hour * minutes_per_hour,
sizes=minutes_per_hour * 2,
)
time_period_max_heights = max_load - max_load_df.max_load
# Cumulative constraint for the max profile.
model.add_cumulative(
intervals.to_list() + time_period_max_intervals.to_list(),
tasks_df.load.to_list() + time_period_max_heights.to_list(),
max_load,
)
# Set up complemented intervals (from 0 to start, and from start + size to
# horizon).
prefix_intervals = model.new_optional_interval_var_series(
name="prefix_intervals",
index=tasks_df.index,
starts=0,
sizes=starts,
ends=starts,
are_present=performed,
)
suffix_intervals = model.new_optional_interval_var_series(
name="suffix_intervals",
index=tasks_df.index,
starts=starts + tasks_df.duration,
sizes=horizon - starts - tasks_df.duration,
ends=horizon,
are_present=performed,
)
# Set up the min profile. We use complemented intervals to maintain the
# complement of the work load, and fixed intervals to enforce the min
# number of active workers per time period.
#
# Note that this works only if the max load cumulative is also added to the
# model.
time_period_min_intervals = model.new_fixed_size_interval_var_series(
name="time_period_min_intervals",
index=min_load_df.index,
starts=min_load_df.start_hour * minutes_per_hour,
sizes=minutes_per_hour * 2,
)
time_period_min_heights = min_load_df.min_load
# We take into account optional intervals. The actual capacity of the min load
# cumulative is the sum of all the active demands.
sum_of_demands = sum(tasks_df.load)
complement_capacity = model.new_int_var(0, sum_of_demands, "complement_capacity")
model.add(complement_capacity == performed.dot(tasks_df.load))
# Cumulative constraint for the min profile.
model.add_cumulative(
prefix_intervals.to_list()
+ suffix_intervals.to_list()
+ time_period_min_intervals.to_list(),
tasks_df.load.to_list()
+ tasks_df.load.to_list()
+ time_period_min_heights.to_list(),
complement_capacity,
)
# Objective: maximize the value of performed intervals.
# 1 is the max priority.
max_priority = max(tasks_df.priority)
model.maximize(sum(performed * (max_priority + 1 - tasks_df.priority)))
# Create the solver and solve the model.
solver = cp_model.CpSolver()
solver.parameters.log_search_progress = True
solver.parameters.num_workers = 16
solver.parameters.max_time_in_seconds = 30.0
status = solver.solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
start_values = solver.values(starts)
performed_values = solver.boolean_values(performed)
tasks: list[tuple[int, int, int]] = []
for task in tasks_df.index:
if performed_values[task]:
print(
f'task {task} duration={tasks_df["duration"][task]} '
f'load={tasks_df["load"][task]} starts at {start_values[task]}'
)
tasks.append(
(start_values[task], tasks_df.duration[task], tasks_df.load[task])
)
else:
print(f"task {task} is not performed")
assert check_solution(
tasks=tasks,
min_load_df=min_load_df,
max_load_df=max_load_df,
period_length=2 * minutes_per_hour,
horizon=horizon,
)
elif status == cp_model.INFEASIBLE:
print("No solution found")
else:
print("Something is wrong, check the status and the log of the solve")
if __name__ == "__main__":
app.run(main)To rank intervals in a no_overlap constraint, you will count the number of performed intervals that precede each interval.
This is slightly complicated if some interval variables are optional. To
implement it, you will create a matrix of precedences boolean variables.
precedences[i][j] is set to true if and only if interval i is performed,
interval j is performed, and if the start of i is before the start of j.
Furthermore, precedences[i][i] is set to be equal to presences[i]. This way,
you can define the rank of an interval i as sum over j(precedences[j][i]) - 1. If the interval is not performed, the rank computed as -1, if the interval
is performed, its presence variable negates the -1, and the formula counts the
number of other intervals that precede it.
#!/usr/bin/env python3
"""Code sample to demonstrates how to rank intervals."""
from ortools.sat.python import cp_model
def rank_tasks(
model: cp_model.CpModel,
starts: list[cp_model.IntVar],
presences: list[cp_model.BoolVarT],
ranks: list[cp_model.IntVar],
) -> None:
"""This method adds constraints and variables to links tasks and ranks.
This method assumes that all starts are disjoint, meaning that all tasks have
a strictly positive duration, and they appear in the same NoOverlap
constraint.
Args:
model: The CpModel to add the constraints to.
starts: The array of starts variables of all tasks.
presences: The array of presence variables or constants of all tasks.
ranks: The array of rank variables of all tasks.
"""
num_tasks = len(starts)
all_tasks = range(num_tasks)
# Creates precedence variables between pairs of intervals.
precedences: dict[tuple[int, int], cp_model.BoolVarT] = {}
for i in all_tasks:
for j in all_tasks:
if i == j:
precedences[(i, j)] = presences[i]
else:
prec = model.new_bool_var(f"{i} before {j}")
precedences[(i, j)] = prec
model.add(starts[i] < starts[j]).only_enforce_if(prec)
# Treats optional intervals.
for i in range(num_tasks - 1):
for j in range(i + 1, num_tasks):
tmp_array: list[cp_model.BoolVarT] = [
precedences[(i, j)],
precedences[(j, i)],
]
if not cp_model.object_is_a_true_literal(presences[i]):
tmp_array.append(~presences[i])
# Makes sure that if i is not performed, all precedences are false.
model.add_implication(~presences[i], ~precedences[(i, j)])
model.add_implication(~presences[i], ~precedences[(j, i)])
if not cp_model.object_is_a_true_literal(presences[j]):
tmp_array.append(~presences[j])
# Makes sure that if j is not performed, all precedences are false.
model.add_implication(~presences[j], ~precedences[(i, j)])
model.add_implication(~presences[j], ~precedences[(j, i)])
# The following bool_or will enforce that for any two intervals:
# i precedes j or j precedes i or at least one interval is not
# performed.
model.add_bool_or(tmp_array)
# Redundant constraint: it propagates early that at most one precedence
# is true.
model.add_implication(precedences[(i, j)], ~precedences[(j, i)])
model.add_implication(precedences[(j, i)], ~precedences[(i, j)])
# Links precedences and ranks.
for i in all_tasks:
model.add(ranks[i] == sum(precedences[(j, i)] for j in all_tasks) - 1)
def ranking_sample_sat() -> None:
"""Ranks tasks in a NoOverlap constraint."""
model = cp_model.CpModel()
horizon = 100
num_tasks = 4
all_tasks = range(num_tasks)
starts = []
ends = []
intervals = []
presences: list[cp_model.BoolVarT] = []
ranks = []
# Creates intervals, half of them are optional.
for t in all_tasks:
start = model.new_int_var(0, horizon, f"start[{t}]")
duration = t + 1
end = model.new_int_var(0, horizon, f"end[{t}]")
if t < num_tasks // 2:
interval = model.new_interval_var(start, duration, end, f"interval[{t}]")
presence = model.new_constant(1)
else:
presence = model.new_bool_var(f"presence[{t}]")
interval = model.new_optional_interval_var(
start, duration, end, presence, f"o_interval[{t}]"
)
starts.append(start)
ends.append(end)
intervals.append(interval)
presences.append(presence)
# Ranks = -1 if and only if the tasks is not performed.
ranks.append(model.new_int_var(-1, num_tasks - 1, f"rank[{t}]"))
# Adds NoOverlap constraint.
model.add_no_overlap(intervals)
# Adds ranking constraint.
rank_tasks(model, starts, presences, ranks)
# Adds a constraint on ranks.
model.add(ranks[0] < ranks[1])
# Creates makespan variable.
makespan = model.new_int_var(0, horizon, "makespan")
for t in all_tasks:
model.add(ends[t] <= makespan).only_enforce_if(presences[t])
# Minimizes makespan - fixed gain per tasks performed.
# As the fixed cost is less that the duration of the last interval,
# the solver will not perform the last interval.
model.minimize(2 * makespan - 7 * sum(presences[t] for t in all_tasks))
# Solves the model model.
solver = cp_model.CpSolver()
status = solver.solve(model)
if status == cp_model.OPTIMAL:
# Prints out the makespan and the start times and ranks of all tasks.
print(f"Optimal cost: {solver.objective_value}")
print(f"Makespan: {solver.value(makespan)}")
for t in all_tasks:
if solver.value(presences[t]):
print(
f"Task {t} starts at {solver.value(starts[t])} "
f"with rank {solver.value(ranks[t])}"
)
else:
print(
f"Task {t} in not performed and ranked at {solver.value(ranks[t])}"
)
else:
print(f"Solver exited with nonoptimal status: {status}")
ranking_sample_sat()#include <stdint.h>
#include <stdlib.h>
#include <vector>
#include "absl/types/span.h"
#include "ortools/base/logging.h"
#include "ortools/sat/cp_model.h"
#include "ortools/sat/cp_model.pb.h"
#include "ortools/sat/cp_model_solver.h"
#include "ortools/util/sorted_interval_list.h"
namespace operations_research {
namespace sat {
void RankingSampleSat() {
CpModelBuilder cp_model;
const int kHorizon = 100;
const int kNumTasks = 4;
auto add_task_ranking = [&cp_model](absl::Span<const IntVar> starts,
absl::Span<const BoolVar> presences,
absl::Span<const IntVar> ranks) {
const int num_tasks = starts.size();
// Creates precedence variables between pairs of intervals.
std::vector<std::vector<BoolVar>> precedences(num_tasks);
for (int i = 0; i < num_tasks; ++i) {
precedences[i].resize(num_tasks);
for (int j = 0; j < num_tasks; ++j) {
if (i == j) {
precedences[i][i] = presences[i];
} else {
BoolVar prec = cp_model.NewBoolVar();
precedences[i][j] = prec;
cp_model.AddLessOrEqual(starts[i], starts[j]).OnlyEnforceIf(prec);
}
}
}
// Treats optional intervals.
for (int i = 0; i < num_tasks - 1; ++i) {
for (int j = i + 1; j < num_tasks; ++j) {
// Makes sure that if i is not performed, all precedences are
// false.
cp_model.AddImplication(~presences[i], ~precedences[i][j]);
cp_model.AddImplication(~presences[i], ~precedences[j][i]);
// Makes sure that if j is not performed, all precedences are
// false.
cp_model.AddImplication(~presences[j], ~precedences[i][j]);
cp_model.AddImplication(~presences[j], ~precedences[j][i]);
// The following bool_or will enforce that for any two intervals:
// i precedes j or j precedes i or at least one interval is not
// performed.
cp_model.AddBoolOr({precedences[i][j], precedences[j][i], ~presences[i],
~presences[j]});
// Redundant constraint: it propagates early that at most one
// precedence is true.
cp_model.AddImplication(precedences[i][j], ~precedences[j][i]);
cp_model.AddImplication(precedences[j][i], ~precedences[i][j]);
}
}
// Links precedences and ranks.
for (int i = 0; i < num_tasks; ++i) {
LinearExpr sum_of_predecessors(-1);
for (int j = 0; j < num_tasks; ++j) {
sum_of_predecessors += precedences[j][i];
}
cp_model.AddEquality(ranks[i], sum_of_predecessors);
}
};
std::vector<IntVar> starts;
std::vector<IntVar> ends;
std::vector<IntervalVar> intervals;
std::vector<BoolVar> presences;
std::vector<IntVar> ranks;
const Domain horizon(0, kHorizon);
const Domain possible_ranks(-1, kNumTasks - 1);
for (int t = 0; t < kNumTasks; ++t) {
const IntVar start = cp_model.NewIntVar(horizon);
const int64_t duration = t + 1;
const IntVar end = cp_model.NewIntVar(horizon);
const BoolVar presence =
t < kNumTasks / 2 ? cp_model.TrueVar() : cp_model.NewBoolVar();
const IntervalVar interval =
cp_model.NewOptionalIntervalVar(start, duration, end, presence);
const IntVar rank = cp_model.NewIntVar(possible_ranks);
starts.push_back(start);
ends.push_back(end);
intervals.push_back(interval);
presences.push_back(presence);
ranks.push_back(rank);
}
// Adds NoOverlap constraint.
cp_model.AddNoOverlap(intervals);
// Ranks tasks.
add_task_ranking(starts, presences, ranks);
// Adds a constraint on ranks.
cp_model.AddLessThan(ranks[0], ranks[1]);
// Creates makespan variables.
const IntVar makespan = cp_model.NewIntVar(horizon);
for (int t = 0; t < kNumTasks; ++t) {
cp_model.AddLessOrEqual(ends[t], makespan).OnlyEnforceIf(presences[t]);
}
// Create objective: minimize 2 * makespan - 7 * sum of presences.
// That is you gain 7 by interval performed, but you pay 2 by day of delays.
LinearExpr objective = 2 * makespan;
for (int t = 0; t < kNumTasks; ++t) {
objective -= 7 * presences[t];
}
cp_model.Minimize(objective);
// Solving part.
const CpSolverResponse response = Solve(cp_model.Build());
LOG(INFO) << CpSolverResponseStats(response);
if (response.status() == CpSolverStatus::OPTIMAL) {
LOG(INFO) << "Optimal cost: " << response.objective_value();
LOG(INFO) << "Makespan: " << SolutionIntegerValue(response, makespan);
for (int t = 0; t < kNumTasks; ++t) {
if (SolutionBooleanValue(response, presences[t])) {
LOG(INFO) << "task " << t << " starts at "
<< SolutionIntegerValue(response, starts[t]) << " with rank "
<< SolutionIntegerValue(response, ranks[t]);
} else {
LOG(INFO) << "task " << t << " is not performed and ranked at "
<< SolutionIntegerValue(response, ranks[t]);
}
}
}
}
} // namespace sat
} // namespace operations_research
int main() {
operations_research::sat::RankingSampleSat();
return EXIT_SUCCESS;
}package com.google.ortools.sat.samples;
import com.google.ortools.Loader;
import com.google.ortools.sat.BoolVar;
import com.google.ortools.sat.CpModel;
import com.google.ortools.sat.CpSolver;
import com.google.ortools.sat.CpSolverStatus;
import com.google.ortools.sat.IntVar;
import com.google.ortools.sat.IntervalVar;
import com.google.ortools.sat.LinearExpr;
import com.google.ortools.sat.LinearExprBuilder;
import com.google.ortools.sat.Literal;
import java.util.ArrayList;
import java.util.List;
/** Code sample to demonstrates how to rank intervals. */
public class RankingSampleSat {
/**
* This code takes a list of interval variables in a noOverlap constraint, and a parallel list of
* integer variables and enforces the following constraint
*
* <ul>
* <li>rank[i] == -1 iff interval[i] is not active.
* <li>rank[i] == number of active intervals that precede interval[i].
* </ul>
*/
static void rankTasks(CpModel model, IntVar[] starts, Literal[] presences, IntVar[] ranks) {
int numTasks = starts.length;
// Creates precedence variables between pairs of intervals.
Literal[][] precedences = new Literal[numTasks][numTasks];
for (int i = 0; i < numTasks; ++i) {
for (int j = 0; j < numTasks; ++j) {
if (i == j) {
precedences[i][i] = presences[i];
} else {
BoolVar prec = model.newBoolVar(String.format("%d before %d", i, j));
precedences[i][j] = prec;
// Ensure that task i precedes task j if prec is true.
model.addLessThan(starts[i], starts[j]).onlyEnforceIf(prec);
}
}
}
// Create optional intervals.
for (int i = 0; i < numTasks - 1; ++i) {
for (int j = i + 1; j < numTasks; ++j) {
List<Literal> list = new ArrayList<>();
list.add(precedences[i][j]);
list.add(precedences[j][i]);
list.add(presences[i].not());
// Makes sure that if i is not performed, all precedences are false.
model.addImplication(presences[i].not(), precedences[i][j].not());
model.addImplication(presences[i].not(), precedences[j][i].not());
list.add(presences[j].not());
// Makes sure that if j is not performed, all precedences are false.
model.addImplication(presences[j].not(), precedences[i][j].not());
model.addImplication(presences[j].not(), precedences[j][i].not());
// The following boolOr will enforce that for any two intervals:
// i precedes j or j precedes i or at least one interval is not
// performed.
model.addBoolOr(list);
// For efficiency, we add a redundant constraint declaring that only one of i precedes j and
// j precedes i are true. This will speed up the solve because the reason of this
// propagation is shorter that using interval bounds is true.
model.addImplication(precedences[i][j], precedences[j][i].not());
model.addImplication(precedences[j][i], precedences[i][j].not());
}
}
// Links precedences and ranks.
for (int i = 0; i < numTasks; ++i) {
// ranks == sum(precedences) - 1;
LinearExprBuilder expr = LinearExpr.newBuilder();
for (int j = 0; j < numTasks; ++j) {
expr.add(precedences[j][i]);
}
expr.add(-1);
model.addEquality(ranks[i], expr);
}
}
public static void main(String[] args) throws Exception {
Loader.loadNativeLibraries();
CpModel model = new CpModel();
int horizon = 100;
int numTasks = 4;
IntVar[] starts = new IntVar[numTasks];
IntVar[] ends = new IntVar[numTasks];
IntervalVar[] intervals = new IntervalVar[numTasks];
Literal[] presences = new Literal[numTasks];
IntVar[] ranks = new IntVar[numTasks];
Literal trueLiteral = model.trueLiteral();
// Creates intervals, half of them are optional.
for (int t = 0; t < numTasks; ++t) {
starts[t] = model.newIntVar(0, horizon, "start_" + t);
int duration = t + 1;
ends[t] = model.newIntVar(0, horizon, "end_" + t);
if (t < numTasks / 2) {
intervals[t] = model.newIntervalVar(
starts[t], LinearExpr.constant(duration), ends[t], "interval_" + t);
presences[t] = trueLiteral;
} else {
presences[t] = model.newBoolVar("presence_" + t);
intervals[t] = model.newOptionalIntervalVar(
starts[t], LinearExpr.constant(duration), ends[t], presences[t], "o_interval_" + t);
}
// The rank will be -1 iff the task is not performed.
ranks[t] = model.newIntVar(-1, numTasks - 1, "rank_" + t);
}
// Adds NoOverlap constraint.
model.addNoOverlap(intervals);
// Adds ranking constraint.
rankTasks(model, starts, presences, ranks);
// Adds a constraint on ranks (ranks[0] < ranks[1]).
model.addLessThan(ranks[0], ranks[1]);
// Creates makespan variable.
IntVar makespan = model.newIntVar(0, horizon, "makespan");
for (int t = 0; t < numTasks; ++t) {
model.addLessOrEqual(ends[t], makespan).onlyEnforceIf(presences[t]);
}
// The objective function is a mix of a fixed gain per task performed, and a fixed cost for each
// additional day of activity.
// The solver will balance both cost and gain and minimize makespan * per-day-penalty - number
// of tasks performed * per-task-gain.
//
// On this problem, as the fixed cost is less that the duration of the last interval, the solver
// will not perform the last interval.
LinearExprBuilder obj = LinearExpr.newBuilder();
for (int t = 0; t < numTasks; ++t) {
obj.addTerm(presences[t], -7);
}
obj.addTerm(makespan, 2);
model.minimize(obj);
// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.solve(model);
if (status == CpSolverStatus.OPTIMAL) {
System.out.println("Optimal cost: " + solver.objectiveValue());
System.out.println("Makespan: " + solver.value(makespan));
for (int t = 0; t < numTasks; ++t) {
if (solver.booleanValue(presences[t])) {
System.out.printf("Task %d starts at %d with rank %d%n", t, solver.value(starts[t]),
solver.value(ranks[t]));
} else {
System.out.printf(
"Task %d in not performed and ranked at %d%n", t, solver.value(ranks[t]));
}
}
} else {
System.out.println("Solver exited with nonoptimal status: " + status);
}
}
}using System;
using System.Collections.Generic;
using Google.OrTools.Sat;
public class RankingSampleSat
{
static void RankTasks(CpModel model, IntVar[] starts, ILiteral[] presences, IntVar[] ranks)
{
int num_tasks = starts.Length;
// Creates precedence variables between pairs of intervals.
ILiteral[,] precedences = new ILiteral[num_tasks, num_tasks];
for (int i = 0; i < num_tasks; ++i)
{
for (int j = 0; j < num_tasks; ++j)
{
if (i == j)
{
precedences[i, i] = presences[i];
}
else
{
BoolVar prec = model.NewBoolVar(String.Format("{0} before {1}", i, j));
precedences[i, j] = prec;
model.Add(starts[i] < starts[j]).OnlyEnforceIf(prec);
}
}
}
// Treats optional intervals.
for (int i = 0; i < num_tasks - 1; ++i)
{
for (int j = i + 1; j < num_tasks; ++j)
{
List<ILiteral> tmp_array = new List<ILiteral>();
tmp_array.Add(precedences[i, j]);
tmp_array.Add(precedences[j, i]);
tmp_array.Add(presences[i].Not());
// Makes sure that if i is not performed, all precedences are false.
model.AddImplication(presences[i].Not(), precedences[i, j].Not());
model.AddImplication(presences[i].Not(), precedences[j, i].Not());
tmp_array.Add(presences[j].Not());
// Makes sure that if j is not performed, all precedences are false.
model.AddImplication(presences[j].Not(), precedences[i, j].Not());
model.AddImplication(presences[j].Not(), precedences[j, i].Not());
// The following bool_or will enforce that for any two intervals:
// i precedes j or j precedes i or at least one interval is not
// performed.
model.AddBoolOr(tmp_array);
// Redundant constraint: it propagates early that at most one precedence
// is true.
model.AddImplication(precedences[i, j], precedences[j, i].Not());
model.AddImplication(precedences[j, i], precedences[i, j].Not());
}
}
// Links precedences and ranks.
for (int i = 0; i < num_tasks; ++i)
{
List<IntVar> tasks = new List<IntVar>();
for (int j = 0; j < num_tasks; ++j)
{
tasks.Add((IntVar)precedences[j, i]);
}
model.Add(ranks[i] == LinearExpr.Sum(tasks) - 1);
}
}
static void Main()
{
CpModel model = new CpModel();
// Three weeks.
int horizon = 100;
int num_tasks = 4;
IntVar[] starts = new IntVar[num_tasks];
IntVar[] ends = new IntVar[num_tasks];
IntervalVar[] intervals = new IntervalVar[num_tasks];
ILiteral[] presences = new ILiteral[num_tasks];
IntVar[] ranks = new IntVar[num_tasks];
ILiteral true_var = model.TrueLiteral();
// Creates intervals, half of them are optional.
for (int t = 0; t < num_tasks; ++t)
{
starts[t] = model.NewIntVar(0, horizon, String.Format("start_{0}", t));
int duration = t + 1;
ends[t] = model.NewIntVar(0, horizon, String.Format("end_{0}", t));
if (t < num_tasks / 2)
{
intervals[t] = model.NewIntervalVar(starts[t], duration, ends[t], String.Format("interval_{0}", t));
presences[t] = true_var;
}
else
{
presences[t] = model.NewBoolVar(String.Format("presence_{0}", t));
intervals[t] = model.NewOptionalIntervalVar(starts[t], duration, ends[t], presences[t],
String.Format("o_interval_{0}", t));
}
// Ranks = -1 if and only if the tasks is not performed.
ranks[t] = model.NewIntVar(-1, num_tasks - 1, String.Format("rank_{0}", t));
}
// Adds NoOverlap constraint.
model.AddNoOverlap(intervals);
// Adds ranking constraint.
RankTasks(model, starts, presences, ranks);
// Adds a constraint on ranks.
model.Add(ranks[0] < ranks[1]);
// Creates makespan variable.
IntVar makespan = model.NewIntVar(0, horizon, "makespan");
for (int t = 0; t < num_tasks; ++t)
{
model.Add(ends[t] <= makespan).OnlyEnforceIf(presences[t]);
}
// Minimizes makespan - fixed gain per tasks performed.
// As the fixed cost is less that the duration of the last interval,
// the solver will not perform the last interval.
IntVar[] presences_as_int_vars = new IntVar[num_tasks];
for (int t = 0; t < num_tasks; ++t)
{
presences_as_int_vars[t] = (IntVar)presences[t];
}
model.Minimize(2 * makespan - 7 * LinearExpr.Sum(presences_as_int_vars));
// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
CpSolverStatus status = solver.Solve(model);
if (status == CpSolverStatus.Optimal)
{
Console.WriteLine(String.Format("Optimal cost: {0}", solver.ObjectiveValue));
Console.WriteLine(String.Format("Makespan: {0}", solver.Value(makespan)));
for (int t = 0; t < num_tasks; ++t)
{
if (solver.BooleanValue(presences[t]))
{
Console.WriteLine(String.Format("Task {0} starts at {1} with rank {2}", t, solver.Value(starts[t]),
solver.Value(ranks[t])));
}
else
{
Console.WriteLine(
String.Format("Task {0} in not performed and ranked at {1}", t, solver.Value(ranks[t])));
}
}
}
else
{
Console.WriteLine(String.Format("Solver exited with nonoptimal status: {0}", status));
}
}
}// The ranking_sample_sat command is an example of ranking intervals in a NoOverlap constraint.
package main
import (
"fmt"
"github.com/golang/glog"
cmpb "ortools/sat/cp_model_go_proto"
"ortools/sat/go/cpmodel"
)
const (
horizonLength = 100
numTasks = 4
)
// rankTasks adds constraints and variables to link tasks and ranks. This method
// assumes that all starts are disjoint, meaning that all tasks have a strictly
// positive duration, and they appear in the same NoOverlap constraint.
func rankTasks(starts []cpmodel.IntVar, presences []cpmodel.BoolVar, ranks []cpmodel.IntVar, model *cpmodel.Builder) {
// Creates precedence variables between pairs of intervals.
precedences := make([][]cpmodel.BoolVar, numTasks)
for i := 0; i < numTasks; i++ {
precedences[i] = make([]cpmodel.BoolVar, numTasks)
for j := 0; j < numTasks; j++ {
if i == j {
precedences[i][i] = presences[i]
} else {
prec := model.NewBoolVar()
precedences[i][j] = prec
model.AddLessOrEqual(starts[i], starts[j]).OnlyEnforceIf(prec)
}
}
}
// Treats optional intervals.
for i := 0; i+1 < numTasks; i++ {
for j := i + 1; j < numTasks; j++ {
// Make sure that if task i is not performed, all precedences are false.
model.AddImplication(presences[i].Not(), precedences[i][j].Not())
model.AddImplication(presences[i].Not(), precedences[j][i].Not())
// Make sure that if task j is not performed, all precedences are false.
model.AddImplication(presences[j].Not(), precedences[i][j].Not())
model.AddImplication(presences[j].Not(), precedences[j][i].Not())
// The following BoolOr will enforce that for any two intervals:
// i precedes j or j precedes i or at least one interval is not performed.
model.AddBoolOr(precedences[i][j], precedences[j][i], presences[i].Not(), presences[j].Not())
// Redundant constraint: it propagates early that at most one precedence
// is true.
model.AddImplication(precedences[i][j], precedences[j][i].Not())
model.AddImplication(precedences[j][i], precedences[i][j].Not())
}
}
// Links precedences and ranks.
for i := 0; i < numTasks; i++ {
sumOfPredecessors := cpmodel.NewConstant(-1)
for j := 0; j < numTasks; j++ {
sumOfPredecessors.Add(precedences[j][i])
}
model.AddEquality(ranks[i], sumOfPredecessors)
}
}
func rankingSampleSat() error {
model := cpmodel.NewCpModelBuilder()
starts := make([]cpmodel.IntVar, numTasks)
ends := make([]cpmodel.IntVar, numTasks)
intervals := make([]cpmodel.IntervalVar, numTasks)
presences := make([]cpmodel.BoolVar, numTasks)
ranks := make([]cpmodel.IntVar, numTasks)
horizon := cpmodel.NewDomain(0, horizonLength)
possibleRanks := cpmodel.NewDomain(-1, numTasks-1)
for t := 0; t < numTasks; t++ {
start := model.NewIntVarFromDomain(horizon)
duration := cpmodel.NewConstant(int64_t(t + 1))
end := model.NewIntVarFromDomain(horizon)
var presence cpmodel.BoolVar
if t < numTasks/2 {
presence = model.TrueVar()
} else {
presence = model.NewBoolVar()
}
interval := model.NewOptionalIntervalVar(start, duration, end, presence)
rank := model.NewIntVarFromDomain(possibleRanks)
starts[t] = start
ends[t] = end
intervals[t] = interval
presences[t] = presence
ranks[t] = rank
}
// Adds NoOverlap constraint.
model.AddNoOverlap(intervals...)
// Ranks tasks.
rankTasks(starts, presences, ranks, model)
// Adds a constraint on ranks.
model.AddLessThan(ranks[0], ranks[1])
// Creates makespan variables.
makespan := model.NewIntVarFromDomain(horizon)
for t := 0; t < numTasks; t++ {
model.AddLessOrEqual(ends[t], makespan).OnlyEnforceIf(presences[t])
}
// Create objective: minimize 2 * makespan - 7 * sum of presences.
// This is you gain 7 by interval performed, but you pay 2 by day of delays.
objective := cpmodel.NewLinearExpr().AddTerm(makespan, 2)
for t := 0; t < numTasks; t++ {
objective.AddTerm(presences[t], -7)
}
model.Minimize(objective)
// Solving part.
m, err := model.Model()
if err != nil {
return fmt.Errorf("failed to instantiate the CP model: %w", err)
}
response, err := cpmodel.SolveCpModel(m)
if err != nil {
return fmt.Errorf("failed to solve the model: %w", err)
}
if response.GetStatus() == cmpb.CpSolverStatus_OPTIMAL {
fmt.Println(response.GetStatus())
fmt.Println("Optimal cost: ", response.GetObjectiveValue())
fmt.Println("Makespan: ", cpmodel.SolutionIntegerValue(response, makespan))
for t := 0; t < numTasks; t++ {
rank := cpmodel.SolutionIntegerValue(response, ranks[t])
if cpmodel.SolutionBooleanValue(response, presences[t]) {
start := cpmodel.SolutionIntegerValue(response, starts[t])
fmt.Printf("Task %v starts at %v with rank %v\n", t, start, rank)
} else {
fmt.Printf("Task %v is not performed and ranked at %v\n", t, rank)
}
}
}
return nil
}
func main() {
if err := rankingSampleSat(); err != nil {
glog.Exitf("rankingSampleSat returned with error: %v", err)
}
}To rank intervals in a no_overlap constraint, you will use a circuit constraint to perform the transitive reduction from precedences to successors.
This is slightly complicated if some interval variables are optional, and you need to take into account the case where no task is performed.
#!/usr/bin/env python3
"""Code sample to demonstrates how to rank intervals using a circuit."""
from typing import List, Sequence
from ortools.sat.python import cp_model
def rank_tasks_with_circuit(
model: cp_model.CpModel,
starts: Sequence[cp_model.IntVar],
durations: Sequence[int],
presences: Sequence[cp_model.IntVar],
ranks: Sequence[cp_model.IntVar],
) -> None:
"""This method uses a circuit constraint to rank tasks.
This method assumes that all starts are disjoint, meaning that all tasks have
a strictly positive duration, and they appear in the same NoOverlap
constraint.
To implement this ranking, we will create a dense graph with num_tasks + 1
nodes.
The extra node (with id 0) will be used to decide which task is first with
its only outgoing arc, and which task is last with its only incoming arc.
Each task i will be associated with id i + 1, and an arc between i + 1 and j +
1 indicates that j is the immediate successor of i.
The circuit constraint ensures there is at most 1 hamiltonian cycle of
length > 1. If no such path exists, then no tasks are active.
We also need to enforce that any hamiltonian cycle of size > 1 must contain
the node 0. And thus, there is a self loop on node 0 iff the circuit is empty.
Args:
model: The CpModel to add the constraints to.
starts: The array of starts variables of all tasks.
durations: the durations of all tasks.
presences: The array of presence variables of all tasks.
ranks: The array of rank variables of all tasks.
"""
num_tasks = len(starts)
all_tasks = range(num_tasks)
arcs: List[cp_model.ArcT] = []
for i in all_tasks:
# if node i is first.
start_lit = model.new_bool_var(f"start_{i}")
arcs.append((0, i + 1, start_lit))
model.add(ranks[i] == 0).only_enforce_if(start_lit)
# As there are no other constraints on the problem, we can add this
# redundant constraint.
model.add(starts[i] == 0).only_enforce_if(start_lit)
# if node i is last.
end_lit = model.new_bool_var(f"end_{i}")
arcs.append((i + 1, 0, end_lit))
for j in all_tasks:
if i == j:
arcs.append((i + 1, i + 1, ~presences[i]))
model.add(ranks[i] == -1).only_enforce_if(~presences[i])
else:
literal = model.new_bool_var(f"arc_{i}_to_{j}")
arcs.append((i + 1, j + 1, literal))
model.add(ranks[j] == ranks[i] + 1).only_enforce_if(literal)
# To perform the transitive reduction from precedences to successors,
# we need to tie the starts of the tasks with 'literal'.
# In a pure problem, the following inequality could be an equality.
# It is not true in general.
#
# Note that we could use this literal to penalize the transition, add an
# extra delay to the precedence.
model.add(starts[j] >= starts[i] + durations[i]).only_enforce_if(
literal
)
# Manage the empty circuit
empty = model.new_bool_var("empty")
arcs.append((0, 0, empty))
for i in all_tasks:
model.add_implication(empty, ~presences[i])
# Add the circuit constraint.
model.add_circuit(arcs)
def ranking_sample_sat() -> None:
"""Ranks tasks in a NoOverlap constraint."""
model = cp_model.CpModel()
horizon = 100
num_tasks = 4
all_tasks = range(num_tasks)
starts = []
durations = []
intervals = []
presences = []
ranks = []
# Creates intervals, half of them are optional.
for t in all_tasks:
start = model.new_int_var(0, horizon, f"start[{t}]")
duration = t + 1
presence = model.new_bool_var(f"presence[{t}]")
interval = model.new_optional_fixed_size_interval_var(
start, duration, presence, f"opt_interval[{t}]"
)
if t < num_tasks // 2:
model.add(presence == 1)
starts.append(start)
durations.append(duration)
intervals.append(interval)
presences.append(presence)
# Ranks = -1 if and only if the tasks is not performed.
ranks.append(model.new_int_var(-1, num_tasks - 1, f"rank[{t}]"))
# Adds NoOverlap constraint.
model.add_no_overlap(intervals)
# Adds ranking constraint.
rank_tasks_with_circuit(model, starts, durations, presences, ranks)
# Adds a constraint on ranks.
model.add(ranks[0] < ranks[1])
# Creates makespan variable.
makespan = model.new_int_var(0, horizon, "makespan")
for t in all_tasks:
model.add(starts[t] + durations[t] <= makespan).only_enforce_if(presences[t])
# Minimizes makespan - fixed gain per tasks performed.
# As the fixed cost is less that the duration of the last interval,
# the solver will not perform the last interval.
model.minimize(2 * makespan - 7 * sum(presences[t] for t in all_tasks))
# Solves the model model.
solver = cp_model.CpSolver()
status = solver.solve(model)
if status == cp_model.OPTIMAL:
# Prints out the makespan and the start times and ranks of all tasks.
print(f"Optimal cost: {solver.objective_value}")
print(f"Makespan: {solver.value(makespan)}")
for t in all_tasks:
if solver.value(presences[t]):
print(
f"Task {t} starts at {solver.value(starts[t])} "
f"with rank {solver.value(ranks[t])}"
)
else:
print(
f"Task {t} in not performed and ranked at {solver.value(ranks[t])}"
)
else:
print(f"Solver exited with nonoptimal status: {status}")
ranking_sample_sat()Sometimes, a task can be interrupted by a break (overnight, lunch break). In that context, although the processing time of the task is the same, the duration can vary.
To implement this feature, you will have the duration of the task be a function of the start of the task. This is implemented using channeling constraints.
The following code displays:
start=8 duration=3 across=0
start=9 duration=3 across=0
start=10 duration=3 across=0
start=11 duration=4 across=1
start=12 duration=4 across=1
start=14 duration=3 across=0
start=15 duration=3 across=0
#!/usr/bin/env python3
"""Code sample to demonstrate how an interval can span across a break."""
from ortools.sat.python import cp_model
class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self, variables: list[cp_model.IntVar]):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
def on_solution_callback(self) -> None:
for v in self.__variables:
print(f"{v}={self.value(v)}", end=" ")
print()
def scheduling_with_calendar_sample_sat():
"""Interval spanning across a lunch break."""
model = cp_model.CpModel()
# The data is the following:
# Work starts at 8h, ends at 18h, with a lunch break between 13h and 14h.
# We need to schedule a task that needs 3 hours of processing time.
# Total duration can be 3 or 4 (if it spans the lunch break).
#
# Because the duration is at least 3 hours, work cannot start after 15h.
# Because of the break, work cannot start at 13h.
start = model.new_int_var_from_domain(
cp_model.Domain.from_intervals([(8, 12), (14, 15)]), "start"
)
duration = model.new_int_var(3, 4, "duration")
end = model.new_int_var(8, 18, "end")
unused_interval = model.new_interval_var(start, duration, end, "interval")
# We have 2 states (spanning across lunch or not)
across = model.new_bool_var("across")
non_spanning_hours = cp_model.Domain.from_values([8, 9, 10, 14, 15])
model.add_linear_expression_in_domain(start, non_spanning_hours).only_enforce_if(
~across
)
model.add_linear_constraint(start, 11, 12).only_enforce_if(across)
model.add(duration == 3).only_enforce_if(~across)
model.add(duration == 4).only_enforce_if(across)
# Search for x values in increasing order.
model.add_decision_strategy(
[start], cp_model.CHOOSE_FIRST, cp_model.SELECT_MIN_VALUE
)
# Create a solver and solve with a fixed search.
solver = cp_model.CpSolver()
# Force the solver to follow the decision strategy exactly.
solver.parameters.search_branching = cp_model.FIXED_SEARCH
# Enumerate all solutions.
solver.parameters.enumerate_all_solutions = True
# Search and print all solutions.
solution_printer = VarArraySolutionPrinter([start, duration, across])
solver.solve(model, solution_printer)
scheduling_with_calendar_sample_sat()You want a Boolean variable to be true if and only if two intervals overlap. To enforce this, you will create 3 Boolean variables, link two of them to the relative positions of the two intervals, and define the third one using the other two Boolean variables.
There are two ways of linking the three Boolean variables. The first version
uses one clause and two implications. Propagation will be faster using this
version. The second version uses a sum(..) == 1 equation. It is more compact,
but assumes the length of the two intervals is > 0.
Note that you need to create the intervals to enforce start + size == end, but
you do not actually use them in this code sample.
The following code displays
start_a=0 start_b=0 a_overlaps_b=1
start_a=0 start_b=1 a_overlaps_b=1
start_a=0 start_b=2 a_overlaps_b=1
start_a=0 start_b=3 a_overlaps_b=0
start_a=0 start_b=4 a_overlaps_b=0
start_a=0 start_b=5 a_overlaps_b=0
start_a=1 start_b=0 a_overlaps_b=1
start_a=1 start_b=1 a_overlaps_b=1
start_a=1 start_b=2 a_overlaps_b=1
start_a=1 start_b=3 a_overlaps_b=1
start_a=1 start_b=4 a_overlaps_b=0
start_a=1 start_b=5 a_overlaps_b=0
...
#!/usr/bin/env python3
"""Code sample to demonstrates how to detect if two intervals overlap."""
from ortools.sat.python import cp_model
class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
"""Print intermediate solutions."""
def __init__(self, variables: list[cp_model.IntVar]):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
def on_solution_callback(self) -> None:
for v in self.__variables:
print(f"{v}={self.value(v)}", end=" ")
print()
def overlapping_interval_sample_sat():
"""Create the overlapping Boolean variables and enumerate all states."""
model = cp_model.CpModel()
horizon = 7
# First interval.
start_var_a = model.new_int_var(0, horizon, "start_a")
duration_a = 3
end_var_a = model.new_int_var(0, horizon, "end_a")
unused_interval_var_a = model.new_interval_var(
start_var_a, duration_a, end_var_a, "interval_a"
)
# Second interval.
start_var_b = model.new_int_var(0, horizon, "start_b")
duration_b = 2
end_var_b = model.new_int_var(0, horizon, "end_b")
unused_interval_var_b = model.new_interval_var(
start_var_b, duration_b, end_var_b, "interval_b"
)
# a_after_b Boolean variable.
a_after_b = model.new_bool_var("a_after_b")
model.add(start_var_a >= end_var_b).only_enforce_if(a_after_b)
model.add(start_var_a < end_var_b).only_enforce_if(~a_after_b)
# b_after_a Boolean variable.
b_after_a = model.new_bool_var("b_after_a")
model.add(start_var_b >= end_var_a).only_enforce_if(b_after_a)
model.add(start_var_b < end_var_a).only_enforce_if(~b_after_a)
# Result Boolean variable.
a_overlaps_b = model.new_bool_var("a_overlaps_b")
# Option a: using only clauses
model.add_bool_or(a_after_b, b_after_a, a_overlaps_b)
model.add_implication(a_after_b, ~a_overlaps_b)
model.add_implication(b_after_a, ~a_overlaps_b)
# Option b: using an exactly one constraint.
# model.add_exactly_one(a_after_b, b_after_a, a_overlaps_b)
# Search for start values in increasing order for the two intervals.
model.add_decision_strategy(
[start_var_a, start_var_b],
cp_model.CHOOSE_FIRST,
cp_model.SELECT_MIN_VALUE,
)
# Create a solver and solve with a fixed search.
solver = cp_model.CpSolver()
# Force the solver to follow the decision strategy exactly.
solver.parameters.search_branching = cp_model.FIXED_SEARCH
# Enumerate all solutions.
solver.parameters.enumerate_all_solutions = True
# Search and print out all solutions.
solution_printer = VarArraySolutionPrinter([start_var_a, start_var_b, a_overlaps_b])
solver.solve(model, solution_printer)
overlapping_interval_sample_sat()In some scheduling problems, switching between certain type of tasks on a machine implies some penalty, and/or some delay. Implementing these functionalities implies knowing which are the direct successors of each task.
The circuit constraint is used to perform the transitive reduction from precedences to successors. Once this is done, it is straightforward to use the successor literals to implement the penalties or the delays.
#!/usr/bin/env python3
"""Implements transition times and costs in a no_overlap constraint."""
from typing import Dict, List, Sequence, Tuple, Union
from ortools.sat.python import cp_model
def transitive_reduction_with_circuit_delays_and_penalties(
model: cp_model.CpModel,
starts: Sequence[cp_model.IntVar],
durations: Sequence[int],
presences: Sequence[Union[cp_model.IntVar, bool]],
penalties: Dict[Tuple[int, int], int],
delays: Dict[Tuple[int, int], int],
) -> Sequence[Tuple[cp_model.IntVar, int]]:
"""This method uses a circuit constraint to rank tasks.
This method assumes that all starts are disjoint, meaning that all tasks have
a strictly positive duration, and they appear in the same NoOverlap
constraint.
The extra node (with id 0) will be used to decide which task is first with
its only outgoing arc, and which task is last with its only incoming arc.
Each task i will be associated with id i + 1, and an arc between i + 1 and j +
1 indicates that j is the immediate successor of i.
The circuit constraint ensures there is at most 1 hamiltonian cycle of
length > 1. If no such path exists, then no tasks are active.
We also need to enforce that any hamiltonian cycle of size > 1 must contain
the node 0. And thus, there is a self loop on node 0 iff the circuit is empty.
Args:
model: The CpModel to add the constraints to.
starts: The array of starts variables of all tasks.
durations: the durations of all tasks.
presences: The array of presence variables of all tasks.
penalties: the array of tuple (`tail_index`, `head_index`, `penalty`) that
specifies that if task `tail_index` is the successor of the task
`head_index`, then `penalty` must be added to the cost.
delays: the array of tuple (`tail_index`, `head_index`, `delay`) that
specifies that if task `tail_index` is the successor of the task
`head_index`, then an extra `delay` must be added between the end of the
first task and the start of the second task.
Returns:
The list of pairs (Boolean variables, penalty) to be added to the objective.
"""
num_tasks = len(starts)
all_tasks = range(num_tasks)
arcs: List[cp_model.ArcT] = []
penalty_terms = []
for i in all_tasks:
# if node i is first.
start_lit = model.new_bool_var(f"start_{i}")
arcs.append((0, i + 1, start_lit))
# As there are no other constraints on the problem, we can add this
# redundant constraint.
model.add(starts[i] == 0).only_enforce_if(start_lit)
# if node i is last.
end_lit = model.new_bool_var(f"end_{i}")
arcs.append((i + 1, 0, end_lit))
for j in all_tasks:
if i == j:
arcs.append((i + 1, i + 1, ~presences[i]))
else:
literal = model.new_bool_var(f"arc_{i}_to_{j}")
arcs.append((i + 1, j + 1, literal))
# To perform the transitive reduction from precedences to successors,
# we need to tie the starts of the tasks with 'literal'.
# In a pure problem, the following inequality could be an equality.
# It is not true in general.
#
# Note that we could use this literal to penalize the transition, add an
# extra delay to the precedence.
min_delay = 0
key = (i, j)
if key in delays:
min_delay = delays[key]
model.add(
starts[j] >= starts[i] + durations[i] + min_delay
).only_enforce_if(literal)
# Create the penalties.
if key in penalties:
penalty_terms.append((literal, penalties[key]))
# Manage the empty circuit
empty = model.new_bool_var("empty")
arcs.append((0, 0, empty))
for i in all_tasks:
model.add_implication(empty, ~presences[i])
# Add the circuit constraint.
model.add_circuit(arcs)
return penalty_terms
def transitions_in_no_overlap_sample_sat():
"""Implement transitions in a NoOverlap constraint."""
model = cp_model.CpModel()
horizon = 40
num_tasks = 4
# Breaking the natural sequence induces a fixed penalty.
penalties = {
(1, 0): 10,
(2, 0): 10,
(3, 0): 10,
(2, 1): 10,
(3, 1): 10,
(3, 2): 10,
}
# Switching from an odd to even or even to odd task indices induces a delay.
delays = {
(1, 0): 10,
(0, 1): 10,
(3, 0): 10,
(0, 3): 10,
(1, 2): 10,
(2, 1): 10,
(3, 2): 10,
(2, 3): 10,
}
all_tasks = range(num_tasks)
starts = []
durations = []
intervals = []
presences = []
# Creates intervals, all present. But the cost is robust w.r.t. optional
# intervals.
for t in all_tasks:
start = model.new_int_var(0, horizon, f"start[{t}]")
duration = 5
presence = True
interval = model.new_optional_fixed_size_interval_var(
start, duration, presence, f"opt_interval[{t}]"
)
starts.append(start)
durations.append(duration)
intervals.append(interval)
presences.append(presence)
# Adds NoOverlap constraint.
model.add_no_overlap(intervals)
# Adds ranking constraint.
penalty_terms = transitive_reduction_with_circuit_delays_and_penalties(
model, starts, durations, presences, penalties, delays
)
# Minimize the sum of penalties,
model.minimize(sum(var * penalty for var, penalty in penalty_terms))
# In practise, only one penalty can happen. Thus the two even tasks are
# together, same for the two odd tasks.
# Because of the penalties, the optimal sequence is 0 -> 2 -> 1 -> 3
# which induces one penalty and one delay.
# Solves the model model.
solver = cp_model.CpSolver()
status = solver.solve(model)
if status == cp_model.OPTIMAL:
# Prints out the makespan and the start times and ranks of all tasks.
print(f"Optimal cost: {solver.objective_value}")
for t in all_tasks:
if solver.value(presences[t]):
print(f"Task {t} starts at {solver.value(starts[t])} ")
else:
print(f"Task {t} in not performed")
else:
print(f"Solver exited with nonoptimal status: {status}")
transitions_in_no_overlap_sample_sat()