DotNet Reference

.Net Reference

CpModel.cs
Go to the documentation of this file.
1// Copyright 2010-2021 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
14namespace Google.OrTools.Sat
15{
16using System;
17using System.Collections.Generic;
18using Google.OrTools.Util;
19
23public class CpModel
24{
25 public CpModel()
26 {
27 model_ = new CpModelProto();
28 constant_map_ = new Dictionary<long, int>();
29 var_value_map_ = new Dictionary<int, long>(10);
30 terms_ = new Queue<Term>(10);
31 }
32
33 // Getters.
34
40 public CpModelProto Model
41 {
42 get {
43 return model_;
44 }
45 }
46
47 int Negated(int index)
48 {
49 return -index - 1;
50 }
51
52 // Integer variables and constraints.
53
64 public IntVar NewIntVar(long lb, long ub, string name)
65 {
66 return new IntVar(model_, lb, ub, name);
67 }
68
78 public IntVar NewIntVarFromDomain(Domain domain, string name)
79 {
80 return new IntVar(model_, domain, name);
81 }
82
88 public IntVar NewConstant(long value)
89 {
90 return new IntVar(model_, ConvertConstant(value));
91 }
92
98 public BoolVar NewBoolVar(string name)
99 {
100 return new BoolVar(model_, name);
101 }
102
109 {
110 return true_literal_ ??= new BoolVar(model_, ConvertConstant(1));
111 }
112
119 {
120 return TrueLiteral().Not();
121 }
122
123 private long FillLinearConstraint(LinearExpr expr, out LinearConstraintProto linear)
124 {
125 var dict = var_value_map_;
126 dict.Clear();
127 long constant = LinearExpr.GetVarValueMap(expr, dict, terms_);
128 var count = dict.Count;
129 linear = new LinearConstraintProto();
130 linear.Vars.Capacity = count;
131 linear.Vars.AddRange(dict.Keys);
132 linear.Coeffs.Capacity = count;
133 linear.Coeffs.AddRange(dict.Values);
134 return constant;
135 }
141 public Constraint AddLinearConstraint(LinearExpr expr, long lb, long ub)
142 {
143 long constant = FillLinearConstraint(expr, out var linear);
144 linear.Domain.Capacity = 2;
145 linear.Domain.Add(lb is Int64.MinValue or Int64.MaxValue ? lb : lb - constant);
146 linear.Domain.Add(ub is Int64.MinValue or Int64.MaxValue ? ub : ub - constant);
147
148 Constraint ct = new Constraint(model_);
149 ct.Proto.Linear = linear;
150 return ct;
151 }
152
159 {
160 long constant = FillLinearConstraint(expr, out var linear);
161 var array = domain.FlattenedIntervals();
162 linear.Domain.Capacity = array.Length;
163 foreach (long value in array)
164 {
165 linear.Domain.Add(value is Int64.MinValue or Int64.MaxValue ? value : value - constant);
166 }
167
168 Constraint ct = new Constraint(model_);
169 ct.Proto.Linear = linear;
170 return ct;
171 }
172
173 private Constraint AddLinearExpressionNotEqualCst(LinearExpr expr, long value)
174 {
175 long constant = FillLinearConstraint(expr, out var linear);
176 linear.Domain.Capacity = 4;
177 linear.Domain.Add(Int64.MinValue);
178 linear.Domain.Add(value - constant - 1);
179 linear.Domain.Add(value - constant + 1);
180 linear.Domain.Add(Int64.MaxValue);
181
182 Constraint ct = new Constraint(model_);
183 ct.Proto.Linear = linear;
184 return ct;
185 }
186
193 {
194 switch (lin.CtType)
195 {
196 case BoundedLinearExpression.Type.BoundExpression: {
197 return AddLinearConstraint(lin.Left, lin.Lb, lin.Ub);
198 }
199 case BoundedLinearExpression.Type.VarEqVar: {
200 return AddLinearConstraint(lin.Left - lin.Right, 0, 0);
201 }
202 case BoundedLinearExpression.Type.VarDiffVar: {
203 return AddLinearExpressionNotEqualCst(lin.Left - lin.Right, 0);
204 }
205 case BoundedLinearExpression.Type.VarEqCst: {
206 return AddLinearConstraint(lin.Left, lin.Lb, lin.Lb);
207 }
208 case BoundedLinearExpression.Type.VarDiffCst: {
209 return AddLinearExpressionNotEqualCst(lin.Left, lin.Lb);
210 }
211 }
212 return null;
213 }
214
220 public Constraint AddAllDifferent(IEnumerable<LinearExpr> exprs)
221 {
222 AllDifferentConstraintProto alldiff = new AllDifferentConstraintProto();
223 alldiff.Exprs.TrySetCapacity(exprs);
224 foreach (LinearExpr expr in exprs)
225 {
226 alldiff.Exprs.Add(GetLinearExpressionProto(expr));
227 }
228
229 Constraint ct = new Constraint(model_);
230 ct.Proto.AllDiff = alldiff;
231 return ct;
232 }
233
239 public Constraint AddElement(IntVar index, IEnumerable<IntVar> vars, IntVar target)
240 {
241 ElementConstraintProto element = new ElementConstraintProto();
242 element.Index = index.Index;
243 element.Vars.TrySetCapacity(vars);
244 foreach (IntVar var in vars)
245 {
246 element.Vars.Add(var.Index);
247 }
248 element.Target = target.Index;
249
250 Constraint ct = new Constraint(model_);
251 ct.Proto.Element = element;
252 return ct;
253 }
254
260 public Constraint AddElement(IntVar index, IEnumerable<long> values, IntVar target)
261 {
262 ElementConstraintProto element = new ElementConstraintProto();
263 element.Index = index.Index;
264 element.Vars.TrySetCapacity(values);
265 foreach (long value in values)
266 {
267 element.Vars.Add(ConvertConstant(value));
268 }
269 element.Target = target.Index;
270
271 Constraint ct = new Constraint(model_);
272 ct.Proto.Element = element;
273 return ct;
274 }
275
281 public Constraint AddElement(IntVar index, IEnumerable<int> values, IntVar target)
282 {
283 ElementConstraintProto element = new ElementConstraintProto();
284 element.Index = index.Index;
285 element.Vars.TrySetCapacity(values);
286 foreach (int value in values)
287 {
288 element.Vars.Add(ConvertConstant(value));
289 }
290 element.Target = target.Index;
291
292 Constraint ct = new Constraint(model_);
293 ct.Proto.Element = element;
294 return ct;
295 }
296
308 {
309 CircuitConstraint ct = new CircuitConstraint(model_);
310 ct.Proto.Circuit = new CircuitConstraintProto();
311 return ct;
312 }
313
326 {
328 ct.Proto.Routes = new RoutesConstraintProto();
329 return ct;
330 }
331
347 public TableConstraint AddAllowedAssignments(IEnumerable<IntVar> vars)
348 {
349 TableConstraintProto table = new TableConstraintProto();
350 table.Vars.TrySetCapacity(vars);
351 foreach (IntVar var in vars)
352 {
353 table.Vars.Add(var.Index);
354 }
355
356 TableConstraint ct = new TableConstraint(model_);
357 ct.Proto.Table = table;
358 return ct;
359 }
360
375 public TableConstraint AddForbiddenAssignments(IEnumerable<IntVar> vars)
376 {
378 ct.Proto.Table.Negated = true;
379 return ct;
380 }
381
415 public AutomatonConstraint AddAutomaton(IEnumerable<IntVar> vars, long starting_state,
416 IEnumerable<long> final_states)
417 {
418 AutomatonConstraintProto aut = new AutomatonConstraintProto();
419 aut.Vars.TrySetCapacity(vars);
420 foreach (IntVar var in vars)
421 {
422 aut.Vars.Add(var.Index);
423 }
424
425 aut.StartingState = starting_state;
426 aut.FinalStates.AddRange(final_states);
427
429 ct.Proto.Automaton = aut;
430 return ct;
431 }
432
446 public Constraint AddInverse(IEnumerable<IntVar> direct, IEnumerable<IntVar> reverse)
447 {
448 InverseConstraintProto inverse = new InverseConstraintProto();
449 inverse.FDirect.TrySetCapacity(direct);
450 foreach (IntVar var in direct)
451 {
452 inverse.FDirect.Add(var.Index);
453 }
454
455 inverse.FInverse.TrySetCapacity(reverse);
456 foreach (IntVar var in reverse)
457 {
458 inverse.FInverse.Add(var.Index);
459 }
460
461 Constraint ct = new Constraint(model_);
462 ct.Proto.Inverse = inverse;
463 return ct;
464 }
465
492 public ReservoirConstraint AddReservoirConstraint(long minLevel, long maxLevel)
493 {
494 ReservoirConstraintProto res = new ReservoirConstraintProto();
495
496 res.MinLevel = minLevel;
497 res.MaxLevel = maxLevel;
498
499 ReservoirConstraint ct = new ReservoirConstraint(this, model_);
500 ct.Proto.Reservoir = res;
501 return ct;
502 }
503
504 public void AddMapDomain(IntVar var, IEnumerable<IntVar> bool_vars, long offset = 0)
505 {
506 int i = 0;
507 int var_index = var.Index;
508 foreach (IntVar bool_var in bool_vars)
509 {
510 int b_index = bool_var.Index;
511
512 LinearConstraintProto lin1 = new LinearConstraintProto();
513 lin1.Vars.Capacity = 1;
514 lin1.Vars.Add(var_index);
515 lin1.Coeffs.Capacity = 1;
516 lin1.Coeffs.Add(1L);
517 lin1.Domain.Capacity = 2;
518 lin1.Domain.Add(offset + i);
519 lin1.Domain.Add(offset + i);
520 ConstraintProto ct1 = new ConstraintProto();
521 ct1.Linear = lin1;
522 ct1.EnforcementLiteral.Add(b_index);
523 model_.Constraints.Add(ct1);
524
525 LinearConstraintProto lin2 = new LinearConstraintProto();
526 lin1.Vars.Capacity = 1;
527 lin2.Vars.Add(var_index);
528 lin1.Coeffs.Capacity = 1;
529 lin2.Coeffs.Add(1L);
530 lin1.Domain.Capacity = 4;
531 lin2.Domain.Add(Int64.MinValue);
532 lin2.Domain.Add(offset + i - 1);
533 lin2.Domain.Add(offset + i + 1);
534 lin2.Domain.Add(Int64.MaxValue);
535 ConstraintProto ct2 = new ConstraintProto();
536 ct2.Linear = lin2;
537 ct2.EnforcementLiteral.Add(-b_index - 1);
538 model_.Constraints.Add(ct2);
539
540 i++;
541 }
542 }
543
550 {
551 BoolArgumentProto or = new BoolArgumentProto();
552 or.Literals.Capacity = 2;
553 or.Literals.Add(a.Not().GetIndex());
554 or.Literals.Add(b.GetIndex());
555
556 Constraint ct = new Constraint(model_);
557 ct.Proto.BoolOr = or;
558 return ct;
559 }
560
566 public Constraint AddBoolOr(IEnumerable<ILiteral> literals)
567 {
568 BoolArgumentProto bool_argument = new BoolArgumentProto();
569 bool_argument.Literals.TrySetCapacity(literals);
570 foreach (ILiteral lit in literals)
571 {
572 bool_argument.Literals.Add(lit.GetIndex());
573 }
574
575 Constraint ct = new Constraint(model_);
576 ct.Proto.BoolOr = bool_argument;
577 return ct;
578 }
579
585 public Constraint AddAtLeastOne(IEnumerable<ILiteral> literals)
586 {
587 return AddBoolOr(literals);
588 }
589
595 public Constraint AddAtMostOne(IEnumerable<ILiteral> literals)
596 {
597 BoolArgumentProto bool_argument = new BoolArgumentProto();
598 bool_argument.Literals.TrySetCapacity(literals);
599 foreach (ILiteral lit in literals)
600 {
601 bool_argument.Literals.Add(lit.GetIndex());
602 }
603
604 Constraint ct = new Constraint(model_);
605 ct.Proto.AtMostOne = bool_argument;
606 return ct;
607 }
608
614 public Constraint AddExactlyOne(IEnumerable<ILiteral> literals)
615 {
616 BoolArgumentProto bool_argument = new BoolArgumentProto();
617 bool_argument.Literals.TrySetCapacity(literals);
618 foreach (ILiteral lit in literals)
619 {
620 bool_argument.Literals.Add(lit.GetIndex());
621 }
622
623 Constraint ct = new Constraint(model_);
624 ct.Proto.ExactlyOne = bool_argument;
625 return ct;
626 }
627
633 public Constraint AddBoolAnd(IEnumerable<ILiteral> literals)
634 {
635 BoolArgumentProto bool_argument = new BoolArgumentProto();
636 bool_argument.Literals.TrySetCapacity(literals);
637 foreach (ILiteral lit in literals)
638 {
639 bool_argument.Literals.Add(lit.GetIndex());
640 }
641
642 Constraint ct = new Constraint(model_);
643 ct.Proto.BoolAnd = bool_argument;
644 return ct;
645 }
646
652 public Constraint AddBoolXor(IEnumerable<ILiteral> literals)
653 {
654 BoolArgumentProto bool_argument = new BoolArgumentProto();
655 bool_argument.Literals.TrySetCapacity(literals);
656 foreach (ILiteral lit in literals)
657 {
658 bool_argument.Literals.Add(lit.GetIndex());
659 }
660
661 Constraint ct = new Constraint(model_);
662 ct.Proto.BoolXor = bool_argument;
663 return ct;
664 }
665
671 public Constraint AddMinEquality(LinearExpr target, IEnumerable<LinearExpr> exprs)
672 {
673 LinearArgumentProto lin = new LinearArgumentProto();
674 lin.Exprs.TrySetCapacity(exprs);
675 foreach (LinearExpr expr in exprs)
676 {
677 lin.Exprs.Add(GetLinearExpressionProto(expr, /*negate=*/true));
678 }
679 lin.Target = GetLinearExpressionProto(target, /*negate=*/true);
680
681 Constraint ct = new Constraint(model_);
682 ct.Proto.LinMax = lin;
683 return ct;
684 }
685
691 public Constraint AddMaxEquality(LinearExpr target, IEnumerable<LinearExpr> exprs)
692 {
693 LinearArgumentProto lin = new LinearArgumentProto();
694 lin.Exprs.TrySetCapacity(exprs);
695 foreach (LinearExpr expr in exprs)
696 {
697 lin.Exprs.Add(GetLinearExpressionProto(expr));
698 }
699 lin.Target = GetLinearExpressionProto(target);
700
701 Constraint ct = new Constraint(model_);
702 ct.Proto.LinMax = lin;
703 return ct;
704 }
705
711 public Constraint AddDivisionEquality<T, N, D>(T target, N num, D denom)
712 {
713 LinearArgumentProto div = new LinearArgumentProto();
714 div.Exprs.Capacity = 2;
715 div.Exprs.Add(GetLinearExpressionProto(GetLinearExpr(num)));
716 div.Exprs.Add(GetLinearExpressionProto(GetLinearExpr(denom)));
717 div.Target = GetLinearExpressionProto(GetLinearExpr(target));
718
719 Constraint ct = new Constraint(model_);
720 ct.Proto.IntDiv = div;
721 return ct;
722 }
723
730 {
731 LinearArgumentProto abs = new LinearArgumentProto();
732 abs.Exprs.Capacity = 2;
733 abs.Exprs.Add(GetLinearExpressionProto(expr));
734 abs.Exprs.Add(GetLinearExpressionProto(expr, /*negate=*/true));
735 abs.Target = GetLinearExpressionProto(target);
736
737 Constraint ct = new Constraint(model_);
738 ct.Proto.LinMax = abs;
739 return ct;
740 }
741
747 public Constraint AddModuloEquality<T, V, M>(T target, V v, M m)
748 {
749 LinearArgumentProto mod = new LinearArgumentProto();
750 mod.Exprs.Capacity = 2;
751 mod.Exprs.Add(GetLinearExpressionProto(GetLinearExpr(v)));
752 mod.Exprs.Add(GetLinearExpressionProto(GetLinearExpr(m)));
753 mod.Target = GetLinearExpressionProto(GetLinearExpr(target));
754
755 Constraint ct = new Constraint(model_);
756 ct.Proto.IntMod = mod;
757 return ct;
758 }
759
765 public Constraint AddMultiplicationEquality(LinearExpr target, IEnumerable<LinearExpr> exprs)
766 {
767 LinearArgumentProto prod = new LinearArgumentProto();
768 prod.Target = GetLinearExpressionProto(target);
769 prod.Exprs.TrySetCapacity(exprs);
770 foreach (LinearExpr expr in exprs)
771 {
772 prod.Exprs.Add(GetLinearExpressionProto(expr));
773 }
774
775 Constraint ct = new Constraint(model_);
776 ct.Proto.IntProd = prod;
777 return ct;
778 }
779
786 {
787 LinearArgumentProto prod = new LinearArgumentProto();
788 prod.Target = GetLinearExpressionProto(target);
789 prod.Exprs.Capacity = 2;
790 prod.Exprs.Add(GetLinearExpressionProto(left));
791 prod.Exprs.Add(GetLinearExpressionProto(right));
792
793 Constraint ct = new Constraint(model_);
794 ct.Proto.IntProd = prod;
795 return ct;
796 }
797
798 // Scheduling support
799
815 public IntervalVar NewIntervalVar<S, D, E>(S start, D size, E end, string name)
816 {
817 LinearExpr startExpr = GetLinearExpr(start);
818 LinearExpr sizeExpr = GetLinearExpr(size);
819 LinearExpr endExpr = GetLinearExpr(end);
820 Add(startExpr + sizeExpr == endExpr);
821
822 LinearExpressionProto startProto = GetLinearExpressionProto(startExpr);
823 LinearExpressionProto sizeProto = GetLinearExpressionProto(sizeExpr);
824 LinearExpressionProto endProto = GetLinearExpressionProto(endExpr);
825 return new IntervalVar(model_, startProto, sizeProto, endProto, name);
826 }
827
843 public IntervalVar NewFixedSizeIntervalVar<S>(S start, long size, string name)
844 {
845 LinearExpr startExpr = GetLinearExpr(start);
846 LinearExpr sizeExpr = GetLinearExpr(size);
847 LinearExpr endExpr = LinearExpr.Sum(new LinearExpr[] { startExpr, sizeExpr });
848
849 LinearExpressionProto startProto = GetLinearExpressionProto(startExpr);
850 LinearExpressionProto sizeProto = GetLinearExpressionProto(sizeExpr);
851 LinearExpressionProto endProto = GetLinearExpressionProto(endExpr);
852 return new IntervalVar(model_, startProto, sizeProto, endProto, name);
853 }
854
873 public IntervalVar NewOptionalIntervalVar<S, D, E>(S start, D size, E end, ILiteral is_present, string name)
874 {
875 LinearExpr startExpr = GetLinearExpr(start);
876 LinearExpr sizeExpr = GetLinearExpr(size);
877 LinearExpr endExpr = GetLinearExpr(end);
878 Add(startExpr + sizeExpr == endExpr).OnlyEnforceIf(is_present);
879
880 LinearExpressionProto startProto = GetLinearExpressionProto(startExpr);
881 LinearExpressionProto sizeProto = GetLinearExpressionProto(sizeExpr);
882 LinearExpressionProto endProto = GetLinearExpressionProto(endExpr);
883 return new IntervalVar(model_, startProto, sizeProto, endProto, is_present.GetIndex(), name);
884 }
885
904 public IntervalVar NewOptionalFixedSizeIntervalVar<S>(S start, long size, ILiteral is_present, string name)
905 {
906 LinearExpr startExpr = GetLinearExpr(start);
907 LinearExpr sizeExpr = GetLinearExpr(size);
908 LinearExpr endExpr = LinearExpr.Sum(new LinearExpr[] { startExpr, sizeExpr });
909
910 LinearExpressionProto startProto = GetLinearExpressionProto(startExpr);
911 LinearExpressionProto sizeProto = GetLinearExpressionProto(sizeExpr);
912 LinearExpressionProto endProto = GetLinearExpressionProto(endExpr);
913 return new IntervalVar(model_, startProto, sizeProto, endProto, is_present.GetIndex(), name);
914 }
915
925 public Constraint AddNoOverlap(IEnumerable<IntervalVar> intervals)
926 {
927 NoOverlapConstraintProto no_overlap = new NoOverlapConstraintProto();
928 no_overlap.Intervals.TrySetCapacity(intervals);
929 foreach (IntervalVar var in intervals)
930 {
931 no_overlap.Intervals.Add(var.GetIndex());
932 }
933
934 Constraint ct = new Constraint(model_);
935 ct.Proto.NoOverlap = no_overlap;
936 return ct;
937 }
938
956 {
958 ct.Proto.NoOverlap2D = new NoOverlap2DConstraintProto();
959 return ct;
960 }
961
982 {
983 CumulativeConstraintProto cumul = new CumulativeConstraintProto();
984 LinearExpr capacityExpr = GetLinearExpr(capacity);
985 cumul.Capacity = GetLinearExpressionProto(capacityExpr);
986
987 CumulativeConstraint ct = new CumulativeConstraint(this, model_);
988 ct.Proto.Cumulative = cumul;
989 return ct;
990 }
991
992 // Objective.
993
995 public void Minimize(LinearExpr obj)
996 {
997 SetObjective(obj, true);
998 }
999
1001 public void Maximize(LinearExpr obj)
1002 {
1003 SetObjective(obj, false);
1004 }
1005
1007 void ClearObjective()
1008 {
1009 model_.Objective = null;
1010 }
1011
1013 bool HasObjective()
1014 {
1015 return model_.Objective is not null;
1016 }
1017
1018 // Search Decision.
1019
1021 public void AddDecisionStrategy(IEnumerable<IntVar> vars,
1022 DecisionStrategyProto.Types.VariableSelectionStrategy var_str,
1023 DecisionStrategyProto.Types.DomainReductionStrategy dom_str)
1024 {
1025 DecisionStrategyProto ds = new DecisionStrategyProto();
1026 ds.Variables.TrySetCapacity(vars);
1027 foreach (IntVar var in vars)
1028 {
1029 ds.Variables.Add(var.Index);
1030 }
1031 ds.VariableSelectionStrategy = var_str;
1032 ds.DomainReductionStrategy = dom_str;
1033 model_.SearchStrategy.Add(ds);
1034 }
1035
1037 public void AddHint(IntVar var, long value)
1038 {
1039 model_.SolutionHint ??= new PartialVariableAssignment();
1040 model_.SolutionHint.Vars.Add(var.GetIndex());
1041 model_.SolutionHint.Values.Add(value);
1042 }
1043
1045 public void ClearHints()
1046 {
1047 model_.SolutionHint = null;
1048 }
1049
1051 public void AddAssumption(ILiteral lit)
1052 {
1053 model_.Assumptions.Add(lit.GetIndex());
1054 }
1055
1057 public void AddAssumptions(IEnumerable<ILiteral> literals)
1058 {
1059 foreach (ILiteral lit in literals)
1060 {
1061 AddAssumption(lit);
1062 }
1063 }
1064
1066 public void ClearAssumptions()
1067 {
1068 model_.Assumptions.Clear();
1069 }
1070
1071 // Internal methods.
1072
1073 void SetObjective(LinearExpr obj, bool minimize)
1074 {
1075 CpObjectiveProto objective = new CpObjectiveProto();
1076 if (obj is null)
1077 {
1078 objective.Offset = 0L;
1079 objective.ScalingFactor = minimize ? 1L : -1;
1080 }
1081 else if (obj is IntVar intVar)
1082 {
1083 objective.Offset = 0L;
1084 objective.Vars.Capacity = 1;
1085 objective.Vars.Add(intVar.Index);
1086
1087 objective.Coeffs.Capacity = 1;
1088 if (minimize)
1089 {
1090 objective.Coeffs.Add(1L);
1091 objective.ScalingFactor = 1L;
1092 }
1093 else
1094 {
1095 objective.Coeffs.Add(-1L);
1096 objective.ScalingFactor = -1L;
1097 }
1098 }
1099 else
1100 {
1101 var dict = var_value_map_;
1102 dict.Clear();
1103 long constant = LinearExpr.GetVarValueMap(obj, dict, terms_);
1104 var dictCount = dict.Count;
1105 objective.Vars.Capacity = dictCount;
1106 objective.Vars.AddRange(dict.Keys);
1107 objective.Coeffs.Capacity = dictCount;
1108 if (minimize)
1109 {
1110 objective.Coeffs.AddRange(dict.Values);
1111 objective.ScalingFactor = 1L;
1112 objective.Offset = constant;
1113 }
1114 else
1115 {
1116 foreach (var coeff in dict.Values)
1117 {
1118 objective.Coeffs.Add(-coeff);
1119 }
1120 objective.ScalingFactor = -1L;
1121 objective.Offset = -constant;
1122 }
1123 }
1124 model_.Objective = objective;
1125 }
1126
1128 public String ModelStats()
1129 {
1130 return CpSatHelper.ModelStats(model_);
1131 }
1132
1143 public Boolean ExportToFile(String file)
1144 {
1145 return CpSatHelper.WriteModelToFile(model_, file);
1146 }
1147
1153 public String Validate()
1154 {
1155 return CpSatHelper.ValidateModel(model_);
1156 }
1157
1158 private int ConvertConstant(long value)
1159 {
1160 if (constant_map_.TryGetValue(value, out var index))
1161 {
1162 return index;
1163 }
1164
1165 index = model_.Variables.Count;
1166 IntegerVariableProto var = new IntegerVariableProto();
1167 var.Domain.Capacity = 2;
1168 var.Domain.Add(value);
1169 var.Domain.Add(value);
1170 constant_map_.Add(value, index);
1171 model_.Variables.Add(var);
1172 return index;
1173 }
1174
1175 internal LinearExpr GetLinearExpr<X>(X x)
1176 {
1177 if (typeof(X) == typeof(IntVar))
1178 {
1179 return (IntVar)(Object)x;
1180 }
1181 if (typeof(X) == typeof(long) || typeof(X) == typeof(int) || typeof(X) == typeof(short))
1182 {
1183 return LinearExpr.Constant(Convert.ToInt64(x));
1184 }
1185 if (typeof(X) == typeof(LinearExpr))
1186 {
1187 return (LinearExpr)(Object)x;
1188 }
1189 throw new ArgumentException("Cannot convert argument to LinearExpr");
1190 }
1191
1192 internal LinearExpressionProto GetLinearExpressionProto(LinearExpr expr, bool negate = false)
1193 {
1194 var dict = var_value_map_;
1195 dict.Clear();
1196 long constant = LinearExpr.GetVarValueMap(expr, dict, terms_);
1197
1198 LinearExpressionProto linear = new LinearExpressionProto();
1199 var dictCount = dict.Count;
1200 linear.Vars.Capacity = dictCount;
1201 linear.Vars.AddRange(dict.Keys);
1202 linear.Coeffs.Capacity = dictCount;
1203 if (negate)
1204 {
1205 foreach (var coeff in dict.Values)
1206 {
1207 linear.Coeffs.Add(-coeff);
1208 }
1209 linear.Offset = -constant;
1210 }
1211 else
1212 {
1213 linear.Coeffs.AddRange(dict.Values);
1214 linear.Offset = constant;
1215 }
1216
1217 return linear;
1218 }
1219
1220 private CpModelProto model_;
1221 private Dictionary<long, int> constant_map_;
1222 private Dictionary<int, long> var_value_map_;
1223 private BoolVar true_literal_;
1224 private Queue<Term> terms_;
1225}
1226
1227} // namespace Google.OrTools.Sat
Specialized automaton constraint.
Definition: Constraints.cs:276
Holds a Boolean variable.
Holds a linear constraint: expression ∈ domain
Specialized circuit constraint.
Definition: Constraints.cs:85
Wrapper around a ConstraintProto.
Definition: Constraints.cs:29
void OnlyEnforceIf(ILiteral lit)
Adds a literal to the constraint.
Definition: Constraints.cs:38
ConstraintProto Proto
The underlying constraint proto.
Definition: Constraints.cs:62
Wrapper class around the cp_model proto.
Definition: CpModel.cs:24
void AddAssumption(ILiteral lit)
Adds a literal to the model as assumption.
Definition: CpModel.cs:1051
Constraint AddInverse(IEnumerable< IntVar > direct, IEnumerable< IntVar > reverse)
Adds Inverse(variables, inverseVariables).
Definition: CpModel.cs:446
ILiteral FalseLiteral()
Returns a constant false literal.
Definition: CpModel.cs:118
Constraint AddLinearExpressionInDomain(LinearExpr expr, Domain domain)
Adds expr ∈ domain.
Definition: CpModel.cs:158
IntervalVar NewOptionalFixedSizeIntervalVar< S >(S start, long size, ILiteral is_present, string name)
Creates an optional interval variable from an affine expression start, a fixed size,...
Definition: CpModel.cs:904
IntervalVar NewIntervalVar< S, D, E >(S start, D size, E end, string name)
Creates an interval variable from three affine expressions start, size, and end.
Definition: CpModel.cs:815
TableConstraint AddAllowedAssignments(IEnumerable< IntVar > vars)
Adds AllowedAssignments(variables).
Definition: CpModel.cs:347
void Minimize(LinearExpr obj)
Adds a minimization objective of a linear expression.
Definition: CpModel.cs:995
Constraint AddBoolXor(IEnumerable< ILiteral > literals)
Adds XOr(literals) == true.
Definition: CpModel.cs:652
void AddMapDomain(IntVar var, IEnumerable< IntVar > bool_vars, long offset=0)
Definition: CpModel.cs:504
void ClearAssumptions()
Clears all assumptions from the model.
Definition: CpModel.cs:1066
Constraint AddAtLeastOne(IEnumerable< ILiteral > literals)
Same as AddBoolOr: ∑(literals) ≥ 1.
Definition: CpModel.cs:585
IntervalVar NewFixedSizeIntervalVar< S >(S start, long size, string name)
Creates an interval variable from an affine expression start, and a fixed size.
Definition: CpModel.cs:843
void AddDecisionStrategy(IEnumerable< IntVar > vars, DecisionStrategyProto.Types.VariableSelectionStrategy var_str, DecisionStrategyProto.Types.DomainReductionStrategy dom_str)
Adds DecisionStrategy(variables, var_str, dom_str).
Definition: CpModel.cs:1021
ILiteral TrueLiteral()
Returns a constant true literal.
Definition: CpModel.cs:108
IntervalVar NewOptionalIntervalVar< S, D, E >(S start, D size, E end, ILiteral is_present, string name)
Creates an optional interval variable from three affine expressions start, size, and end,...
Definition: CpModel.cs:873
Boolean ExportToFile(String file)
Write the model as a protocol buffer to file.
Definition: CpModel.cs:1143
AutomatonConstraint AddAutomaton(IEnumerable< IntVar > vars, long starting_state, IEnumerable< long > final_states)
Adds an automaton constraint.
Definition: CpModel.cs:415
Constraint AddMaxEquality(LinearExpr target, IEnumerable< LinearExpr > exprs)
Adds target == Max(exprs).
Definition: CpModel.cs:691
Constraint AddDivisionEquality< T, N, D >(T target, N num, D denom)
Adds target == num / denom (integer division rounded towards 0).
Definition: CpModel.cs:711
void ClearHints()
Clears all hinting from the model.
Definition: CpModel.cs:1045
ReservoirConstraint AddReservoirConstraint(long minLevel, long maxLevel)
Adds a reservoir constraint with optional refill/emptying events.
Definition: CpModel.cs:492
Constraint AddExactlyOne(IEnumerable< ILiteral > literals)
Adds ExactlyOne(literals): ∑(literals) == 1.
Definition: CpModel.cs:614
Constraint AddNoOverlap(IEnumerable< IntervalVar > intervals)
Adds NoOverlap(intervalVars).
Definition: CpModel.cs:925
BoolVar NewBoolVar(string name)
Creates an Boolean variable with given domain.
Definition: CpModel.cs:98
CircuitConstraint AddCircuit()
Adds and returns an empty circuit constraint.
Definition: CpModel.cs:307
IntVar NewConstant(long value)
Creates a constant variable.
Definition: CpModel.cs:88
void AddHint(IntVar var, long value)
Adds variable hinting to the model.
Definition: CpModel.cs:1037
Constraint AddElement(IntVar index, IEnumerable< IntVar > vars, IntVar target)
Adds the element constraint: variables[index] == target.
Definition: CpModel.cs:239
Constraint AddMinEquality(LinearExpr target, IEnumerable< LinearExpr > exprs)
Adds target == Min(exprs).
Definition: CpModel.cs:671
Constraint AddAtMostOne(IEnumerable< ILiteral > literals)
Adds AtMostOne(literals): ∑(literals) ≤ 1.
Definition: CpModel.cs:595
Constraint AddMultiplicationEquality(LinearExpr target, IEnumerable< LinearExpr > exprs)
Adds target == ∏(exprs).
Definition: CpModel.cs:765
void Maximize(LinearExpr obj)
Adds a maximization objective of a linear expression.
Definition: CpModel.cs:1001
Constraint AddImplication(ILiteral a, ILiteral b)
Adds a ⇒ b.
Definition: CpModel.cs:549
NoOverlap2dConstraint AddNoOverlap2D()
Adds NoOverlap2D().
Definition: CpModel.cs:955
IntVar NewIntVar(long lb, long ub, string name)
Creates an integer variable with domain [lb, ub].
Definition: CpModel.cs:64
Constraint AddBoolAnd(IEnumerable< ILiteral > literals)
Adds And(literals) == true.
Definition: CpModel.cs:633
Constraint AddBoolOr(IEnumerable< ILiteral > literals)
Adds Or(literals) == true.
Definition: CpModel.cs:566
Constraint AddModuloEquality< T, V, M >(T target, V v, M m)
Adds target == v % m.
Definition: CpModel.cs:747
Constraint AddElement(IntVar index, IEnumerable< long > values, IntVar target)
Adds the element constraint: values[index] == target.
Definition: CpModel.cs:260
CumulativeConstraint AddCumulative< C >(C capacity)
Adds Cumulative(capacity).
Definition: CpModel.cs:981
String ModelStats()
Returns some statistics on model as a string.
Definition: CpModel.cs:1128
MultipleCircuitConstraint AddMultipleCircuit()
Adds and returns an empty multiple circuit constraint.
Definition: CpModel.cs:325
IntVar NewIntVarFromDomain(Domain domain, string name)
Creates an integer variable with given domain.
Definition: CpModel.cs:78
Constraint AddMultiplicationEquality(LinearExpr target, LinearExpr left, LinearExpr right)
Adds target == left * right.
Definition: CpModel.cs:785
Constraint AddElement(IntVar index, IEnumerable< int > values, IntVar target)
Adds the element constraint: values[index] == target.
Definition: CpModel.cs:281
CpModelProto Model
The underlying CpModelProto.
Definition: CpModel.cs:41
Constraint AddAllDifferent(IEnumerable< LinearExpr > exprs)
Adds the constraint AllDifferent(exprs).
Definition: CpModel.cs:220
String Validate()
Returns a non empty string explaining the issue if the model is invalid.
Definition: CpModel.cs:1153
Constraint Add(BoundedLinearExpression lin)
Adds a linear constraint to the model.
Definition: CpModel.cs:192
Constraint AddAbsEquality(LinearExpr target, LinearExpr expr)
Adds target == abs(expr).
Definition: CpModel.cs:729
Constraint AddLinearConstraint(LinearExpr expr, long lb, long ub)
Adds lb ≤ expr ≤ ub.
Definition: CpModel.cs:141
void AddAssumptions(IEnumerable< ILiteral > literals)
Adds multiple literals to the model as assumptions.
Definition: CpModel.cs:1057
TableConstraint AddForbiddenAssignments(IEnumerable< IntVar > vars)
Adds ForbiddenAssignments(variables).
Definition: CpModel.cs:375
Specialized cumulative constraint.
Definition: Constraints.cs:365
Holds a integer variable with a discrete domain.
int GetIndex()
Returns the index of the variable in the underlying CpModelProto.
int Index
Returns the index of the variable in the underlying CpModelProto.
Holds a linear expression: sum (ai * xi) + b.
static LinearExpr Sum(IEnumerable< LinearExpr > exprs)
Creates Sum(exprs).
Specialized multiple circuit constraint.
Definition: Constraints.cs:119
Specialized NoOverlap2D constraint.
Definition: Constraints.cs:407
Specialized reservoir constraint.
Definition: Constraints.cs:307
Specialized assignment constraint.
Definition: Constraints.cs:152
Holds a Boolean variable or its negation.
int GetIndex()
Returns the logical index of the literal.
ILiteral Not()
Returns the Boolean negation of the literal.