Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
CpModel.java
Go to the documentation of this file.
1// Copyright 2010-2025 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.CpModelProto;
20import com.google.ortools.sat.CpObjectiveProto;
21import com.google.ortools.sat.CumulativeConstraintProto;
22import com.google.ortools.sat.DecisionStrategyProto;
23import com.google.ortools.sat.ElementConstraintProto;
24import com.google.ortools.sat.FloatObjectiveProto;
25import com.google.ortools.sat.InverseConstraintProto;
26import com.google.ortools.sat.LinearArgumentProto;
27import com.google.ortools.sat.LinearConstraintProto;
28import com.google.ortools.sat.LinearExpressionProto;
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.Arrays;
34import java.util.LinkedHashMap;
35import java.util.Map;
36
42public final class CpModel {
43 static class CpModelException extends RuntimeException {
44 public CpModelException(String methodName, String msg) {
45 // Call constructor of parent Exception
46 super(methodName + ": " + msg);
47 }
48 }
49
51 public static class MismatchedArrayLengths extends CpModelException {
52 public MismatchedArrayLengths(String methodName, String array1Name, String array2Name) {
53 super(methodName, array1Name + " and " + array2Name + " have mismatched lengths");
54 }
55 }
56
58 public static class WrongLength extends CpModelException {
59 public WrongLength(String methodName, String msg) {
60 super(methodName, msg);
61 }
62 }
63
64 public CpModel() {
65 modelBuilder = CpModelProto.newBuilder();
66 constantMap = new LinkedHashMap<>();
67 }
68
69 public CpModel getClone() {
70 CpModel clone = new CpModel();
71 clone.modelBuilder.mergeFrom(modelBuilder.build());
72 clone.constantMap.clear();
73 clone.constantMap.putAll(constantMap);
74 return clone;
75 }
76
77 // Integer variables.
78
80 public IntVar newIntVar(long lb, long ub, String name) {
81 return new IntVar(modelBuilder, new Domain(lb, ub), name);
82 }
83
91 public IntVar newIntVarFromDomain(Domain domain, String name) {
92 return new IntVar(modelBuilder, domain, name);
93 }
94
96 public BoolVar newBoolVar(String name) {
97 return new BoolVar(modelBuilder, new Domain(0, 1), name);
98 }
99
101 public IntVar newConstant(long value) {
102 if (constantMap.containsKey(value)) {
103 return new IntVar(modelBuilder, constantMap.get(value));
104 }
105 IntVar cste = new IntVar(modelBuilder, new Domain(value), ""); // bounds and name.
106 constantMap.put(value, cste.getIndex());
107 return cste;
108 }
109
112 if (constantMap.containsKey(1L)) {
113 return new BoolVar(modelBuilder, constantMap.get(1L));
114 }
115 BoolVar cste = new BoolVar(modelBuilder, new Domain(1), ""); // bounds and name.
116 constantMap.put(1L, cste.getIndex());
117 return cste;
118 }
119
122 if (constantMap.containsKey(0L)) {
123 return new BoolVar(modelBuilder, constantMap.get(0L));
124 }
125 BoolVar cste = new BoolVar(modelBuilder, new Domain(0), ""); // bounds and name.
126 constantMap.put(0L, cste.getIndex());
127 return cste;
128 }
129
132 return new BoolVar(modelBuilder, index);
133 }
134
136 public IntVar getIntVarFromProtoIndex(int index) {
137 return new IntVar(modelBuilder, index);
138 }
139
140 // Boolean Constraints.
141
143 public Constraint addBoolOr(Literal[] literals) {
144 return addBoolOr(Arrays.asList(literals));
145 }
146
148 public Constraint addBoolOr(Iterable<Literal> literals) {
149 Constraint ct = new Constraint(modelBuilder);
150 BoolArgumentProto.Builder boolOr = ct.getBuilder().getBoolOrBuilder();
151 for (Literal lit : literals) {
152 boolOr.addLiterals(lit.getIndex());
153 }
154 return ct;
155 }
156
158 public Constraint addAtLeastOne(Literal[] literals) {
159 return addBoolOr(Arrays.asList(literals));
160 }
161
163 public Constraint addAtLeastOne(Iterable<Literal> literals) {
164 return addBoolOr(literals);
165 }
166
168 public Constraint addAtMostOne(Literal[] literals) {
169 return addAtMostOne(Arrays.asList(literals));
170 }
171
173 public Constraint addAtMostOne(Iterable<Literal> literals) {
174 Constraint ct = new Constraint(modelBuilder);
175 BoolArgumentProto.Builder atMostOne = ct.getBuilder().getAtMostOneBuilder();
176 for (Literal lit : literals) {
177 atMostOne.addLiterals(lit.getIndex());
178 }
179 return ct;
180 }
181
183 public Constraint addExactlyOne(Literal[] literals) {
184 return addExactlyOne(Arrays.asList(literals));
185 }
186
188 public Constraint addExactlyOne(Iterable<Literal> literals) {
189 Constraint ct = new Constraint(modelBuilder);
190 BoolArgumentProto.Builder exactlyOne = ct.getBuilder().getExactlyOneBuilder();
191 for (Literal lit : literals) {
192 exactlyOne.addLiterals(lit.getIndex());
193 }
194 return ct;
195 }
196
198 public Constraint addBoolAnd(Literal[] literals) {
199 return addBoolAnd(Arrays.asList(literals));
200 }
201
203 public Constraint addBoolAnd(Iterable<Literal> literals) {
204 Constraint ct = new Constraint(modelBuilder);
205 BoolArgumentProto.Builder boolAnd = ct.getBuilder().getBoolAndBuilder();
206 for (Literal lit : literals) {
207 boolAnd.addLiterals(lit.getIndex());
208 }
209 return ct;
210 }
211
213 public Constraint addBoolXor(Literal[] literals) {
214 return addBoolXor(Arrays.asList(literals));
215 }
216
218 public Constraint addBoolXor(Iterable<Literal> literals) {
219 Constraint ct = new Constraint(modelBuilder);
220 BoolArgumentProto.Builder boolXOr = ct.getBuilder().getBoolXorBuilder();
221 for (Literal lit : literals) {
222 boolXOr.addLiterals(lit.getIndex());
223 }
224 return ct;
225 }
226
229 return addBoolOr(new Literal[] {a.not(), b});
230 }
231
232 // Linear constraints.
233
236 Constraint ct = new Constraint(modelBuilder);
237 LinearConstraintProto.Builder lin = ct.getBuilder().getLinearBuilder();
238 final LinearExpr e = expr.build();
239 for (int i = 0; i < e.numElements(); ++i) {
240 lin.addVars(e.getVariableIndex(i)).addCoeffs(e.getCoefficient(i));
241 }
242 long offset = e.getOffset();
243 for (long b : domain.flattenedIntervals()) {
244 if (b == Long.MIN_VALUE || b == Long.MAX_VALUE) {
245 lin.addDomain(b);
246 } else {
247 lin.addDomain(b - offset);
248 }
249 }
250 return ct;
251 }
252
254 public Constraint addLinearConstraint(LinearArgument expr, long lb, long ub) {
255 return addLinearExpressionInDomain(expr, new Domain(lb, ub));
256 }
257
259 public Constraint addEquality(LinearArgument expr, long value) {
260 return addLinearExpressionInDomain(expr, new Domain(value));
261 }
262
266 difference.addTerm(left, 1);
267 difference.addTerm(right, -1);
268 return addLinearExpressionInDomain(difference, new Domain(0));
269 }
270
272 public Constraint addLessOrEqual(LinearArgument expr, long value) {
273 return addLinearExpressionInDomain(expr, new Domain(Long.MIN_VALUE, value));
274 }
275
279 difference.addTerm(left, 1);
280 difference.addTerm(right, -1);
281 return addLinearExpressionInDomain(difference, new Domain(Long.MIN_VALUE, 0));
282 }
283
285 public Constraint addLessThan(LinearArgument expr, long value) {
286 return addLinearExpressionInDomain(expr, new Domain(Long.MIN_VALUE, value - 1));
287 }
288
292 difference.addTerm(left, 1);
293 difference.addTerm(right, -1);
294 return addLinearExpressionInDomain(difference, new Domain(Long.MIN_VALUE, -1));
295 }
296
298 public Constraint addGreaterOrEqual(LinearArgument expr, long value) {
299 return addLinearExpressionInDomain(expr, new Domain(value, Long.MAX_VALUE));
300 }
301
305 difference.addTerm(left, 1);
306 difference.addTerm(right, -1);
307 return addLinearExpressionInDomain(difference, new Domain(0, Long.MAX_VALUE));
308 }
309
311 public Constraint addGreaterThan(LinearArgument expr, long value) {
312 return addLinearExpressionInDomain(expr, new Domain(value + 1, Long.MAX_VALUE));
313 }
314
318 difference.addTerm(left, 1);
319 difference.addTerm(right, -1);
320 return addLinearExpressionInDomain(difference, new Domain(1, Long.MAX_VALUE));
321 }
322
324 public Constraint addDifferent(LinearArgument expr, long value) {
325 return addLinearExpressionInDomain(expr,
327 new long[] {Long.MIN_VALUE, value - 1, value + 1, Long.MAX_VALUE}));
328 }
329
333 difference.addTerm(left, 1);
334 difference.addTerm(right, -1);
336 difference, Domain.fromFlatIntervals(new long[] {Long.MIN_VALUE, -1, 1, Long.MAX_VALUE}));
337 }
338
339 // Integer constraints.
340
350 return addAllDifferent(Arrays.asList(expressions));
351 }
352
358 public Constraint addAllDifferent(Iterable<? extends LinearArgument> expressions) {
359 Constraint ct = new Constraint(modelBuilder);
360 AllDifferentConstraintProto.Builder allDiff = ct.getBuilder().getAllDiffBuilder();
361 for (LinearArgument expr : expressions) {
362 allDiff.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(expr, /*negate=*/false));
363 }
364 return ct;
365 }
366
369 LinearArgument index, LinearArgument[] expressions, LinearArgument target) {
370 Constraint ct = new Constraint(modelBuilder);
371 ElementConstraintProto.Builder element = ct.getBuilder().getElementBuilder().setLinearIndex(
372 getLinearExpressionProtoBuilderFromLinearArgument(index, /* negate= */ false));
373 for (LinearArgument expr : expressions) {
374 element.addExprs(
375 getLinearExpressionProtoBuilderFromLinearArgument(expr, /* negate= */ false));
376 }
377 element.setLinearTarget(
378 getLinearExpressionProtoBuilderFromLinearArgument(target, /* negate= */ false));
379 return ct;
380 }
381
384 LinearArgument index, Iterable<? extends LinearArgument> expressions, LinearArgument target) {
385 Constraint ct = new Constraint(modelBuilder);
386 ElementConstraintProto.Builder element = ct.getBuilder().getElementBuilder().setLinearIndex(
387 getLinearExpressionProtoBuilderFromLinearArgument(index, /* negate= */ false));
388 for (LinearArgument expr : expressions) {
389 element.addExprs(
390 getLinearExpressionProtoBuilderFromLinearArgument(expr, /* negate= */ false));
391 }
392 element.setLinearTarget(
393 getLinearExpressionProtoBuilderFromLinearArgument(target, /* negate= */ false));
394 return ct;
395 }
396
398 public Constraint addElement(LinearArgument index, long[] values, LinearArgument target) {
399 Constraint ct = new Constraint(modelBuilder);
400 ElementConstraintProto.Builder element = ct.getBuilder().getElementBuilder().setLinearIndex(
401 getLinearExpressionProtoBuilderFromLinearArgument(index, /* negate= */ false));
402 for (long v : values) {
403 element.addExprs(LinearExpressionProto.newBuilder().setOffset(v));
404 }
405 element.setLinearTarget(
406 getLinearExpressionProtoBuilderFromLinearArgument(target, /* negate= */ false));
407 return ct;
408 }
409
411 public Constraint addElement(LinearArgument index, int[] values, LinearArgument target) {
412 Constraint ct = new Constraint(modelBuilder);
413 ElementConstraintProto.Builder element = ct.getBuilder().getElementBuilder().setLinearIndex(
414 getLinearExpressionProtoBuilderFromLinearArgument(index, /* negate= */ false));
415 for (long v : values) {
416 element.addExprs(LinearExpressionProto.newBuilder().setOffset(v));
417 }
418 element.setLinearTarget(
419 getLinearExpressionProtoBuilderFromLinearArgument(target, /* negate= */ false));
420 return ct;
421 }
422
433 return new CircuitConstraint(modelBuilder);
434 }
435
447 return new MultipleCircuitConstraint(modelBuilder);
448 }
449
462 return addAllowedAssignments(Arrays.asList(expressions));
463 }
464
470 public TableConstraint addAllowedAssignments(Iterable<? extends LinearArgument> expressions) {
471 TableConstraint ct = new TableConstraint(modelBuilder);
472 TableConstraintProto.Builder table = ct.getBuilder().getTableBuilder();
473 for (LinearArgument expr : expressions) {
474 table.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(expr, /* negate= */ false));
475 }
476 table.setNegated(false);
477 return ct;
478 }
479
491 return addForbiddenAssignments(Arrays.asList(expressions));
492 }
493
499 public TableConstraint addForbiddenAssignments(Iterable<? extends LinearArgument> expressions) {
500 TableConstraint ct = new TableConstraint(modelBuilder);
501 TableConstraintProto.Builder table = ct.getBuilder().getTableBuilder();
502 for (LinearArgument expr : expressions) {
503 table.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(expr, /* negate= */ false));
504 }
505 table.setNegated(true);
506 return ct;
507 }
508
540 LinearArgument[] transitionExpressions, long startingState, long[] finalStates) {
541 AutomatonConstraint ct = new AutomatonConstraint(modelBuilder);
542 AutomatonConstraintProto.Builder automaton = ct.getBuilder().getAutomatonBuilder();
543 for (LinearArgument expr : transitionExpressions) {
544 automaton.addExprs(
545 getLinearExpressionProtoBuilderFromLinearArgument(expr, /* negate= */ false));
546 }
547 automaton.setStartingState(startingState);
548 for (long c : finalStates) {
549 automaton.addFinalStates(c);
550 }
551 return ct;
552 }
553
560 public AutomatonConstraint addAutomaton(Iterable<? extends LinearArgument> transitionExpressions,
561 long startingState, long[] finalStates) {
562 AutomatonConstraint ct = new AutomatonConstraint(modelBuilder);
563 AutomatonConstraintProto.Builder automaton = ct.getBuilder().getAutomatonBuilder();
564 for (LinearArgument expr : transitionExpressions) {
565 automaton.addExprs(
566 getLinearExpressionProtoBuilderFromLinearArgument(expr, /* negate= */ false));
567 }
568 automaton.setStartingState(startingState);
569 for (long c : finalStates) {
570 automaton.addFinalStates(c);
571 }
572 return ct;
573 }
574
586 public Constraint addInverse(IntVar[] variables, IntVar[] inverseVariables) {
587 if (variables.length != inverseVariables.length) {
588 throw new MismatchedArrayLengths("CpModel.addInverse", "variables", "inverseVariables");
589 }
590 Constraint ct = new Constraint(modelBuilder);
591 InverseConstraintProto.Builder inverse = ct.getBuilder().getInverseBuilder();
592 for (IntVar var : variables) {
593 inverse.addFDirect(var.getIndex());
594 }
595 for (IntVar var : inverseVariables) {
596 inverse.addFInverse(var.getIndex());
597 }
598 return ct;
599 }
600
624 public ReservoirConstraint addReservoirConstraint(long minLevel, long maxLevel) {
625 if (minLevel > 0) {
626 throw new IllegalArgumentException("CpModel.addReservoirConstraint: minLevel must be <= 0");
627 }
628 if (maxLevel < 0) {
629 throw new IllegalArgumentException("CpModel.addReservoirConstraint: maxLevel must be >= 0");
630 }
632 ReservoirConstraintProto.Builder reservoir = ct.getBuilder().getReservoirBuilder();
633 reservoir.setMinLevel(minLevel).setMaxLevel(maxLevel);
634 return ct;
635 }
636
638 public void addMapDomain(IntVar var, Literal[] booleans, long offset) {
639 for (int i = 0; i < booleans.length; ++i) {
640 addEquality(var, offset + i).onlyEnforceIf(booleans[i]);
641 addDifferent(var, offset + i).onlyEnforceIf(booleans[i].not());
642 }
643 }
644
647 Constraint ct = new Constraint(modelBuilder);
648 LinearArgumentProto.Builder linMax = ct.getBuilder().getLinMaxBuilder();
649 linMax.setTarget(getLinearExpressionProtoBuilderFromLinearArgument(target, /*negate=*/true));
650 for (LinearArgument expr : exprs) {
651 linMax.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(expr, /*negate=*/true));
652 }
653 return ct;
654 }
655
658 LinearArgument target, Iterable<? extends LinearArgument> exprs) {
659 Constraint ct = new Constraint(modelBuilder);
660 LinearArgumentProto.Builder linMax = ct.getBuilder().getLinMaxBuilder();
661 linMax.setTarget(getLinearExpressionProtoBuilderFromLinearArgument(target, /*negate=*/true));
662 for (LinearArgument expr : exprs) {
663 linMax.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(expr, /*negate=*/true));
664 }
665 return ct;
666 }
667
670 Constraint ct = new Constraint(modelBuilder);
671 LinearArgumentProto.Builder linMax = ct.getBuilder().getLinMaxBuilder();
672 linMax.setTarget(getLinearExpressionProtoBuilderFromLinearArgument(target, /*negate=*/false));
673 for (LinearArgument expr : exprs) {
674 linMax.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(expr, /*negate=*/false));
675 }
676 return ct;
677 }
678
681 LinearArgument target, Iterable<? extends LinearArgument> exprs) {
682 Constraint ct = new Constraint(modelBuilder);
683 LinearArgumentProto.Builder linMax = ct.getBuilder().getLinMaxBuilder();
684 linMax.setTarget(getLinearExpressionProtoBuilderFromLinearArgument(target, /*negate=*/false));
685 for (LinearArgument expr : exprs) {
686 linMax.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(expr, /*negate=*/false));
687 }
688 return ct;
689 }
690
693 LinearArgument target, LinearArgument num, LinearArgument denom) {
694 Constraint ct = new Constraint(modelBuilder);
695 ct.getBuilder()
696 .getIntDivBuilder()
697 .setTarget(getLinearExpressionProtoBuilderFromLinearArgument(target, /*negate=*/false))
698 .addExprs(getLinearExpressionProtoBuilderFromLinearArgument(num, /*negate=*/false))
699 .addExprs(getLinearExpressionProtoBuilderFromLinearArgument(denom, /*negate=*/false));
700 return ct;
701 }
702
705 Constraint ct = new Constraint(modelBuilder);
706 LinearArgumentProto.Builder linMax = ct.getBuilder().getLinMaxBuilder();
707 linMax.setTarget(getLinearExpressionProtoBuilderFromLinearArgument(target, /*negate=*/false));
708 linMax.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(expr, /*negate=*/false));
709 linMax.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(expr, /*negate=*/true));
710 return ct;
711 }
712
716 Constraint ct = new Constraint(modelBuilder);
717 ct.getBuilder()
718 .getIntModBuilder()
719 .setTarget(getLinearExpressionProtoBuilderFromLinearArgument(target, /*negate=*/false))
720 .addExprs(getLinearExpressionProtoBuilderFromLinearArgument(var, /*negate=*/false))
721 .addExprs(getLinearExpressionProtoBuilderFromLinearArgument(mod, /*negate=*/false));
722 return ct;
723 }
724
727 Constraint ct = new Constraint(modelBuilder);
728 ct.getBuilder()
729 .getIntModBuilder()
730 .setTarget(getLinearExpressionProtoBuilderFromLinearArgument(target, /*negate=*/false))
731 .addExprs(getLinearExpressionProtoBuilderFromLinearArgument(var, /*negate=*/false))
732 .addExprs(getLinearExpressionProtoBuilderFromLong(mod));
733 return ct;
734 }
735
738 Constraint ct = new Constraint(modelBuilder);
739 LinearArgumentProto.Builder intProd = ct.getBuilder().getIntProdBuilder();
740 intProd.setTarget(getLinearExpressionProtoBuilderFromLinearArgument(target, /*negate=*/false));
741 for (LinearArgument expr : exprs) {
742 intProd.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(expr, /*negate=*/false));
743 }
744 return ct;
745 }
746
749 LinearArgument target, LinearArgument left, LinearArgument right) {
750 Constraint ct = new Constraint(modelBuilder);
751 LinearArgumentProto.Builder intProd = ct.getBuilder().getIntProdBuilder();
752 intProd.setTarget(getLinearExpressionProtoBuilderFromLinearArgument(target, /*negate=*/false));
753 intProd.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(left, /*negate=*/false));
754 intProd.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(right, /*negate=*/false));
755 return ct;
756 }
757
758 // Scheduling support.
759
775 LinearArgument start, LinearArgument size, LinearArgument end, String name) {
776 return new IntervalVar(modelBuilder,
777 getLinearExpressionProtoBuilderFromLinearArgument(start, /*negate=*/false),
778 getLinearExpressionProtoBuilderFromLinearArgument(size, /*negate=*/false),
779 getLinearExpressionProtoBuilderFromLinearArgument(end, /*negate=*/false), name);
780 }
781
793 public IntervalVar newFixedSizeIntervalVar(LinearArgument start, long size, String name) {
794 return new IntervalVar(modelBuilder,
795 getLinearExpressionProtoBuilderFromLinearArgument(start, /*negate=*/false),
796 getLinearExpressionProtoBuilderFromLong(size),
797 getLinearExpressionProtoBuilderFromLinearArgument(
798 LinearExpr.newBuilder().add(start).add(size), /*negate=*/false),
799 name);
800 }
801
803 public IntervalVar newFixedInterval(long start, long size, String name) {
804 return new IntervalVar(modelBuilder, getLinearExpressionProtoBuilderFromLong(start),
805 getLinearExpressionProtoBuilderFromLong(size),
806 getLinearExpressionProtoBuilderFromLong(start + size), name);
807 }
808
828 LinearArgument end, Literal isPresent, String name) {
829 return new IntervalVar(modelBuilder,
830 getLinearExpressionProtoBuilderFromLinearArgument(start, /*negate=*/false),
831 getLinearExpressionProtoBuilderFromLinearArgument(size, /*negate=*/false),
832 getLinearExpressionProtoBuilderFromLinearArgument(end, /*negate=*/false),
833 isPresent.getIndex(), name);
834 }
835
850 LinearArgument start, long size, Literal isPresent, String name) {
851 return new IntervalVar(modelBuilder,
852 getLinearExpressionProtoBuilderFromLinearArgument(start, /*negate=*/false),
853 getLinearExpressionProtoBuilderFromLong(size),
854 getLinearExpressionProtoBuilderFromLinearArgument(
855 LinearExpr.newBuilder().add(start).add(size), /*negate=*/false),
856 isPresent.getIndex(), name);
857 }
858
861 long start, long size, Literal isPresent, String name) {
862 return new IntervalVar(modelBuilder, getLinearExpressionProtoBuilderFromLong(start),
863 getLinearExpressionProtoBuilderFromLong(size),
864 getLinearExpressionProtoBuilderFromLong(start + size), isPresent.getIndex(), name);
865 }
866
875 public Constraint addNoOverlap(IntervalVar[] intervalVars) {
876 return addNoOverlap(Arrays.asList(intervalVars));
877 }
878
884 public Constraint addNoOverlap(Iterable<IntervalVar> intervalVars) {
885 Constraint ct = new Constraint(modelBuilder);
886 NoOverlapConstraintProto.Builder noOverlap = ct.getBuilder().getNoOverlapBuilder();
887 for (IntervalVar var : intervalVars) {
888 noOverlap.addIntervals(var.getIndex());
889 }
890 return ct;
891 }
892
906 return new NoOverlap2dConstraint(modelBuilder);
907 }
908
924 CumulativeConstraintProto.Builder cumul = ct.getBuilder().getCumulativeBuilder();
925 cumul.setCapacity(getLinearExpressionProtoBuilderFromLinearArgument(capacity, false));
926 return ct;
927 }
928
934 public CumulativeConstraint addCumulative(long capacity) {
936 CumulativeConstraintProto.Builder cumul = ct.getBuilder().getCumulativeBuilder();
937 cumul.setCapacity(getLinearExpressionProtoBuilderFromLong(capacity));
938 return ct;
939 }
940
942 public void addHint(IntVar var, long value) {
943 modelBuilder.getSolutionHintBuilder().addVars(var.getIndex());
944 modelBuilder.getSolutionHintBuilder().addValues(value);
945 }
946
948 public void addHint(Literal lit, boolean value) {
949 if (isPositive(lit)) {
950 modelBuilder.getSolutionHintBuilder().addVars(lit.getIndex());
951 modelBuilder.getSolutionHintBuilder().addValues(value ? 1 : 0);
952 } else {
953 modelBuilder.getSolutionHintBuilder().addVars(negated(lit.getIndex()));
954 modelBuilder.getSolutionHintBuilder().addValues(value ? 0 : 1);
955 }
956 }
957
959 public void clearHints() {
960 modelBuilder.clearSolutionHint();
961 }
962
964 public void addAssumption(Literal lit) {
965 modelBuilder.addAssumptions(lit.getIndex());
966 }
967
969 public void addAssumptions(Literal[] literals) {
970 for (Literal lit : literals) {
971 addAssumption(lit);
972 }
973 }
974
976 public void clearAssumptions() {
977 modelBuilder.clearAssumptions();
978 }
979
980 // Objective.
981
983 public void minimize(LinearArgument expr) {
985 CpObjectiveProto.Builder obj = modelBuilder.getObjectiveBuilder();
986 final LinearExpr e = expr.build();
987 for (int i = 0; i < e.numElements(); ++i) {
988 obj.addVars(e.getVariableIndex(i)).addCoeffs(e.getCoefficient(i));
989 }
990 obj.setOffset((double) e.getOffset());
991 }
992
994 public void minimize(DoubleLinearExpr expr) {
996 FloatObjectiveProto.Builder obj = modelBuilder.getFloatingPointObjectiveBuilder();
997 for (int i = 0; i < expr.numElements(); ++i) {
998 obj.addVars(expr.getVariableIndex(i)).addCoeffs(expr.getCoefficient(i));
999 }
1000 obj.setOffset(expr.getOffset()).setMaximize(false);
1001 }
1002
1004 public void maximize(LinearArgument expr) {
1006 CpObjectiveProto.Builder obj = modelBuilder.getObjectiveBuilder();
1007 final LinearExpr e = expr.build();
1008 for (int i = 0; i < e.numElements(); ++i) {
1009 obj.addVars(e.getVariableIndex(i)).addCoeffs(-e.getCoefficient(i));
1010 }
1011 obj.setOffset((double) -e.getOffset());
1012 obj.setScalingFactor(-1.0);
1013 }
1014
1016 public void maximize(DoubleLinearExpr expr) {
1018 FloatObjectiveProto.Builder obj = modelBuilder.getFloatingPointObjectiveBuilder();
1019 for (int i = 0; i < expr.numElements(); ++i) {
1020 obj.addVars(expr.getVariableIndex(i)).addCoeffs(expr.getCoefficient(i));
1021 }
1022 obj.setOffset(expr.getOffset()).setMaximize(true);
1023 }
1024
1026 public void clearObjective() {
1027 modelBuilder.clearObjective();
1028 modelBuilder.clearFloatingPointObjective();
1029 }
1030
1032 public boolean hasObjective() {
1033 return modelBuilder.hasObjective() || modelBuilder.hasFloatingPointObjective();
1034 }
1035
1036 // DecisionStrategy
1037
1039 public void addDecisionStrategy(LinearArgument[] expressions,
1042 DecisionStrategyProto.Builder ds = modelBuilder.addSearchStrategyBuilder();
1043 for (LinearArgument arg : expressions) {
1044 ds.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(arg, /* negate= */ false));
1045 }
1047 }
1048
1050 public void addDecisionStrategy(Iterable<? extends LinearArgument> expressions,
1053 DecisionStrategyProto.Builder ds = modelBuilder.addSearchStrategyBuilder();
1054 for (LinearArgument arg : expressions) {
1055 ds.addExprs(getLinearExpressionProtoBuilderFromLinearArgument(arg, /* negate= */ false));
1056 }
1058 }
1059
1061 public String modelStats() {
1062 return CpSatHelper.modelStats(model());
1063 }
1064
1066 public String validate() {
1068 }
1069
1078 public Boolean exportToFile(String file) {
1079 return CpSatHelper.writeModelToFile(model(), file);
1080 }
1081
1082 // Helpers
1083 LinearExpressionProto.Builder getLinearExpressionProtoBuilderFromLinearArgument(
1084 LinearArgument arg, boolean negate) {
1086 final LinearExpr expr = arg.build();
1087 final int numVariables = expr.numElements();
1088 final long mult = negate ? -1 : 1;
1089 for (int i = 0; i < numVariables; ++i) {
1090 builder.addVars(expr.getVariableIndex(i));
1091 builder.addCoeffs(expr.getCoefficient(i) * mult);
1092 }
1093 builder.setOffset(expr.getOffset() * mult);
1094 return builder;
1095 }
1096
1097 LinearExpressionProto.Builder getLinearExpressionProtoBuilderFromLong(long value) {
1098 LinearExpressionProto.Builder builder = LinearExpressionProto.newBuilder();
1099 builder.setOffset(value);
1100 return builder;
1101 }
1102
1103 // Getters.
1104
1106 return modelBuilder.build();
1107 }
1108
1109 public int negated(int index) {
1110 return -index - 1;
1111 }
1112
1113 public boolean isPositive(Literal lit) {
1114 return lit.getIndex() >= 0;
1115 }
1116
1119 return modelBuilder;
1120 }
1121
1122 private final CpModelProto.Builder modelBuilder;
1123 private final Map<Long, Integer> constantMap;
1124}
ConstraintProto.Builder getBuilder()
MismatchedArrayLengths(String methodName, String array1Name, String array2Name)
Definition CpModel.java:52
WrongLength(String methodName, String msg)
Definition CpModel.java:59
Constraint addDifferent(LinearArgument left, LinearArgument right)
Definition CpModel.java:331
TableConstraint addForbiddenAssignments(Iterable<? extends LinearArgument > expressions)
Definition CpModel.java:499
TableConstraint addAllowedAssignments(Iterable<? extends LinearArgument > expressions)
Definition CpModel.java:470
IntVar newConstant(long value)
Definition CpModel.java:101
Constraint addAtMostOne(Iterable< Literal > literals)
Definition CpModel.java:173
BoolVar newBoolVar(String name)
Definition CpModel.java:96
Constraint addMinEquality(LinearArgument target, Iterable<? extends LinearArgument > exprs)
Definition CpModel.java:657
void addDecisionStrategy(LinearArgument[] expressions, DecisionStrategyProto.VariableSelectionStrategy varStr, DecisionStrategyProto.DomainReductionStrategy domStr)
DecisionStrategy.
ReservoirConstraint addReservoirConstraint(long minLevel, long maxLevel)
Definition CpModel.java:624
IntervalVar newOptionalIntervalVar(LinearArgument start, LinearArgument size, LinearArgument end, Literal isPresent, String name)
Definition CpModel.java:827
Constraint addBoolAnd(Literal[] literals)
Definition CpModel.java:198
Constraint addDivisionEquality(LinearArgument target, LinearArgument num, LinearArgument denom)
Definition CpModel.java:692
CpModelProto model()
Getters.
Constraint addDifferent(LinearArgument expr, long value)
Definition CpModel.java:324
Constraint addModuloEquality(LinearArgument target, LinearArgument var, LinearArgument mod)
Definition CpModel.java:714
Constraint addMaxEquality(LinearArgument target, LinearArgument[] exprs)
Definition CpModel.java:669
Constraint addAbsEquality(LinearArgument target, LinearArgument expr)
Definition CpModel.java:704
Constraint addBoolOr(Iterable< Literal > literals)
Definition CpModel.java:148
IntervalVar newOptionalFixedSizeIntervalVar(LinearArgument start, long size, Literal isPresent, String name)
Definition CpModel.java:849
CumulativeConstraint addCumulative(long capacity)
Definition CpModel.java:934
NoOverlap2dConstraint addNoOverlap2D()
Definition CpModel.java:905
AutomatonConstraint addAutomaton(LinearArgument[] transitionExpressions, long startingState, long[] finalStates)
Definition CpModel.java:539
Boolean exportToFile(String file)
TableConstraint addAllowedAssignments(LinearArgument[] expressions)
Definition CpModel.java:461
Constraint addElement(LinearArgument index, long[] values, LinearArgument target)
Definition CpModel.java:398
Constraint addAtLeastOne(Literal[] literals)
Definition CpModel.java:158
Constraint addLinearConstraint(LinearArgument expr, long lb, long ub)
Definition CpModel.java:254
TableConstraint addForbiddenAssignments(LinearArgument[] expressions)
Definition CpModel.java:490
MultipleCircuitConstraint addMultipleCircuit()
Definition CpModel.java:446
IntVar newIntVarFromDomain(Domain domain, String name)
Definition CpModel.java:91
AutomatonConstraint addAutomaton(Iterable<? extends LinearArgument > transitionExpressions, long startingState, long[] finalStates)
Definition CpModel.java:560
CircuitConstraint addCircuit()
Definition CpModel.java:432
Constraint addGreaterOrEqual(LinearArgument expr, long value)
Definition CpModel.java:298
IntervalVar newOptionalFixedInterval(long start, long size, Literal isPresent, String name)
Definition CpModel.java:860
Constraint addElement(LinearArgument index, int[] values, LinearArgument target)
Definition CpModel.java:411
Constraint addMultiplicationEquality(LinearArgument target, LinearArgument left, LinearArgument right)
Definition CpModel.java:748
Constraint addEquality(LinearArgument left, LinearArgument right)
Definition CpModel.java:264
Constraint addMaxEquality(LinearArgument target, Iterable<? extends LinearArgument > exprs)
Definition CpModel.java:680
Constraint addBoolAnd(Iterable< Literal > literals)
Definition CpModel.java:203
void minimize(LinearArgument expr)
Objective.
Definition CpModel.java:983
Constraint addLessOrEqual(LinearArgument left, LinearArgument right)
Definition CpModel.java:277
Constraint addEquality(LinearArgument expr, long value)
Definition CpModel.java:259
Constraint addNoOverlap(Iterable< IntervalVar > intervalVars)
Definition CpModel.java:884
void addAssumptions(Literal[] literals)
Definition CpModel.java:969
IntVar newIntVar(long lb, long ub, String name)
Integer variables.
Definition CpModel.java:80
Constraint addExactlyOne(Literal[] literals)
Definition CpModel.java:183
Constraint addAtLeastOne(Iterable< Literal > literals)
Definition CpModel.java:163
Constraint addElement(LinearArgument index, Iterable<? extends LinearArgument > expressions, LinearArgument target)
Definition CpModel.java:383
Constraint addLessOrEqual(LinearArgument expr, long value)
Definition CpModel.java:272
IntervalVar newFixedSizeIntervalVar(LinearArgument start, long size, String name)
Definition CpModel.java:793
Constraint addLessThan(LinearArgument expr, long value)
Definition CpModel.java:285
BoolVar getBoolVarFromProtoIndex(int index)
Definition CpModel.java:131
Constraint addGreaterOrEqual(LinearArgument left, LinearArgument right)
Definition CpModel.java:303
Constraint addMinEquality(LinearArgument target, LinearArgument[] exprs)
Definition CpModel.java:646
Constraint addLessThan(LinearArgument left, LinearArgument right)
Definition CpModel.java:290
CumulativeConstraint addCumulative(LinearArgument capacity)
Definition CpModel.java:922
Constraint addBoolXor(Iterable< Literal > literals)
Definition CpModel.java:218
Constraint addModuloEquality(LinearArgument target, LinearArgument var, long mod)
Definition CpModel.java:726
Constraint addGreaterThan(LinearArgument left, LinearArgument right)
Definition CpModel.java:316
void addMapDomain(IntVar var, Literal[] booleans, long offset)
Definition CpModel.java:638
void addDecisionStrategy(Iterable<? extends LinearArgument > expressions, DecisionStrategyProto.VariableSelectionStrategy varStr, DecisionStrategyProto.DomainReductionStrategy domStr)
Constraint addAllDifferent(LinearArgument[] expressions)
Integer constraints.
Definition CpModel.java:349
Constraint addNoOverlap(IntervalVar[] intervalVars)
Definition CpModel.java:875
void maximize(DoubleLinearExpr expr)
Constraint addBoolXor(Literal[] literals)
Definition CpModel.java:213
IntervalVar newFixedInterval(long start, long size, String name)
Definition CpModel.java:803
void maximize(LinearArgument expr)
Constraint addAllDifferent(Iterable<? extends LinearArgument > expressions)
Definition CpModel.java:358
Constraint addExactlyOne(Iterable< Literal > literals)
Definition CpModel.java:188
Constraint addInverse(IntVar[] variables, IntVar[] inverseVariables)
Definition CpModel.java:586
Constraint addElement(LinearArgument index, LinearArgument[] expressions, LinearArgument target)
Definition CpModel.java:368
Constraint addAtMostOne(Literal[] literals)
Definition CpModel.java:168
boolean isPositive(Literal lit)
IntVar getIntVarFromProtoIndex(int index)
Definition CpModel.java:136
Constraint addImplication(Literal a, Literal b)
Definition CpModel.java:228
void minimize(DoubleLinearExpr expr)
Definition CpModel.java:994
Constraint addLinearExpressionInDomain(LinearArgument expr, Domain domain)
Linear constraints.
Definition CpModel.java:235
Constraint addGreaterThan(LinearArgument expr, long value)
Definition CpModel.java:311
void addHint(Literal lit, boolean value)
Definition CpModel.java:948
Constraint addMultiplicationEquality(LinearArgument target, LinearArgument[] exprs)
Definition CpModel.java:737
void addAssumption(Literal lit)
Definition CpModel.java:964
CpModelProto.Builder getBuilder()
void addHint(IntVar var, long value)
Definition CpModel.java:942
Constraint addBoolOr(Literal[] literals)
Boolean Constraints.
Definition CpModel.java:143
IntervalVar newIntervalVar(LinearArgument start, LinearArgument size, LinearArgument end, String name)
Scheduling support.
Definition CpModel.java:774
static String validateModel(com.google.ortools.sat.CpModelProto model_proto)
static boolean writeModelToFile(com.google.ortools.sat.CpModelProto model_proto, String filename)
static String modelStats(com.google.ortools.sat.CpModelProto model_proto)
Builder setVariableSelectionStrategy(com.google.ortools.sat.DecisionStrategyProto.VariableSelectionStrategy value)
Builder setDomainReductionStrategy(com.google.ortools.sat.DecisionStrategyProto.DomainReductionStrategy value)
LinearExprBuilder add(LinearArgument expr)
LinearExprBuilder addTerm(LinearArgument expr, long coeff)
static Domain fromFlatIntervals(long[] flat_intervals)
Definition Domain.java:121
static LinearExprBuilder newBuilder()