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 
14 package com.google.ortools.sat;
15 
16 import com.google.ortools.sat.AllDifferentConstraintProto;
17 import com.google.ortools.sat.AutomatonConstraintProto;
18 import com.google.ortools.sat.BoolArgumentProto;
19 import com.google.ortools.sat.CircuitConstraintProto;
20 import com.google.ortools.sat.CpModelProto;
21 import com.google.ortools.sat.CpObjectiveProto;
22 import com.google.ortools.sat.CumulativeConstraintProto;
23 import com.google.ortools.sat.DecisionStrategyProto;
24 import com.google.ortools.sat.ElementConstraintProto;
25 import com.google.ortools.sat.IntegerArgumentProto;
26 import com.google.ortools.sat.InverseConstraintProto;
27 import com.google.ortools.sat.LinearConstraintProto;
28 import com.google.ortools.sat.NoOverlap2DConstraintProto;
29 import com.google.ortools.sat.NoOverlapConstraintProto;
30 import com.google.ortools.sat.ReservoirConstraintProto;
31 import com.google.ortools.sat.TableConstraintProto;
32 import com.google.ortools.util.Domain;
33 import java.util.LinkedHashMap;
34 import java.util.Map;
35 
41 public 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 
101  public Literal trueLiteral() {
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 
150  public Constraint addLinearExpressionInDomain(LinearExpr expr, Domain domain) {
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 
233  public Constraint addGreaterOrEqualWithOffset(LinearExpr left, LinearExpr right, long offset) {
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 
680  public Constraint addAbsEquality(IntVar target, IntVar var) {
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 
691  public Constraint addModuloEquality(IntVar target, IntVar var, IntVar mod) {
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 
713  public Constraint addProductEquality(IntVar target, IntVar[] vars) {
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.
Definition: CpModel.java:246
Constraint addAllowedAssignments(IntVar[] variables, int[][] tuplesList)
Adds.
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.
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.
Definition: CpModel.java:252
Constraint addGreaterOrEqual(LinearExpr expr, long value)
Adds.
Definition: CpModel.java:213
Constraint addForbiddenAssignments(IntVar[] variables, int[][] tuplesList)
Adds.
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.
Definition: CpModel.java:593
Constraint addGreaterOrEqual(LinearExpr left, LinearExpr right)
Adds.
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.
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.
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.
Definition: CpModel.java:197
Constraint addElement(IntVar index, long[] values, IntVar target)
Adds the element constraint:
Definition: CpModel.java:290
Literal falseLiteral()
Returns the false literal.
Definition: CpModel.java:106
Constraint addLessOrEqualWithOffset(LinearExpr left, LinearExpr right, long offset)
Adds.
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.
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.
Definition: CpModel.java:669
Constraint addReservoirConstraint(IntVar[] times, int[] demands, long minLevel, long maxLevel)
Adds.
Definition: CpModel.java:565
Constraint addGreaterThan(LinearExpr expr, long value)
Adds.
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.
Definition: CpModel.java:713
Constraint addReservoirConstraint(IntVar[] times, long[] demands, long minLevel, long maxLevel)
Adds.
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.
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.
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.
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.
Definition: CpModel.java:182
Constraint addElement(IntVar index, IntVar[] variables, IntVar target)
Adds the element constraint:
Definition: CpModel.java:278
Constraint addAbsEquality(IntVar target, IntVar var)
Adds.
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.
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.
Definition: CpModel.java:933
Constraint addReservoirConstraintWithActive(IntVar[] times, int[] demands, IntVar[] actives, long minLevel, long maxLevel)
Adds.
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.
Definition: CpModel.java:268
Constraint addImplication(Literal a, Literal b)
Adds.
Definition: CpModel.java:143
Constraint addBoolXor(Literal[] literals)
Adds.
Definition: CpModel.java:133
Constraint addCumulative(IntervalVar[] intervals, IntVar[] demands, IntVar capacity)
Adds.
Definition: CpModel.java:897
Constraint addLessThan(LinearExpr left, LinearExpr right)
Adds.
Definition: CpModel.java:202
Constraint addMinEquality(IntVar target, IntVar[] vars)
Adds.
Definition: CpModel.java:647
Constraint addCumulative(IntervalVar[] intervals, IntVar[] demands, long capacity)
Adds.
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.
Definition: CpModel.java:639
void addDecisionStrategy(IntVar[] variables, DecisionStrategyProto.VariableSelectionStrategy varStr, DecisionStrategyProto.DomainReductionStrategy domStr)
Adds.
Definition: CpModel.java:1034
Constraint addInverse(IntVar[] variables, IntVar[] inverseVariables)
Adds.
Definition: CpModel.java:499
Constraint addNoOverlap2D(IntervalVar[] xIntervals, IntervalVar[] yIntervals)
Adds.
Definition: CpModel.java:870
Constraint addLinearConstraint(LinearExpr expr, long lb, long ub)
Adds.
Definition: CpModel.java:167
Constraint addNoOverlap(IntervalVar[] intervalVars)
Adds.
Definition: CpModel.java:850
Literal trueLiteral()
Returns the true literal.
Definition: CpModel.java:101
Constraint addForbiddenAssignments(IntVar[] variables, long[][] tuplesList)
Adds.
Definition: CpModel.java:418
Constraint addDifferent(LinearExpr expr, long value)
Adds.
Definition: CpModel.java:239
Constraint addElement(IntVar index, int[] values, IntVar target)
Adds the element constraint:
Definition: CpModel.java:302
Constraint addEquality(LinearExpr expr, long value)
Adds.
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.
Definition: CpModel.java:233
Constraint addMaxEquality(IntVar target, IntVar[] vars)
Adds.
Definition: CpModel.java:658
Constraint addCumulative(IntervalVar[] intervals, int[] demands, long capacity)
Adds.
Definition: CpModel.java:978
Constraint addBoolOr(Literal[] literals)
Adds.
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.
Definition: CpModel.java:150
Constraint addBoolAnd(Literal[] literals)
Adds.
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.
Definition: CpModel.java:915
Constraint addLessOrEqual(LinearExpr left, LinearExpr right)
Adds.
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.