DotNet Reference

DotNet Reference

RankingSampleSat.cs
Go to the documentation of this file.
1 // Copyright 2010-2018 Google LLC
2 // Licensed under the Apache License, Version 2.0 (the "License");
3 // you may not use this file except in compliance with the License.
4 // You may obtain a copy of the License at
5 //
6 // http://www.apache.org/licenses/LICENSE-2.0
7 //
8 // Unless required by applicable law or agreed to in writing, software
9 // distributed under the License is distributed on an "AS IS" BASIS,
10 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11 // See the License for the specific language governing permissions and
12 // limitations under the License.
13 
14 using System;
15 using System.Collections.Generic;
16 using Google.OrTools.Sat;
17 
18 public class RankingSampleSat
19 {
20  static void RankTasks(CpModel model,
21  IntVar[] starts,
22  ILiteral[] presences,
23  IntVar[] ranks) {
24  int num_tasks = starts.Length;
25 
26  // Creates precedence variables between pairs of intervals.
27  ILiteral[,] precedences = new ILiteral[num_tasks, num_tasks];
28  for (int i = 0; i < num_tasks; ++i) {
29  for (int j = 0; j < num_tasks; ++j) {
30  if (i == j) {
31  precedences[i, i] = presences[i];
32  } else {
33  IntVar prec = model.NewBoolVar(String.Format("{0} before {1}", i, j));
34  precedences[i, j] = prec;
35  model.Add(starts[i] < starts[j]).OnlyEnforceIf(prec);
36  }
37  }
38  }
39 
40  // Treats optional intervals.
41  for (int i = 0; i < num_tasks - 1; ++i) {
42  for (int j = i + 1; j < num_tasks; ++j) {
43  List<ILiteral> tmp_array = new List<ILiteral>();
44  tmp_array.Add(precedences[i, j]);
45  tmp_array.Add(precedences[j, i]);
46  tmp_array.Add(presences[i].Not());
47  // Makes sure that if i is not performed, all precedences are false.
48  model.AddImplication(presences[i].Not(), precedences[i, j].Not());
49  model.AddImplication(presences[i].Not(), precedences[j, i].Not());
50  tmp_array.Add(presences[j].Not());
51  // Makes sure that if j is not performed, all precedences are false.
52  model.AddImplication(presences[j].Not(), precedences[i, j].Not());
53  model.AddImplication(presences[j].Not(), precedences[j, i].Not());
54  // The following bool_or will enforce that for any two intervals:
55  // i precedes j or j precedes i or at least one interval is not
56  // performed.
57  model.AddBoolOr(tmp_array);
58  // Redundant constraint: it propagates early that at most one precedence
59  // is true.
60  model.AddImplication(precedences[i, j], precedences[j, i].Not());
61  model.AddImplication(precedences[j, i], precedences[i, j].Not());
62  }
63  }
64 
65  // Links precedences and ranks.
66  for (int i = 0; i < num_tasks; ++i) {
67  IntVar[] tmp_array = new IntVar[num_tasks];
68  for (int j = 0; j < num_tasks; ++j) {
69  tmp_array[j] = (IntVar)precedences[j, i];
70  }
71  model.Add(ranks[i] == LinearExpr.Sum(tmp_array) - 1);
72  }
73  }
74 
75  static void Main()
76  {
77  CpModel model = new CpModel();
78  // Three weeks.
79  int horizon = 100;
80  int num_tasks = 4;
81 
82  IntVar[] starts = new IntVar[num_tasks];
83  IntVar[] ends = new IntVar[num_tasks];
84  IntervalVar[] intervals = new IntervalVar[num_tasks];
85  ILiteral[] presences = new ILiteral[num_tasks];
86  IntVar[] ranks = new IntVar[num_tasks];
87 
88  IntVar true_var = model.NewConstant(1);
89 
90  // Creates intervals, half of them are optional.
91  for (int t = 0; t < num_tasks; ++t) {
92  starts[t] = model.NewIntVar(0, horizon, String.Format("start_{0}", t));
93  int duration = t + 1;
94  ends[t] = model.NewIntVar(0, horizon, String.Format("end_{0}", t));
95  if (t < num_tasks / 2) {
96  intervals[t] = model.NewIntervalVar(starts[t], duration, ends[t],
97  String.Format("interval_{0}", t));
98  presences[t] = true_var;
99  } else {
100  presences[t] = model.NewBoolVar(String.Format("presence_{0}", t));
101  intervals[t] = model.NewOptionalIntervalVar(
102  starts[t], duration, ends[t], presences[t],
103  String.Format("o_interval_{0}", t));
104  }
105 
106  // Ranks = -1 if and only if the tasks is not performed.
107  ranks[t] =
108  model.NewIntVar(-1, num_tasks - 1, String.Format("rank_{0}", t));
109  }
110 
111  // Adds NoOverlap constraint.
112  model.AddNoOverlap(intervals);
113 
114  // Adds ranking constraint.
115  RankTasks(model, starts, presences, ranks);
116 
117  // Adds a constraint on ranks.
118  model.Add(ranks[0] < ranks[1]);
119 
120  // Creates makespan variable.
121  IntVar makespan = model.NewIntVar(0, horizon, "makespan");
122  for (int t = 0; t < num_tasks; ++t) {
123  model.Add(ends[t] <= makespan).OnlyEnforceIf(presences[t]);
124  }
125  // Minimizes makespan - fixed gain per tasks performed.
126  // As the fixed cost is less that the duration of the last interval,
127  // the solver will not perform the last interval.
128  IntVar[] presences_as_int_vars = new IntVar[num_tasks];
129  for (int t = 0; t < num_tasks; ++t) {
130  presences_as_int_vars[t] = (IntVar)presences[t];
131  }
132  model.Minimize(2 * makespan - 7 * LinearExpr.Sum(presences_as_int_vars));
133 
134  // Creates a solver and solves the model.
135  CpSolver solver = new CpSolver();
136  CpSolverStatus status = solver.Solve(model);
137 
138  if (status == CpSolverStatus.Optimal) {
139  Console.WriteLine(String.Format("Optimal cost: {0}",
140  solver.ObjectiveValue));
141  Console.WriteLine(String.Format("Makespan: {0}", solver.Value(makespan)));
142  for (int t = 0; t < num_tasks; ++t) {
143  if (solver.BooleanValue(presences[t])) {
144  Console.WriteLine(String.Format(
145  "Task {0} starts at {1} with rank {2}",
146  t, solver.Value(starts[t]), solver.Value(ranks[t])));
147  } else {
148  Console.WriteLine(String.Format(
149  "Task {0} in not performed and ranked at {1}", t,
150  solver.Value(ranks[t])));
151  }
152  }
153  } else {
154  Console.WriteLine(
155  String.Format("Solver exited with nonoptimal status: {0}", status));
156  }
157  }
158 }
Wrapper class around the cp_model proto.
Definition: CpModel.cs:24
Boolean BooleanValue(ILiteral literal)
Definition: CpSolver.cs:152
void OnlyEnforceIf(ILiteral lit)
Definition: Constraints.cs:28
void Minimize(LinearExpr obj)
Definition: CpModel.cs:588
IntVar NewConstant(long value)
Definition: CpModel.cs:57
Constraint AddImplication(ILiteral a, ILiteral b)
Definition: CpModel.cs:395
Constraint AddNoOverlap(IEnumerable< IntervalVar > intervals)
Definition: CpModel.cs:538
static LinearExpr Sum(IEnumerable< IntVar > vars)
CpSolverStatus
The status returned by a solver trying to solve a CpModelProto.
Definition: CpModel.pb.cs:186
Constraint AddBoolOr(IEnumerable< ILiteral > literals)
Definition: CpModel.cs:405
IntVar NewIntVar(long lb, long ub, string name)
Definition: CpModel.cs:45
Constraint Add(BoundedLinearExpression lin)
Definition: CpModel.cs:104
double ObjectiveValue
Definition: CpSolver.cs:76
CpSolverStatus Solve(CpModel model)
Definition: CpSolver.cs:22
Definition: CpSolver.cs:20
long Value(LinearExpr e)
Definition: CpSolver.cs:96
IntVar NewBoolVar(string name)
Definition: CpModel.cs:67
Definition: CpModel.pb.cs:12