DotNet Reference

.Net Reference

IntegerExpressions.cs
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14namespace Google.OrTools.Sat
15{
16 using System;
17 using System.Collections.Generic;
18 using Google.OrTools.Util;
19
20 // Helpers.
21
22 // IntVar[] helper class.
23 public static class IntVarArrayHelper
24 {
25 [Obsolete("This Sum method is deprecated, please use LinearExpr.Sum() instead.")]
26 public static LinearExpr Sum(this IntVar[] vars)
27 {
28 return LinearExpr.Sum(vars);
29 }
30 [Obsolete("This ScalProd method is deprecated, please use LinearExpr.ScalProd() instead.")]
31 public static LinearExpr ScalProd(this IntVar[] vars, int[] coeffs)
32 {
33 return LinearExpr.ScalProd(vars, coeffs);
34 }
35 [Obsolete("This ScalProd method is deprecated, please use LinearExpr.ScalProd() instead.")]
36 public static LinearExpr ScalProd(this IntVar[] vars, long[] coeffs)
37 {
38 return LinearExpr.ScalProd(vars, coeffs);
39 }
40 }
41
42 public interface ILiteral
43 {
45 int GetIndex();
46 }
47
48 // Holds a linear expression.
49 public class LinearExpr
50 {
51 public static LinearExpr Sum(IEnumerable<IntVar> vars)
52 {
53 return new SumArray(vars);
54 }
55
56 public static LinearExpr Sum(IEnumerable<LinearExpr> exprs)
57 {
58 return new SumArray(exprs);
59 }
60
61 public static LinearExpr ScalProd(IEnumerable<IntVar> vars, IEnumerable<int> coeffs)
62 {
63 return new SumArray(vars, coeffs);
64 }
65
66 public static LinearExpr ScalProd(IEnumerable<IntVar> vars, IEnumerable<long> coeffs)
67 {
68 return new SumArray(vars, coeffs);
69 }
70
71 public static LinearExpr Term(IntVar var, long coeff)
72 {
73 return Prod(var, coeff);
74 }
75
76 public int Index
77 {
78 get {
79 return GetIndex();
80 }
81 }
82
83 public virtual int GetIndex()
84 {
85 throw new NotImplementedException();
86 }
87
88 public virtual string ShortString()
89 {
90 return ToString();
91 }
92
94 {
95 return new SumArray(a, b);
96 }
97
98 public static LinearExpr operator +(LinearExpr a, long v)
99 {
100 return new SumArray(a, v);
101 }
102
103 public static LinearExpr operator +(long v, LinearExpr a)
104 {
105 return new SumArray(a, v);
106 }
107
109 {
110 return new SumArray(a, Prod(b, -1));
111 }
112
113 public static LinearExpr operator -(LinearExpr a, long v)
114 {
115 return new SumArray(a, -v);
116 }
117
118 public static LinearExpr operator -(long v, LinearExpr a)
119 {
120 return new SumArray(Prod(a, -1), v);
121 }
122
123 public static LinearExpr operator *(LinearExpr a, long v)
124 {
125 return Prod(a, v);
126 }
127
128 public static LinearExpr operator *(long v, LinearExpr a)
129 {
130 return Prod(a, v);
131 }
132
134 {
135 return Prod(a, -1);
136 }
137
139 {
140 return new BoundedLinearExpression(a, b, true);
141 }
142
144 {
145 return new BoundedLinearExpression(a, b, false);
146 }
147
149 {
150 return new BoundedLinearExpression(a, v, true);
151 }
152
154 {
155 return new BoundedLinearExpression(a, v, false);
156 }
157
159 {
160 return new BoundedLinearExpression(v, a, Int64.MaxValue);
161 }
162
164 {
165 return a <= v;
166 }
167
169 {
170 return new BoundedLinearExpression(v + 1, a, Int64.MaxValue);
171 }
172
174 {
175 return a < v;
176 }
177
179 {
180 return new BoundedLinearExpression(Int64.MinValue, a, v);
181 }
182
184 {
185 return a >= v;
186 }
187
189 {
190 return new BoundedLinearExpression(Int64.MinValue, a, v - 1);
191 }
192
194 {
195 return a > v;
196 }
197
199 {
200 return new BoundedLinearExpression(0, a - b, Int64.MaxValue);
201 }
202
204 {
205 return new BoundedLinearExpression(1, a - b, Int64.MaxValue);
206 }
207
209 {
210 return new BoundedLinearExpression(Int64.MinValue, a - b, 0);
211 }
212
214 {
215 return new BoundedLinearExpression(Int64.MinValue, a - b, -1);
216 }
217
218 public static LinearExpr Prod(LinearExpr e, long v)
219 {
220 if (v == 1)
221 {
222 return e;
223 }
224 else if (e is ProductCst)
225 {
226 ProductCst p = (ProductCst)e;
227 return new ProductCst(p.Expr, p.Coeff * v);
228 }
229 else
230 {
231 return new ProductCst(e, v);
232 }
233 }
234
235 public static long GetVarValueMap(LinearExpr e, long initial_coeff, Dictionary<IntVar, long> dict)
236 {
237 List<LinearExpr> exprs = new List<LinearExpr>();
238 List<long> coeffs = new List<long>();
239 if ((Object)e != null)
240 {
241 exprs.Add(e);
242 coeffs.Add(initial_coeff);
243 }
244 long constant = 0;
245
246 while (exprs.Count > 0)
247 {
248 LinearExpr expr = exprs[0];
249 exprs.RemoveAt(0);
250 long coeff = coeffs[0];
251 coeffs.RemoveAt(0);
252 if (coeff == 0 || (Object)expr == null)
253 continue;
254
255 if (expr is ProductCst)
256 {
257 ProductCst p = (ProductCst)expr;
258 if (p.Coeff != 0)
259 {
260 exprs.Add(p.Expr);
261 coeffs.Add(p.Coeff * coeff);
262 }
263 }
264 else if (expr is SumArray)
265 {
266 SumArray a = (SumArray)expr;
267 constant += coeff * a.Constant;
268 foreach (LinearExpr sub in a.Expressions)
269 {
270 if (sub is IntVar)
271 {
272 IntVar i = (IntVar)sub;
273 if (dict.ContainsKey(i))
274 {
275 dict[i] += coeff;
276 }
277 else
278 {
279 dict.Add(i, coeff);
280 }
281 }
282 else if (sub is ProductCst && ((ProductCst)sub).Expr is IntVar)
283 {
284 ProductCst sub_prod = (ProductCst)sub;
285 IntVar i = (IntVar)sub_prod.Expr;
286 long sub_coeff = sub_prod.Coeff;
287
288 if (dict.ContainsKey(i))
289 {
290 dict[i] += coeff * sub_coeff;
291 }
292 else
293 {
294 dict.Add(i, coeff * sub_coeff);
295 }
296 }
297 else
298 {
299 exprs.Add(sub);
300 coeffs.Add(coeff);
301 }
302 }
303 }
304 else if (expr is IntVar)
305 {
306 IntVar i = (IntVar)expr;
307 if (dict.ContainsKey(i))
308 {
309 dict[i] += coeff;
310 }
311 else
312 {
313 dict.Add(i, coeff);
314 }
315 }
316 else if (expr is NotBooleanVariable)
317 {
318 IntVar i = ((NotBooleanVariable)expr).NotVar();
319 if (dict.ContainsKey(i))
320 {
321 dict[i] -= coeff;
322 }
323 else
324 {
325 dict.Add(i, -coeff);
326 }
327 constant += coeff;
328 }
329 else
330 {
331 throw new ArgumentException("Cannot interpret '" + expr.ToString() + "' in an integer expression");
332 }
333 }
334 return constant;
335 }
336 }
337
338 public class ProductCst : LinearExpr
339 {
340 public ProductCst(LinearExpr e, long v)
341 {
342 expr_ = e;
343 coeff_ = v;
344 }
345
347 {
348 get {
349 return expr_;
350 }
351 }
352
353 public long Coeff
354 {
355 get {
356 return coeff_;
357 }
358 }
359
360 private LinearExpr expr_;
361 private long coeff_;
362 }
363
364 public class SumArray : LinearExpr
365 {
367 {
368 expressions_ = new List<LinearExpr>();
369 AddExpr(a);
370 AddExpr(b);
371 constant_ = 0L;
372 }
373
374 public SumArray(LinearExpr a, long b)
375 {
376 expressions_ = new List<LinearExpr>();
377 AddExpr(a);
378 constant_ = b;
379 }
380
381 public SumArray(IEnumerable<LinearExpr> exprs)
382 {
383 expressions_ = new List<LinearExpr>(exprs);
384 constant_ = 0L;
385 }
386
387 public SumArray(IEnumerable<IntVar> vars)
388 {
389 expressions_ = new List<LinearExpr>(vars);
390 constant_ = 0L;
391 }
392
393 public SumArray(IntVar[] vars, long[] coeffs)
394 {
395 expressions_ = new List<LinearExpr>(vars.Length);
396 for (int i = 0; i < vars.Length; ++i)
397 {
398 AddExpr(Prod(vars[i], coeffs[i]));
399 }
400 constant_ = 0L;
401 }
402 public SumArray(IEnumerable<IntVar> vars, IEnumerable<long> coeffs)
403 {
404 List<IntVar> tmp_vars = new List<IntVar>();
405 foreach (IntVar v in vars)
406 {
407 tmp_vars.Add(v);
408 }
409 List<long> tmp_coeffs = new List<long>();
410 foreach (long c in coeffs)
411 {
412 tmp_coeffs.Add(c);
413 }
414 if (tmp_vars.Count != tmp_coeffs.Count)
415 {
416 throw new ArgumentException("in SumArray(vars, coeffs), the two lists do not have the same length");
417 }
418 IntVar[] flat_vars = tmp_vars.ToArray();
419 long[] flat_coeffs = tmp_coeffs.ToArray();
420 expressions_ = new List<LinearExpr>(flat_vars.Length);
421 for (int i = 0; i < flat_vars.Length; ++i)
422 {
423 expressions_.Add(Prod(flat_vars[i], flat_coeffs[i]));
424 }
425 constant_ = 0L;
426 }
427
428 public SumArray(IEnumerable<IntVar> vars, IEnumerable<int> coeffs)
429 {
430 List<IntVar> tmp_vars = new List<IntVar>();
431 foreach (IntVar v in vars)
432 {
433 tmp_vars.Add(v);
434 }
435 List<long> tmp_coeffs = new List<long>();
436 foreach (int c in coeffs)
437 {
438 tmp_coeffs.Add(c);
439 }
440 if (tmp_vars.Count != tmp_coeffs.Count)
441 {
442 throw new ArgumentException("in SumArray(vars, coeffs), the two lists do not have the same length");
443 }
444 IntVar[] flat_vars = tmp_vars.ToArray();
445 long[] flat_coeffs = tmp_coeffs.ToArray();
446 expressions_ = new List<LinearExpr>(flat_vars.Length);
447 for (int i = 0; i < flat_vars.Length; ++i)
448 {
449 expressions_.Add(Prod(flat_vars[i], flat_coeffs[i]));
450 }
451 constant_ = 0L;
452 }
453
454 public void AddExpr(LinearExpr expr)
455 {
456 if ((Object)expr != null)
457 {
458 expressions_.Add(expr);
459 }
460 }
461
462 public List<LinearExpr> Expressions
463 {
464 get {
465 return expressions_;
466 }
467 }
468
469 public long Constant
470 {
471 get {
472 return constant_;
473 }
474 }
475
476 public override string ShortString()
477 {
478 return String.Format("({0})", ToString());
479 }
480
481 public override string ToString()
482 {
483 string result = "";
484 foreach (LinearExpr expr in expressions_)
485 {
486 if ((Object)expr == null)
487 continue;
488 if (!String.IsNullOrEmpty(result))
489 {
490 result += String.Format(" + ");
491 }
492
493 result += expr.ShortString();
494 }
495 return result;
496 }
497
498 private List<LinearExpr> expressions_;
499 private long constant_;
500 }
501
502 public class IntVar : LinearExpr, ILiteral
503 {
504 public IntVar(CpModelProto model, Domain domain, string name)
505 {
506 model_ = model;
507 index_ = model.Variables.Count;
508 var_ = new IntegerVariableProto();
509 var_.Name = name;
510 var_.Domain.Add(domain.FlattenedIntervals());
511 model.Variables.Add(var_);
512 negation_ = null;
513 }
514
515 public int Index
516 {
517 get {
518 return index_;
519 }
520 }
521
522 public override int GetIndex()
523 {
524 return index_;
525 }
526
527 public IntegerVariableProto Proto
528 {
529 get {
530 return var_;
531 }
532 set {
533 var_ = value;
534 }
535 }
536
538 {
539 get {
540 return SatHelper.VariableDomain(var_);
541 }
542 }
543
544 public override string ToString()
545 {
546 return var_.ToString();
547 }
548
549 public override string ShortString()
550 {
551 if (var_.Name != null)
552 {
553 return var_.Name;
554 }
555 else
556 {
557 return var_.ToString();
558 }
559 }
560
561 public string Name()
562 {
563 return var_.Name;
564 }
565
566 public ILiteral Not()
567 {
568 foreach (long b in var_.Domain)
569 {
570 if (b < 0 || b > 1)
571 {
572 throw new ArgumentException("Cannot call Not() on a non boolean variable");
573 }
574 }
575 if (negation_ == null)
576 {
577 negation_ = new NotBooleanVariable(this);
578 }
579 return negation_;
580 }
581
582 private CpModelProto model_;
583 private int index_;
584 private List<long> bounds_;
585 private IntegerVariableProto var_;
586 private NotBooleanVariable negation_;
587 }
588
590 {
592 {
593 boolvar_ = boolvar;
594 }
595
596 public override int GetIndex()
597 {
598 return -boolvar_.Index - 1;
599 }
600
601 public ILiteral Not()
602 {
603 return boolvar_;
604 }
605
606 public IntVar NotVar()
607 {
608 return boolvar_;
609 }
610
611 public override string ShortString()
612 {
613 return String.Format("Not({0})", boolvar_.ShortString());
614 }
615
616 private IntVar boolvar_;
617 }
618
620 {
621 public enum Type
622 {
623 BoundExpression,
624 VarEqVar,
625 VarDiffVar,
626 VarEqCst,
627 VarDiffCst,
628 }
629
630 public BoundedLinearExpression(long lb, LinearExpr expr, long ub)
631 {
632 left_ = expr;
633 right_ = null;
634 lb_ = lb;
635 ub_ = ub;
636 type_ = Type.BoundExpression;
637 }
638
639 public BoundedLinearExpression(LinearExpr left, LinearExpr right, bool equality)
640 {
641 left_ = left;
642 right_ = right;
643 lb_ = 0;
644 ub_ = 0;
645 type_ = equality ? Type.VarEqVar : Type.VarDiffVar;
646 }
647
648 public BoundedLinearExpression(LinearExpr left, long v, bool equality)
649 {
650 left_ = left;
651 right_ = null;
652 lb_ = v;
653 ub_ = 0;
654 type_ = equality ? Type.VarEqCst : Type.VarDiffCst;
655 }
656
657 bool IsTrue()
658 {
659 if (type_ == Type.VarEqVar)
660 {
661 return (object)left_ == (object)right_;
662 }
663 else if (type_ == Type.VarDiffVar)
664 {
665 return (object)left_ != (object)right_;
666 }
667 return false;
668 }
669
670 public static bool operator true(BoundedLinearExpression bie)
671 {
672 return bie.IsTrue();
673 }
674
675 public static bool operator false(BoundedLinearExpression bie)
676 {
677 return !bie.IsTrue();
678 }
679
680 public override string ToString()
681 {
682 switch (type_)
683 {
684 case Type.BoundExpression:
685 return String.Format("{0} <= {1} <= {2}", lb_, left_, ub_);
686 case Type.VarEqVar:
687 return String.Format("{0} == {1}", left_, right_);
688 case Type.VarDiffVar:
689 return String.Format("{0} != {1}", left_, right_);
690 case Type.VarEqCst:
691 return String.Format("{0} == {1}", left_, lb_);
692 case Type.VarDiffCst:
693 return String.Format("{0} != {1}", left_, lb_);
694 default:
695 throw new ArgumentException("Wrong mode in BoundedLinearExpression.");
696 }
697 }
698
700 {
701 if (a.CtType != Type.BoundExpression || a.Ub != Int64.MaxValue)
702 {
703 throw new ArgumentException("Operator <= not supported for this BoundedLinearExpression");
704 }
705 return new BoundedLinearExpression(a.Lb, a.Left, v);
706 }
707
709 {
710 if (a.CtType != Type.BoundExpression || a.Ub != Int64.MaxValue)
711 {
712 throw new ArgumentException("Operator < not supported for this BoundedLinearExpression");
713 }
714 return new BoundedLinearExpression(a.Lb, a.Left, v - 1);
715 }
716
718 {
719 if (a.CtType != Type.BoundExpression || a.Lb != Int64.MinValue)
720 {
721 throw new ArgumentException("Operator >= not supported for this BoundedLinearExpression");
722 }
723 return new BoundedLinearExpression(v, a.Left, a.Ub);
724 }
725
727 {
728 if (a.CtType != Type.BoundExpression || a.Lb != Int64.MinValue)
729 {
730 throw new ArgumentException("Operator < not supported for this BoundedLinearExpression");
731 }
732 return new BoundedLinearExpression(v + 1, a.Left, a.Ub);
733 }
734
736 {
737 get {
738 return left_;
739 }
740 }
741
743 {
744 get {
745 return right_;
746 }
747 }
748
749 public long Lb
750 {
751 get {
752 return lb_;
753 }
754 }
755
756 public long Ub
757 {
758 get {
759 return ub_;
760 }
761 }
762
764 {
765 get {
766 return type_;
767 }
768 }
769
770 private LinearExpr left_;
771 private LinearExpr right_;
772 private long lb_;
773 private long ub_;
774 private Type type_;
775 }
776
777} // namespace Google.OrTools.Sat
using System
Definition: Program.cs:14
static BoundedLinearExpression operator<=(BoundedLinearExpression a, long v)
BoundedLinearExpression(long lb, LinearExpr expr, long ub)
BoundedLinearExpression(LinearExpr left, LinearExpr right, bool equality)
BoundedLinearExpression(LinearExpr left, long v, bool equality)
static BoundedLinearExpression operator<(BoundedLinearExpression a, long v)
static BoundedLinearExpression operator>(BoundedLinearExpression a, long v)
static BoundedLinearExpression operator>=(BoundedLinearExpression a, long v)
static LinearExpr ScalProd(this IntVar[] vars, long[] coeffs)
static LinearExpr Sum(this IntVar[] vars)
static LinearExpr ScalProd(this IntVar[] vars, int[] coeffs)
IntVar(CpModelProto model, Domain domain, string name)
IntegerVariableProto Proto
static LinearExpr operator*(LinearExpr a, long v)
static LinearExpr Term(IntVar var, long coeff)
static LinearExpr Sum(IEnumerable< LinearExpr > exprs)
static BoundedLinearExpression operator<(LinearExpr a, long v)
static BoundedLinearExpression operator==(LinearExpr a, LinearExpr b)
static BoundedLinearExpression operator>(LinearExpr a, long v)
static BoundedLinearExpression operator>=(LinearExpr a, long v)
static BoundedLinearExpression operator<=(LinearExpr a, long v)
static LinearExpr Prod(LinearExpr e, long v)
static LinearExpr ScalProd(IEnumerable< IntVar > vars, IEnumerable< long > coeffs)
static LinearExpr ScalProd(IEnumerable< IntVar > vars, IEnumerable< int > coeffs)
static LinearExpr operator+(LinearExpr a, LinearExpr b)
static BoundedLinearExpression operator<(LinearExpr a, LinearExpr b)
static BoundedLinearExpression operator>(LinearExpr a, LinearExpr b)
static BoundedLinearExpression operator<(long v, LinearExpr a)
static long GetVarValueMap(LinearExpr e, long initial_coeff, Dictionary< IntVar, long > dict)
static BoundedLinearExpression operator>(long v, LinearExpr a)
static LinearExpr Sum(IEnumerable< IntVar > vars)
static BoundedLinearExpression operator!=(LinearExpr a, LinearExpr b)
static LinearExpr operator-(LinearExpr a, LinearExpr b)
ProductCst(LinearExpr e, long v)
SumArray(LinearExpr a, long b)
SumArray(IEnumerable< IntVar > vars, IEnumerable< long > coeffs)
void AddExpr(LinearExpr expr)
SumArray(IEnumerable< IntVar > vars)
SumArray(IEnumerable< IntVar > vars, IEnumerable< int > coeffs)
SumArray(IntVar[] vars, long[] coeffs)
SumArray(LinearExpr a, LinearExpr b)
SumArray(IEnumerable< LinearExpr > exprs)