Java Reference

Java Reference

CpModel.java
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
14package com.google.ortools.sat;
15
16import com.google.ortools.sat.AllDifferentConstraintProto;
17import com.google.ortools.sat.AutomatonConstraintProto;
18import com.google.ortools.sat.BoolArgumentProto;
19import com.google.ortools.sat.CircuitConstraintProto;
20import com.google.ortools.sat.CpModelProto;
21import com.google.ortools.sat.CpObjectiveProto;
22import com.google.ortools.sat.CumulativeConstraintProto;
23import com.google.ortools.sat.DecisionStrategyProto;
24import com.google.ortools.sat.ElementConstraintProto;
25import com.google.ortools.sat.IntegerArgumentProto;
26import com.google.ortools.sat.InverseConstraintProto;
27import com.google.ortools.sat.LinearConstraintProto;
28import com.google.ortools.sat.NoOverlap2DConstraintProto;
29import com.google.ortools.sat.NoOverlapConstraintProto;
30import com.google.ortools.sat.ReservoirConstraintProto;
31import com.google.ortools.sat.TableConstraintProto;
32import com.google.ortools.util.Domain;
33import java.util.LinkedHashMap;
34import java.util.Map;
35
41public final class CpModel {
42 static class CpModelException extends RuntimeException {
43 public CpModelException(String methodName, String msg) {
44 // Call constructor of parent Exception
45 super(methodName + ": " + msg);
46 }
47 }
48
50 public static class MismatchedArrayLengths extends CpModelException {
51 public MismatchedArrayLengths(String methodName, String array1Name, String array2Name) {
52 super(methodName, array1Name + " and " + array2Name + " have mismatched lengths");
53 }
54 }
55
57 public static class WrongLength extends CpModelException {
58 public WrongLength(String methodName, String msg) {
59 super(methodName, msg);
60 }
61 }
62 public CpModel() {
63 modelBuilder = CpModelProto.newBuilder();
64 constantMap = new LinkedHashMap<>();
65 }
66
67 // Integer variables.
68
70 public IntVar newIntVar(long lb, long ub, String name) {
71 return new IntVar(modelBuilder, new Domain(lb, ub), name);
72 }
73
81 public IntVar newIntVarFromDomain(Domain domain, String name) {
82 return new IntVar(modelBuilder, domain, name);
83 }
84
86 public IntVar newBoolVar(String name) {
87 return new IntVar(modelBuilder, new Domain(0, 1), name);
88 }
89
91 public IntVar newConstant(long value) {
92 if (constantMap.containsKey(value)) {
93 return constantMap.get(value);
94 }
95 IntVar cste = new IntVar(modelBuilder, new Domain(value), ""); // bounds and name.
96 constantMap.put(value, cste);
97 return cste;
98 }
99
102 return newConstant(1);
103 }
104
107 return newConstant(0);
108 }
109
110 // Boolean Constraints.
111
113 public Constraint addBoolOr(Literal[] literals) {
114 Constraint ct = new Constraint(modelBuilder);
115 BoolArgumentProto.Builder boolOr = ct.getBuilder().getBoolOrBuilder();
116 for (Literal lit : literals) {
117 boolOr.addLiterals(lit.getIndex());
118 }
119 return ct;
120 }
121
123 public Constraint addBoolAnd(Literal[] literals) {
124 Constraint ct = new Constraint(modelBuilder);
125 BoolArgumentProto.Builder boolOr = ct.getBuilder().getBoolAndBuilder();
126 for (Literal lit : literals) {
127 boolOr.addLiterals(lit.getIndex());
128 }
129 return ct;
130 }
131
133 public Constraint addBoolXor(Literal[] literals) {
134 Constraint ct = new Constraint(modelBuilder);
135 BoolArgumentProto.Builder boolOr = ct.getBuilder().getBoolXorBuilder();
136 for (Literal lit : literals) {
137 boolOr.addLiterals(lit.getIndex());
138 }
139 return ct;
140 }
141
144 return addBoolOr(new Literal[] {a.not(), b});
145 }
146
147 // Linear constraints.
148
151 Constraint ct = new Constraint(modelBuilder);
152 LinearConstraintProto.Builder lin = ct.getBuilder().getLinearBuilder();
153 for (int i = 0; i < expr.numElements(); ++i) {
154 lin.addVars(expr.getVariable(i).getIndex()).addCoeffs(expr.getCoefficient(i));
155 }
156 long offset = expr.getOffset();
157 if (offset != 0) {
158 lin.addVars(newConstant(1).getIndex()).addCoeffs(offset);
159 }
160 for (long b : domain.flattenedIntervals()) {
161 lin.addDomain(b);
162 }
163 return ct;
164 }
165
167 public Constraint addLinearConstraint(LinearExpr expr, long lb, long ub) {
168 return addLinearExpressionInDomain(expr, new Domain(lb, ub));
169 }
170
172 public Constraint addEquality(LinearExpr expr, long value) {
173 return addLinearExpressionInDomain(expr, new Domain(value));
174 }
175
178 return addLinearExpressionInDomain(new Difference(left, right), new Domain(0));
179 }
180
182 public Constraint addEqualityWithOffset(LinearExpr left, LinearExpr right, long offset) {
183 return addLinearExpressionInDomain(new Difference(left, right), new Domain(-offset));
184 }
185
187 public Constraint addLessOrEqual(LinearExpr expr, long value) {
188 return addLinearExpressionInDomain(expr, new Domain(Long.MIN_VALUE, value));
189 }
190
193 return addLinearExpressionInDomain(new Difference(left, right), new Domain(Long.MIN_VALUE, 0));
194 }
195
197 public Constraint addLessThan(LinearExpr expr, long value) {
198 return addLinearExpressionInDomain(expr, new Domain(Long.MIN_VALUE, value - 1));
199 }
200
203 return addLinearExpressionInDomain(new Difference(left, right), new Domain(Long.MIN_VALUE, -1));
204 }
205
207 public Constraint addLessOrEqualWithOffset(LinearExpr left, LinearExpr right, long offset) {
209 new Difference(left, right), new Domain(Long.MIN_VALUE, -offset));
210 }
211
213 public Constraint addGreaterOrEqual(LinearExpr expr, long value) {
214 return addLinearExpressionInDomain(expr, new Domain(value, Long.MAX_VALUE));
215 }
216
219 return addLinearExpressionInDomain(new Difference(left, right), new Domain(0, Long.MAX_VALUE));
220 }
221
223 public Constraint addGreaterThan(LinearExpr expr, long value) {
224 return addLinearExpressionInDomain(expr, new Domain(value + 1, Long.MAX_VALUE));
225 }
226
229 return addLinearExpressionInDomain(new Difference(left, right), new Domain(1, Long.MAX_VALUE));
230 }
231
235 new Difference(left, right), new Domain(-offset, Long.MAX_VALUE));
236 }
237
239 public Constraint addDifferent(LinearExpr expr, long value) {
240 return addLinearExpressionInDomain(expr,
241 Domain.fromFlatIntervals(
242 new long[] {Long.MIN_VALUE, value - 1, value + 1, Long.MAX_VALUE}));
243 }
244
246 public Constraint addDifferent(IntVar left, IntVar right) {
247 return addLinearExpressionInDomain(new Difference(left, right),
248 Domain.fromFlatIntervals(new long[] {Long.MIN_VALUE, -1, 1, Long.MAX_VALUE}));
249 }
250
252 public Constraint addDifferentWithOffset(IntVar left, IntVar right, long offset) {
253 return addLinearExpressionInDomain(new Difference(left, right),
254 Domain.fromFlatIntervals(
255 new long[] {Long.MIN_VALUE, -offset - 1, -offset + 1, Long.MAX_VALUE}));
256 }
257
258 // Integer constraints.
259
268 public Constraint addAllDifferent(IntVar[] variables) {
269 Constraint ct = new Constraint(modelBuilder);
270 AllDifferentConstraintProto.Builder allDiff = ct.getBuilder().getAllDiffBuilder();
271 for (IntVar var : variables) {
272 allDiff.addVars(var.getIndex());
273 }
274 return ct;
275 }
276
278 public Constraint addElement(IntVar index, IntVar[] variables, IntVar target) {
279 Constraint ct = new Constraint(modelBuilder);
280 ElementConstraintProto.Builder element =
281 ct.getBuilder().getElementBuilder().setIndex(index.getIndex());
282 for (IntVar var : variables) {
283 element.addVars(var.getIndex());
284 }
285 element.setTarget(target.getIndex());
286 return ct;
287 }
288
290 public Constraint addElement(IntVar index, long[] values, IntVar target) {
291 Constraint ct = new Constraint(modelBuilder);
292 ElementConstraintProto.Builder element =
293 ct.getBuilder().getElementBuilder().setIndex(index.getIndex());
294 for (long v : values) {
295 element.addVars(indexFromConstant(v));
296 }
297 element.setTarget(target.getIndex());
298 return ct;
299 }
300
302 public Constraint addElement(IntVar index, int[] values, IntVar target) {
303 Constraint ct = new Constraint(modelBuilder);
304 ElementConstraintProto.Builder element =
305 ct.getBuilder().getElementBuilder().setIndex(index.getIndex());
306 for (long v : values) {
307 element.addVars(indexFromConstant(v));
308 }
309 element.setTarget(target.getIndex());
310 return ct;
311 }
312
328 public Constraint addCircuit(int[] tails, int[] heads, Literal[] literals) {
329 if (tails.length != heads.length) {
330 throw new MismatchedArrayLengths("CpModel.addCircuit", "tails", "heads");
331 }
332 if (tails.length != literals.length) {
333 throw new MismatchedArrayLengths("CpModel.addCircuit", "tails", "literals");
334 }
335
336 Constraint ct = new Constraint(modelBuilder);
337 CircuitConstraintProto.Builder circuit = ct.getBuilder().getCircuitBuilder();
338 for (int t : tails) {
339 circuit.addTails(t);
340 }
341 for (int h : heads) {
342 circuit.addHeads(h);
343 }
344 for (Literal lit : literals) {
345 circuit.addLiterals(lit.getIndex());
346 }
347 return ct;
348 }
349
363 public Constraint addAllowedAssignments(IntVar[] variables, long[][] tuplesList) {
364 Constraint ct = new Constraint(modelBuilder);
365 TableConstraintProto.Builder table = ct.getBuilder().getTableBuilder();
366 for (IntVar var : variables) {
367 table.addVars(var.getIndex());
368 }
369 int numVars = variables.length;
370 for (int t = 0; t < tuplesList.length; ++t) {
371 if (tuplesList[t].length != numVars) {
372 throw new WrongLength("CpModel.addAllowedAssignments",
373 "tuple " + t + " does not have the same length as the variables");
374 }
375 for (int i = 0; i < tuplesList[t].length; ++i) {
376 table.addValues(tuplesList[t][i]);
377 }
378 }
379 return ct;
380 }
381
387 public Constraint addAllowedAssignments(IntVar[] variables, int[][] tuplesList) {
388 Constraint ct = new Constraint(modelBuilder);
389 TableConstraintProto.Builder table = ct.getBuilder().getTableBuilder();
390 for (IntVar var : variables) {
391 table.addVars(var.getIndex());
392 }
393 int numVars = variables.length;
394 for (int t = 0; t < tuplesList.length; ++t) {
395 if (tuplesList[t].length != numVars) {
396 throw new WrongLength("CpModel.addAllowedAssignments",
397 "tuple " + t + " does not have the same length as the variables");
398 }
399 for (int i = 0; i < tuplesList[t].length; ++i) {
400 table.addValues(tuplesList[t][i]);
401 }
402 }
403 return ct;
404 }
405
418 public Constraint addForbiddenAssignments(IntVar[] variables, long[][] tuplesList) {
419 Constraint ct = addAllowedAssignments(variables, tuplesList);
420 // Reverse the flag.
421 ct.getBuilder().getTableBuilder().setNegated(true);
422 return ct;
423 }
424
430 public Constraint addForbiddenAssignments(IntVar[] variables, int[][] tuplesList) {
431 Constraint ct = addAllowedAssignments(variables, tuplesList);
432 // Reverse the flag.
433 ct.getBuilder().getTableBuilder().setNegated(true);
434 return ct;
435 }
436
469 IntVar[] transitionVariables, long startingState, long[] finalStates, long[][] transitions) {
470 Constraint ct = new Constraint(modelBuilder);
471 AutomatonConstraintProto.Builder automaton = ct.getBuilder().getAutomatonBuilder();
472 for (IntVar var : transitionVariables) {
473 automaton.addVars(var.getIndex());
474 }
475 automaton.setStartingState(startingState);
476 for (long c : finalStates) {
477 automaton.addFinalStates(c);
478 }
479 for (long[] t : transitions) {
480 if (t.length != 3) {
481 throw new WrongLength("CpModel.addAutomaton", "transition does not have length 3");
482 }
483 automaton.addTransitionTail(t[0]).addTransitionLabel(t[1]).addTransitionHead(t[2]);
484 }
485 return ct;
486 }
487
499 public Constraint addInverse(IntVar[] variables, IntVar[] inverseVariables) {
500 if (variables.length != inverseVariables.length) {
501 throw new MismatchedArrayLengths("CpModel.addInverse", "variables", "inverseVariables");
502 }
503 Constraint ct = new Constraint(modelBuilder);
504 InverseConstraintProto.Builder inverse = ct.getBuilder().getInverseBuilder();
505 for (IntVar var : variables) {
506 inverse.addFDirect(var.getIndex());
507 }
508 for (IntVar var : inverseVariables) {
509 inverse.addFInverse(var.getIndex());
510 }
511 return ct;
512 }
513
538 IntVar[] times, long[] demands, long minLevel, long maxLevel) {
539 if (times.length != demands.length) {
540 throw new MismatchedArrayLengths("CpModel.addReservoirConstraint", "times", "demands");
541 }
542 if (minLevel > 0) {
543 throw new IllegalArgumentException("CpModel.addReservoirConstraint: minLevel must be <= 0");
544 }
545 if (maxLevel < 0) {
546 throw new IllegalArgumentException("CpModel.addReservoirConstraint: maxLevel must be >= 0");
547 }
548 Constraint ct = new Constraint(modelBuilder);
549 ReservoirConstraintProto.Builder reservoir = ct.getBuilder().getReservoirBuilder();
550 for (IntVar var : times) {
551 reservoir.addTimes(var.getIndex());
552 }
553 for (long d : demands) {
554 reservoir.addDemands(d);
555 }
556 reservoir.setMinLevel(minLevel).setMaxLevel(maxLevel);
557 return ct;
558 }
559
566 IntVar[] times, int[] demands, long minLevel, long maxLevel) {
567 return addReservoirConstraint(times, toLongArray(demands), minLevel, maxLevel);
568 }
569
594 IntVar[] times, long[] demands, IntVar[] actives, long minLevel, long maxLevel) {
595 if (times.length != demands.length) {
596 throw new MismatchedArrayLengths(
597 "CpModel.addReservoirConstraintWithActive", "times", "demands");
598 }
599 if (times.length != actives.length) {
600 throw new MismatchedArrayLengths(
601 "CpModel.addReservoirConstraintWithActive", "times", "actives");
602 }
603 if (minLevel > 0) {
604 throw new IllegalArgumentException(
605 "CpModel.addReservoirConstraintWithActive: minLevel must be <= 0");
606 }
607 if (maxLevel < 0) {
608 throw new IllegalArgumentException(
609 "CpModel.addReservoirConstraintWithActive: maxLevel must be >= 0");
610 }
611
612 Constraint ct = new Constraint(modelBuilder);
613 ReservoirConstraintProto.Builder reservoir = ct.getBuilder().getReservoirBuilder();
614 for (IntVar var : times) {
615 reservoir.addTimes(var.getIndex());
616 }
617 for (long d : demands) {
618 reservoir.addDemands(d);
619 }
620 for (IntVar var : actives) {
621 reservoir.addActives(var.getIndex());
622 }
623 reservoir.setMinLevel(minLevel).setMaxLevel(maxLevel);
624 return ct;
625 }
626
633 IntVar[] times, int[] demands, IntVar[] actives, long minLevel, long maxLevel) {
635 times, toLongArray(demands), actives, minLevel, maxLevel);
636 }
637
639 public void addMapDomain(IntVar var, Literal[] booleans, long offset) {
640 for (int i = 0; i < booleans.length; ++i) {
641 addEquality(var, offset + i).onlyEnforceIf(booleans[i]);
642 addDifferent(var, offset + i).onlyEnforceIf(booleans[i].not());
643 }
644 }
645
647 public Constraint addMinEquality(IntVar target, IntVar[] vars) {
648 Constraint ct = new Constraint(modelBuilder);
649 IntegerArgumentProto.Builder intMin =
650 ct.getBuilder().getIntMinBuilder().setTarget(target.getIndex());
651 for (IntVar var : vars) {
652 intMin.addVars(var.getIndex());
653 }
654 return ct;
655 }
656
658 public Constraint addMaxEquality(IntVar target, IntVar[] vars) {
659 Constraint ct = new Constraint(modelBuilder);
660 IntegerArgumentProto.Builder intMax =
661 ct.getBuilder().getIntMaxBuilder().setTarget(target.getIndex());
662 for (IntVar var : vars) {
663 intMax.addVars(var.getIndex());
664 }
665 return ct;
666 }
667
669 public Constraint addDivisionEquality(IntVar target, IntVar num, IntVar denom) {
670 Constraint ct = new Constraint(modelBuilder);
671 ct.getBuilder()
672 .getIntDivBuilder()
673 .setTarget(target.getIndex())
674 .addVars(num.getIndex())
675 .addVars(denom.getIndex());
676 return ct;
677 }
678
681 Constraint ct = new Constraint(modelBuilder);
682 ct.getBuilder()
683 .getIntMaxBuilder()
684 .setTarget(target.getIndex())
685 .addVars(var.getIndex())
686 .addVars(-var.getIndex() - 1);
687 return ct;
688 }
689
692 Constraint ct = new Constraint(modelBuilder);
693 ct.getBuilder()
694 .getIntModBuilder()
695 .setTarget(target.getIndex())
696 .addVars(var.getIndex())
697 .addVars(mod.getIndex());
698 return ct;
699 }
700
702 public Constraint addModuloEquality(IntVar target, IntVar var, long mod) {
703 Constraint ct = new Constraint(modelBuilder);
704 ct.getBuilder()
705 .getIntModBuilder()
706 .setTarget(target.getIndex())
707 .addVars(var.getIndex())
708 .addVars(indexFromConstant(mod));
709 return ct;
710 }
711
714 Constraint ct = new Constraint(modelBuilder);
715 IntegerArgumentProto.Builder intProd =
716 ct.getBuilder().getIntProdBuilder().setTarget(target.getIndex());
717 for (IntVar var : vars) {
718 intProd.addVars(var.getIndex());
719 }
720 return ct;
721 }
722
723 // Scheduling support.
724
739 public IntervalVar newIntervalVar(IntVar start, IntVar size, IntVar end, String name) {
740 return new IntervalVar(modelBuilder, start.getIndex(), size.getIndex(), end.getIndex(), name);
741 }
742
748 public IntervalVar newIntervalVar(IntVar start, IntVar size, long end, String name) {
749 return new IntervalVar(
750 modelBuilder, start.getIndex(), size.getIndex(), indexFromConstant(end), name);
751 }
752
758 public IntervalVar newIntervalVar(IntVar start, long size, IntVar end, String name) {
759 return new IntervalVar(
760 modelBuilder, start.getIndex(), indexFromConstant(size), end.getIndex(), name);
761 }
762
768 public IntervalVar newIntervalVar(long start, IntVar size, IntVar end, String name) {
769 return new IntervalVar(
770 modelBuilder, indexFromConstant(start), size.getIndex(), end.getIndex(), name);
771 }
772
774 public IntervalVar newFixedInterval(long start, long size, String name) {
775 return new IntervalVar(modelBuilder, indexFromConstant(start), indexFromConstant(size),
776 indexFromConstant(start + size), name);
777 }
778
797 IntVar start, IntVar size, IntVar end, Literal isPresent, String name) {
798 return new IntervalVar(modelBuilder, start.getIndex(), size.getIndex(), end.getIndex(),
799 isPresent.getIndex(), name);
800 }
801
808 IntVar start, IntVar size, long end, Literal isPresent, String name) {
809 return new IntervalVar(modelBuilder, start.getIndex(), size.getIndex(), indexFromConstant(end),
810 isPresent.getIndex(), name);
811 }
812
819 IntVar start, long size, IntVar end, Literal isPresent, String name) {
820 return new IntervalVar(modelBuilder, start.getIndex(), indexFromConstant(size), end.getIndex(),
821 isPresent.getIndex(), name);
822 }
823
826 long start, IntVar size, IntVar end, Literal isPresent, String name) {
827 return new IntervalVar(modelBuilder, indexFromConstant(start), size.getIndex(), end.getIndex(),
828 isPresent.getIndex(), name);
829 }
830
837 long start, long size, Literal isPresent, String name) {
838 return new IntervalVar(modelBuilder, indexFromConstant(start), indexFromConstant(size),
839 indexFromConstant(start + size), isPresent.getIndex(), name);
840 }
841
850 public Constraint addNoOverlap(IntervalVar[] intervalVars) {
851 Constraint ct = new Constraint(modelBuilder);
852 NoOverlapConstraintProto.Builder noOverlap = ct.getBuilder().getNoOverlapBuilder();
853 for (IntervalVar var : intervalVars) {
854 noOverlap.addIntervals(var.getIndex());
855 }
856 return ct;
857 }
858
870 public Constraint addNoOverlap2D(IntervalVar[] xIntervals, IntervalVar[] yIntervals) {
871 Constraint ct = new Constraint(modelBuilder);
872 NoOverlap2DConstraintProto.Builder noOverlap2d = ct.getBuilder().getNoOverlap2DBuilder();
873 for (IntervalVar x : xIntervals) {
874 noOverlap2d.addXIntervals(x.getIndex());
875 }
876 for (IntervalVar y : yIntervals) {
877 noOverlap2d.addYIntervals(y.getIndex());
878 }
879 return ct;
880 }
881
897 public Constraint addCumulative(IntervalVar[] intervals, IntVar[] demands, IntVar capacity) {
898 Constraint ct = new Constraint(modelBuilder);
899 CumulativeConstraintProto.Builder cumul = ct.getBuilder().getCumulativeBuilder();
900 for (IntervalVar interval : intervals) {
901 cumul.addIntervals(interval.getIndex());
902 }
903 for (IntVar var : demands) {
904 cumul.addDemands(var.getIndex());
905 }
906 cumul.setCapacity(capacity.getIndex());
907 return ct;
908 }
909
915 public Constraint addCumulative(IntervalVar[] intervals, long[] demands, IntVar capacity) {
916 Constraint ct = new Constraint(modelBuilder);
917 CumulativeConstraintProto.Builder cumul = ct.getBuilder().getCumulativeBuilder();
918 for (IntervalVar interval : intervals) {
919 cumul.addIntervals(interval.getIndex());
920 }
921 for (long d : demands) {
922 cumul.addDemands(indexFromConstant(d));
923 }
924 cumul.setCapacity(capacity.getIndex());
925 return ct;
926 }
927
933 public Constraint addCumulative(IntervalVar[] intervals, int[] demands, IntVar capacity) {
934 return addCumulative(intervals, toLongArray(demands), capacity);
935 }
936
942 public Constraint addCumulative(IntervalVar[] intervals, IntVar[] demands, long capacity) {
943 Constraint ct = new Constraint(modelBuilder);
944 CumulativeConstraintProto.Builder cumul = ct.getBuilder().getCumulativeBuilder();
945 for (IntervalVar interval : intervals) {
946 cumul.addIntervals(interval.getIndex());
947 }
948 for (IntVar var : demands) {
949 cumul.addDemands(var.getIndex());
950 }
951 cumul.setCapacity(indexFromConstant(capacity));
952 return ct;
953 }
954
960 public Constraint addCumulative(IntervalVar[] intervals, long[] demands, long capacity) {
961 Constraint ct = new Constraint(modelBuilder);
962 CumulativeConstraintProto.Builder cumul = ct.getBuilder().getCumulativeBuilder();
963 for (IntervalVar interval : intervals) {
964 cumul.addIntervals(interval.getIndex());
965 }
966 for (long d : demands) {
967 cumul.addDemands(indexFromConstant(d));
968 }
969 cumul.setCapacity(indexFromConstant(capacity));
970 return ct;
971 }
972
978 public Constraint addCumulative(IntervalVar[] intervals, int[] demands, long capacity) {
979 return addCumulative(intervals, toLongArray(demands), capacity);
980 }
981
983 public void addHint(IntVar var, long value) {
984 modelBuilder.getSolutionHintBuilder().addVars(var.getIndex());
985 modelBuilder.getSolutionHintBuilder().addValues(value);
986 }
987
989 public void clearHints() {
990 modelBuilder.clearSolutionHint();
991 }
992
994 public void addAssumption(Literal lit) {
995 modelBuilder.addAssumptions(lit.getIndex());
996 }
997
999 public void addAssumptions(Literal[] literals) {
1000 for (Literal lit : literals) {
1001 addAssumption(lit);
1002 }
1003 }
1004
1006 public void clearAssumptions() {
1007 modelBuilder.clearAssumptions();
1008 }
1009
1010 // Objective.
1011
1013 public void minimize(LinearExpr expr) {
1014 CpObjectiveProto.Builder obj = modelBuilder.getObjectiveBuilder();
1015 for (int i = 0; i < expr.numElements(); ++i) {
1016 obj.addVars(expr.getVariable(i).getIndex()).addCoeffs(expr.getCoefficient(i));
1017 }
1018 obj.setOffset(expr.getOffset());
1019 }
1020
1022 public void maximize(LinearExpr expr) {
1023 CpObjectiveProto.Builder obj = modelBuilder.getObjectiveBuilder();
1024 for (int i = 0; i < expr.numElements(); ++i) {
1025 obj.addVars(expr.getVariable(i).getIndex()).addCoeffs(-expr.getCoefficient(i));
1026 }
1027 obj.setOffset(-expr.getOffset());
1028 obj.setScalingFactor(-1.0);
1029 }
1030
1031 // DecisionStrategy
1032
1034 public void addDecisionStrategy(IntVar[] variables,
1035 DecisionStrategyProto.VariableSelectionStrategy varStr,
1036 DecisionStrategyProto.DomainReductionStrategy domStr) {
1037 DecisionStrategyProto.Builder ds = modelBuilder.addSearchStrategyBuilder();
1038 for (IntVar var : variables) {
1039 ds.addVariables(var.getIndex());
1040 }
1041 ds.setVariableSelectionStrategy(varStr).setDomainReductionStrategy(domStr);
1042 }
1043
1045 public String modelStats() {
1046 return SatHelper.modelStats(model());
1047 }
1048
1050 public String validate() {
1051 return SatHelper.validateModel(model());
1052 }
1053
1055 public Boolean exportToFile(String file) {
1056 return SatHelper.writeModelToFile(model(), file);
1057 }
1058
1059 // Helpers
1060
1061 long[] toLongArray(int[] values) {
1062 long[] result = new long[values.length];
1063 for (int i = 0; i < values.length; ++i) {
1064 result[i] = values[i];
1065 }
1066 return result;
1067 }
1068
1069 int indexFromConstant(long constant) {
1070 int index = modelBuilder.getVariablesCount();
1071 modelBuilder.addVariablesBuilder().addDomain(constant).addDomain(constant);
1072 return index;
1073 }
1074
1075 // Getters.
1076
1077 public CpModelProto model() {
1078 return modelBuilder.build();
1079 }
1080
1081 public int negated(int index) {
1082 return -index - 1;
1083 }
1084
1086 public CpModelProto.Builder getBuilder() {
1087 return modelBuilder;
1088 }
1089
1090 private final CpModelProto.Builder modelBuilder;
1091 private final Map<Long, IntVar> constantMap;
1092}
Wrapper around a ConstraintProto.
Definition: Constraint.java:25
ConstraintProto.Builder getBuilder()
Returns the constraint builder.
Definition: Constraint.java:49
void onlyEnforceIf(Literal lit)
Adds a literal to the constraint.
Definition: Constraint.java:32
Exception thrown when parallel arrays have mismatched lengths.
Definition: CpModel.java:50
MismatchedArrayLengths(String methodName, String array1Name, String array2Name)
Definition: CpModel.java:51
Exception thrown when an array has a wrong length.
Definition: CpModel.java:57
WrongLength(String methodName, String msg)
Definition: CpModel.java:58
Main modeling class.
Definition: CpModel.java:41
Constraint addDifferent(IntVar left, IntVar right)
Adds left != right.
Definition: CpModel.java:246
Constraint addAllowedAssignments(IntVar[] variables, int[][] tuplesList)
Adds AllowedAssignments(variables, tuplesList).
Definition: CpModel.java:387
IntVar newConstant(long value)
Creates a constant variable.
Definition: CpModel.java:91
Constraint addCumulative(IntervalVar[] intervals, long[] demands, long capacity)
Adds Cumulative(intervals, demands, capacity) with fixed demands and fixed capacity.
Definition: CpModel.java:960
IntVar newBoolVar(String name)
Creates a Boolean variable with the given name.
Definition: CpModel.java:86
Constraint addDifferentWithOffset(IntVar left, IntVar right, long offset)
Adds left + offset != right.
Definition: CpModel.java:252
Constraint addGreaterOrEqual(LinearExpr expr, long value)
Adds expr >= value.
Definition: CpModel.java:213
Constraint addForbiddenAssignments(IntVar[] variables, int[][] tuplesList)
Adds ForbiddenAssignments(variables, tuplesList).
Definition: CpModel.java:430
void clearAssumptions()
Remove all assumptions from the model.
Definition: CpModel.java:1006
IntervalVar newOptionalIntervalVar(IntVar start, IntVar size, long end, Literal isPresent, String name)
Creates an optional interval with a fixed end.
Definition: CpModel.java:807
Constraint addReservoirConstraintWithActive(IntVar[] times, long[] demands, IntVar[] actives, long minLevel, long maxLevel)
Adds Reservoir(times, demands, actives, minLevel, maxLevel).
Definition: CpModel.java:593
Constraint addGreaterOrEqual(LinearExpr left, LinearExpr right)
Adds left >= right.
Definition: CpModel.java:218
Constraint addAutomaton(IntVar[] transitionVariables, long startingState, long[] finalStates, long[][] transitions)
Adds an automaton constraint.
Definition: CpModel.java:468
Constraint addModuloEquality(IntVar target, IntVar var, long mod)
Adds target == var % mod.
Definition: CpModel.java:702
Boolean exportToFile(String file)
Write the model as a ascii protocol buffer to 'file'.
Definition: CpModel.java:1055
Constraint addLessOrEqual(LinearExpr expr, long value)
Adds expr <= value.
Definition: CpModel.java:187
IntervalVar newOptionalFixedInterval(long start, long size, Literal isPresent, String name)
Creates an optional fixed interval from start and size.
Definition: CpModel.java:836
IntervalVar newIntervalVar(long start, IntVar size, IntVar end, String name)
Creates an interval variable with a fixed start.
Definition: CpModel.java:768
Constraint addLessThan(LinearExpr expr, long value)
Adds expr < value.
Definition: CpModel.java:197
Constraint addElement(IntVar index, long[] values, IntVar target)
Adds the element constraint: values[index] == target.
Definition: CpModel.java:290
Literal falseLiteral()
Returns the false literal.
Definition: CpModel.java:106
Constraint addLessOrEqualWithOffset(LinearExpr left, LinearExpr right, long offset)
Adds left + offset <= right.
Definition: CpModel.java:207
void addAssumptions(Literal[] literals)
Adds multiple literals to the model as assumptions.
Definition: CpModel.java:999
Constraint addEquality(LinearExpr left, LinearExpr right)
Adds left == right.
Definition: CpModel.java:177
IntervalVar newOptionalIntervalVar(long start, IntVar size, IntVar end, Literal isPresent, String name)
Creates an optional interval with a fixed start.
Definition: CpModel.java:825
IntervalVar newIntervalVar(IntVar start, long size, IntVar end, String name)
Creates an interval variable with a fixed size.
Definition: CpModel.java:758
void minimize(LinearExpr expr)
Adds a minimization objective of a linear expression.
Definition: CpModel.java:1013
Constraint addDivisionEquality(IntVar target, IntVar num, IntVar denom)
Adds target == num / denom, rounded towards 0.
Definition: CpModel.java:669
Constraint addReservoirConstraint(IntVar[] times, int[] demands, long minLevel, long maxLevel)
Adds Reservoir(times, demands, minLevel, maxLevel).
Definition: CpModel.java:565
Constraint addGreaterThan(LinearExpr expr, long value)
Adds expr > value.
Definition: CpModel.java:223
void addAssumption(Literal lit)
Adds a literal to the model as assumption.
Definition: CpModel.java:994
Constraint addProductEquality(IntVar target, IntVar[] vars)
Adds target == Product(vars).
Definition: CpModel.java:713
Constraint addReservoirConstraint(IntVar[] times, long[] demands, long minLevel, long maxLevel)
Adds Reservoir(times, demands, minLevel, maxLevel).
Definition: CpModel.java:537
void addHint(IntVar var, long value)
Adds hinting to a variable.
Definition: CpModel.java:983
Constraint addModuloEquality(IntVar target, IntVar var, IntVar mod)
Adds target == var % mod.
Definition: CpModel.java:691
IntervalVar newFixedInterval(long start, long size, String name)
Creates a fixed interval from its start and its size.
Definition: CpModel.java:774
Constraint addGreaterThan(LinearExpr left, LinearExpr right)
Adds left > right.
Definition: CpModel.java:228
IntervalVar newOptionalIntervalVar(IntVar start, IntVar size, IntVar end, Literal isPresent, String name)
Creates an optional interval variable from start, size, end, and isPresent.
Definition: CpModel.java:796
Constraint addCircuit(int[] tails, int[] heads, Literal[] literals)
Adds Circuit(tails, heads, literals).
Definition: CpModel.java:328
String modelStats()
Returns some statistics on model as a string.
Definition: CpModel.java:1045
Constraint addEqualityWithOffset(LinearExpr left, LinearExpr right, long offset)
Adds left + offset == right.
Definition: CpModel.java:182
Constraint addElement(IntVar index, IntVar[] variables, IntVar target)
Adds the element constraint: variables[index] == target.
Definition: CpModel.java:278
Constraint addAbsEquality(IntVar target, IntVar var)
Adds target == Abs(var).
Definition: CpModel.java:680
IntervalVar newIntervalVar(IntVar start, IntVar size, IntVar end, String name)
Creates an interval variable from start, size, and end.
Definition: CpModel.java:739
Constraint addAllowedAssignments(IntVar[] variables, long[][] tuplesList)
Adds AllowedAssignments(variables, tuplesList).
Definition: CpModel.java:363
IntervalVar newIntervalVar(IntVar start, IntVar size, long end, String name)
Creates an interval variable with a fixed end.
Definition: CpModel.java:748
Constraint addCumulative(IntervalVar[] intervals, int[] demands, IntVar capacity)
Adds Cumulative(intervals, demands, capacity) with fixed demands.
Definition: CpModel.java:933
Constraint addReservoirConstraintWithActive(IntVar[] times, int[] demands, IntVar[] actives, long minLevel, long maxLevel)
Adds Reservoir(times, demands, actives, minLevel, maxLevel).
Definition: CpModel.java:632
void maximize(LinearExpr expr)
Adds a maximization objective of a linear expression.
Definition: CpModel.java:1022
Constraint addAllDifferent(IntVar[] variables)
Adds AllDifferent(variables).
Definition: CpModel.java:268
Constraint addImplication(Literal a, Literal b)
Adds a => b.
Definition: CpModel.java:143
Constraint addBoolXor(Literal[] literals)
Adds XOr(literals) == true.
Definition: CpModel.java:133
Constraint addCumulative(IntervalVar[] intervals, IntVar[] demands, IntVar capacity)
Adds Cumulative(intervals, demands, capacity).
Definition: CpModel.java:897
Constraint addLessThan(LinearExpr left, LinearExpr right)
Adds left < right.
Definition: CpModel.java:202
Constraint addMinEquality(IntVar target, IntVar[] vars)
Adds target == Min(vars).
Definition: CpModel.java:647
Constraint addCumulative(IntervalVar[] intervals, IntVar[] demands, long capacity)
Adds Cumulative(intervals, demands, capacity) with fixed capacity.
Definition: CpModel.java:942
IntVar newIntVar(long lb, long ub, String name)
Creates an integer variable with domain [lb, ub].
Definition: CpModel.java:70
void addMapDomain(IntVar var, Literal[] booleans, long offset)
Adds var == i + offset <=> booleans[i] == true for all i in [0, booleans.length).
Definition: CpModel.java:639
void addDecisionStrategy(IntVar[] variables, DecisionStrategyProto.VariableSelectionStrategy varStr, DecisionStrategyProto.DomainReductionStrategy domStr)
Adds DecisionStrategy(variables, varStr, domStr).
Definition: CpModel.java:1034
Constraint addInverse(IntVar[] variables, IntVar[] inverseVariables)
Adds Inverse(variables, inverseVariables).
Definition: CpModel.java:499
Constraint addNoOverlap2D(IntervalVar[] xIntervals, IntervalVar[] yIntervals)
Adds NoOverlap2D(xIntervals, yIntervals).
Definition: CpModel.java:870
Constraint addLinearConstraint(LinearExpr expr, long lb, long ub)
Adds lb <= expr <= ub.
Definition: CpModel.java:167
Constraint addNoOverlap(IntervalVar[] intervalVars)
Adds NoOverlap(intervalVars).
Definition: CpModel.java:850
Literal trueLiteral()
Returns the true literal.
Definition: CpModel.java:101
Constraint addForbiddenAssignments(IntVar[] variables, long[][] tuplesList)
Adds ForbiddenAssignments(variables, tuplesList).
Definition: CpModel.java:418
Constraint addDifferent(LinearExpr expr, long value)
Adds expr != value.
Definition: CpModel.java:239
Constraint addElement(IntVar index, int[] values, IntVar target)
Adds the element constraint: values[index] == target.
Definition: CpModel.java:302
Constraint addEquality(LinearExpr expr, long value)
Adds expr == value.
Definition: CpModel.java:172
void clearHints()
Remove all solution hints.
Definition: CpModel.java:989
String validate()
Returns a non empty string explaining the issue if the model is invalid.
Definition: CpModel.java:1050
Constraint addGreaterOrEqualWithOffset(LinearExpr left, LinearExpr right, long offset)
Adds left + offset >= right.
Definition: CpModel.java:233
Constraint addMaxEquality(IntVar target, IntVar[] vars)
Adds target == Max(vars).
Definition: CpModel.java:658
Constraint addCumulative(IntervalVar[] intervals, int[] demands, long capacity)
Adds Cumulative(intervals, demands, capacity) with fixed demands and fixed capacity.
Definition: CpModel.java:978
Constraint addBoolOr(Literal[] literals)
Adds Or(literals) == true.
Definition: CpModel.java:113
IntVar newIntVarFromDomain(Domain domain, String name)
Creates an integer variable with given domain.
Definition: CpModel.java:81
Constraint addLinearExpressionInDomain(LinearExpr expr, Domain domain)
Adds expr in domain.
Definition: CpModel.java:150
Constraint addBoolAnd(Literal[] literals)
Adds And(literals) == true.
Definition: CpModel.java:123
IntervalVar newOptionalIntervalVar(IntVar start, long size, IntVar end, Literal isPresent, String name)
Creates an optional interval with a fixed size.
Definition: CpModel.java:818
Constraint addCumulative(IntervalVar[] intervals, long[] demands, IntVar capacity)
Adds Cumulative(intervals, demands, capacity) with fixed demands.
Definition: CpModel.java:915
Constraint addLessOrEqual(LinearExpr left, LinearExpr right)
Adds left <= right.
Definition: CpModel.java:192
CpModelProto.Builder getBuilder()
Returns the model builder.
Definition: CpModel.java:1086
An integer variable.
Definition: IntVar.java:21
int getIndex()
Internal, returns the index of the variable in the underlying CpModelProto.
Definition: IntVar.java:45
A linear expression interface that can be parsed.
Definition: LinearExpr.java:17
long getCoefficient(int index)
Returns the ith coefficient.
int numElements()
Returns the number of elements in the interface.
long getOffset()
Returns the constant part of the expression.
IntVar getVariable(int index)
Returns the ith variable.
Interface to describe a boolean variable or its negation.
Definition: Literal.java:17
Literal not()
Returns the Boolean negation of the current literal.