DotNet Reference

DotNet 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 
14 namespace 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 
52  public static LinearExpr Sum(IEnumerable<IntVar> vars)
53  {
54  return new SumArray(vars);
55  }
56 
57  public static LinearExpr Sum(IEnumerable<LinearExpr> exprs)
58  {
59  return new SumArray(exprs);
60  }
61 
62  public static LinearExpr ScalProd(IEnumerable<IntVar> vars, IEnumerable<int> coeffs)
63  {
64  return new SumArray(vars, coeffs);
65  }
66 
67  public static LinearExpr ScalProd(IEnumerable<IntVar> vars, IEnumerable<long> coeffs)
68  {
69  return new SumArray(vars, coeffs);
70  }
71 
72  public static LinearExpr Term(IntVar var, long coeff)
73  {
74  return Prod(var, coeff);
75  }
76 
77  public int Index
78  {
79  get { return GetIndex(); }
80  }
81 
82  public virtual int GetIndex()
83  {
84  throw new NotImplementedException();
85  }
86 
87  public virtual string ShortString()
88  {
89  return ToString();
90  }
91 
93  {
94  return new SumArray(a, b);
95  }
96 
97  public static LinearExpr operator +(LinearExpr a, long v)
98  {
99  return new SumArray(a, v);
100  }
101 
102  public static LinearExpr operator +(long v, LinearExpr a)
103  {
104  return new SumArray(a, v);
105  }
106 
108  {
109  return new SumArray(a, Prod(b, -1));
110  }
111 
112  public static LinearExpr operator -(LinearExpr a, long v)
113  {
114  return new SumArray(a, -v);
115  }
116 
117  public static LinearExpr operator -(long v, LinearExpr a)
118  {
119  return new SumArray(Prod(a, -1), v);
120  }
121 
122  public static LinearExpr operator *(LinearExpr a, long v)
123  {
124  return Prod(a, v);
125  }
126 
127  public static LinearExpr operator *(long v, LinearExpr a)
128  {
129  return Prod(a, v);
130  }
131 
133  {
134  return Prod(a, -1);
135  }
136 
138  {
139  return new BoundedLinearExpression(a, b, true);
140  }
141 
143  {
144  return new BoundedLinearExpression(a, b, false);
145  }
146 
148  {
149  return new BoundedLinearExpression(a, v, true);
150  }
151 
153  {
154  return new BoundedLinearExpression(a, v, false);
155  }
156 
158  {
159  return new BoundedLinearExpression(v, a, Int64.MaxValue);
160  }
161 
163  {
164  return a <= v;
165  }
166 
168  {
169  return new BoundedLinearExpression(v + 1, a, Int64.MaxValue);
170  }
171 
173  {
174  return a < v;
175  }
176 
178  {
179  return new BoundedLinearExpression(Int64.MinValue, a, v);
180  }
181 
183  {
184  return a >= v;
185  }
186 
188  {
189  return new BoundedLinearExpression(Int64.MinValue, a, v - 1);
190  }
191 
193  {
194  return a > v;
195  }
196 
198  {
199  return new BoundedLinearExpression(0, a - b, Int64.MaxValue);
200  }
201 
203  {
204  return new BoundedLinearExpression(1, a - b, Int64.MaxValue);
205  }
206 
208  {
209  return new BoundedLinearExpression(Int64.MinValue, a - b, 0);
210  }
211 
213  {
214  return new BoundedLinearExpression(Int64.MinValue, a - b, -1);
215  }
216 
217  public static LinearExpr Prod(LinearExpr e, long v)
218  {
219  if (v == 1)
220  {
221  return e;
222  }
223  else if (e is ProductCst)
224  {
225  ProductCst p = (ProductCst)e;
226  return new ProductCst(p.Expr, p.Coeff * v);
227  }
228  else
229  {
230  return new ProductCst(e, v);
231  }
232  }
233 
234  public static long GetVarValueMap(LinearExpr e,
235  long initial_coeff,
236  Dictionary<IntVar, long> dict)
237  {
238  List<LinearExpr> exprs = new List<LinearExpr>();
239  List<long> coeffs = new List<long>();
240  if ((Object)e != null)
241  {
242  exprs.Add(e);
243  coeffs.Add(initial_coeff);
244  }
245  long constant = 0;
246 
247  while (exprs.Count > 0)
248  {
249  LinearExpr expr = exprs[0];
250  exprs.RemoveAt(0);
251  long coeff = coeffs[0];
252  coeffs.RemoveAt(0);
253  if (coeff == 0 || (Object)expr == null) 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() +
332  "' in an integer expression");
333  }
334  }
335  return constant;
336  }
337  }
338 
339  public class ProductCst : LinearExpr
340  {
341  public ProductCst(LinearExpr e, long v)
342  {
343  expr_ = e;
344  coeff_ = v;
345  }
346 
348  {
349  get { return expr_; }
350  }
351 
352  public long Coeff
353  {
354  get { return coeff_; }
355  }
356 
357  private LinearExpr expr_;
358  private long coeff_;
359 
360  }
361 
362  public class SumArray : LinearExpr
363  {
365  {
366  expressions_ = new List<LinearExpr>();
367  AddExpr(a);
368  AddExpr(b);
369  constant_ = 0L;
370  }
371 
372  public SumArray(LinearExpr a, long b)
373  {
374  expressions_ = new List<LinearExpr>();
375  AddExpr(a);
376  constant_ = b;
377  }
378 
379  public SumArray(IEnumerable<LinearExpr> exprs)
380  {
381  expressions_ = new List<LinearExpr>(exprs);
382  constant_ = 0L;
383  }
384 
385  public SumArray(IEnumerable<IntVar> vars)
386  {
387  expressions_ = new List<LinearExpr>(vars);
388  constant_ = 0L;
389  }
390 
391  public SumArray(IntVar[] vars, long[] coeffs)
392  {
393  expressions_ = new List<LinearExpr>(vars.Length);
394  for (int i = 0; i < vars.Length; ++i)
395  {
396  AddExpr(Prod(vars[i], coeffs[i]));
397  }
398  constant_ = 0L;
399  }
400  public SumArray(IEnumerable<IntVar> vars, IEnumerable<long> coeffs)
401  {
402  List<IntVar> tmp_vars = new List<IntVar>();
403  foreach (IntVar v in vars)
404  {
405  tmp_vars.Add(v);
406  }
407  List<long> tmp_coeffs = new List<long>();
408  foreach (long c in coeffs)
409  {
410  tmp_coeffs.Add(c);
411  }
412  if (tmp_vars.Count != tmp_coeffs.Count)
413  {
414  throw new ArgumentException(
415  "in SumArray(vars, coeffs), the two lists do not have the same length");
416  }
417  IntVar[] flat_vars = tmp_vars.ToArray();
418  long[] flat_coeffs = tmp_coeffs.ToArray();
419  expressions_ = new List<LinearExpr>(flat_vars.Length);
420  for (int i = 0; i < flat_vars.Length; ++i)
421  {
422  expressions_.Add(Prod(flat_vars[i], flat_coeffs[i]));
423  }
424  constant_ = 0L;
425  }
426 
427  public SumArray(IEnumerable<IntVar> vars, IEnumerable<int> coeffs)
428  {
429  List<IntVar> tmp_vars = new List<IntVar>();
430  foreach (IntVar v in vars)
431  {
432  tmp_vars.Add(v);
433  }
434  List<long> tmp_coeffs = new List<long>();
435  foreach (int c in coeffs)
436  {
437  tmp_coeffs.Add(c);
438  }
439  if (tmp_vars.Count != tmp_coeffs.Count)
440  {
441  throw new ArgumentException(
442  "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 { return expressions_; }
465  }
466 
467  public long Constant
468  {
469  get { return constant_; }
470  }
471 
472  public override string ShortString()
473  {
474  return String.Format("({0})", ToString());
475  }
476 
477  public override string ToString()
478  {
479  string result = "";
480  foreach (LinearExpr expr in expressions_)
481  {
482  if ((Object)expr == null) continue;
483  if (!String.IsNullOrEmpty(result))
484  {
485  result += String.Format(" + ");
486  }
487 
488  result += expr.ShortString();
489  }
490  return result;
491  }
492 
493  private List<LinearExpr> expressions_;
494  private long constant_;
495  }
496 
497  public class IntVar : LinearExpr, ILiteral
498  {
499  public IntVar(CpModelProto model, Domain domain, string name)
500  {
501  model_ = model;
502  index_ = model.Variables.Count;
503  var_ = new IntegerVariableProto();
504  var_.Name = name;
505  var_.Domain.Add(domain.FlattenedIntervals());
506  model.Variables.Add(var_);
507  negation_ = null;
508  }
509 
510  public int Index
511  {
512  get { return index_; }
513  }
514 
515  public override int GetIndex()
516  {
517  return index_;
518  }
519 
521  {
522  get { return var_; }
523  set { var_ = value; }
524  }
525 
526  public Domain Domain
527  {
528  get { return SatHelper.VariableDomain(var_); }
529  }
530 
531  public override string ToString()
532  {
533  return var_.ToString();
534  }
535 
536  public override string ShortString()
537  {
538  if (var_.Name != null)
539  {
540  return var_.Name;
541  }
542  else
543  {
544  return var_.ToString();
545  }
546  }
547 
548  public string Name()
549  {
550  return var_.Name;
551  }
552 
553  public ILiteral Not()
554  {
555  foreach (long b in var_.Domain)
556  {
557  if (b < 0 || b > 1)
558  {
559  throw new ArgumentException(
560  "Cannot call Not() on a non boolean variable");
561  }
562  }
563  if (negation_ == null)
564  {
565  negation_ = new NotBooleanVariable(this);
566  }
567  return negation_;
568  }
569 
570  private CpModelProto model_;
571  private int index_;
572  private List<long> bounds_;
573  private IntegerVariableProto var_;
574  private NotBooleanVariable negation_;
575  }
576 
578  {
579  public NotBooleanVariable(IntVar boolvar)
580  {
581  boolvar_ = boolvar;
582  }
583 
584  public override int GetIndex()
585  {
586  return -boolvar_.Index - 1;
587  }
588 
589  public ILiteral Not()
590  {
591  return boolvar_;
592  }
593 
594  public IntVar NotVar()
595  {
596  return boolvar_;
597  }
598 
599  public override string ShortString()
600  {
601  return String.Format("Not({0})", boolvar_.ShortString());
602  }
603 
604  private IntVar boolvar_;
605  }
606 
608  {
609  public enum Type
610  {
611  BoundExpression,
612  VarEqVar,
613  VarDiffVar,
614  VarEqCst,
615  VarDiffCst,
616  }
617 
618  public BoundedLinearExpression(long lb, LinearExpr expr, long ub)
619  {
620  left_ = expr;
621  right_ = null;
622  lb_ = lb;
623  ub_ = ub;
624  type_ = Type.BoundExpression;
625  }
626 
628  bool equality)
629  {
630  left_ = left;
631  right_ = right;
632  lb_ = 0;
633  ub_ = 0;
634  type_ = equality ? Type.VarEqVar : Type.VarDiffVar;
635  }
636 
637  public BoundedLinearExpression(LinearExpr left, long v, bool equality)
638  {
639  left_ = left;
640  right_ = null;
641  lb_ = v;
642  ub_ = 0;
643  type_ = equality ? Type.VarEqCst : Type.VarDiffCst;
644  }
645 
646  bool IsTrue()
647  {
648  if (type_ == Type.VarEqVar)
649  {
650  return (object)left_ == (object)right_;
651  }
652  else if (type_ == Type.VarDiffVar)
653  {
654  return (object)left_ != (object)right_;
655  }
656  return false;
657  }
658 
659  public static bool operator true(BoundedLinearExpression bie)
660  {
661  return bie.IsTrue();
662  }
663 
664  public static bool operator false(BoundedLinearExpression bie)
665  {
666  return !bie.IsTrue();
667  }
668 
669  public override string ToString()
670  {
671  switch (type_)
672  {
673  case Type.BoundExpression:
674  return String.Format("{0} <= {1} <= {2}", lb_, left_, ub_);
675  case Type.VarEqVar:
676  return String.Format("{0} == {1}", left_, right_);
677  case Type.VarDiffVar:
678  return String.Format("{0} != {1}", left_, right_);
679  case Type.VarEqCst:
680  return String.Format("{0} == {1}", left_, lb_);
681  case Type.VarDiffCst:
682  return String.Format("{0} != {1}", left_, lb_);
683  default:
684  throw new ArgumentException("Wrong mode in BoundedLinearExpression.");
685  }
686  }
687 
689  long v)
690  {
691  if (a.CtType != Type.BoundExpression || a.Ub != Int64.MaxValue)
692  {
693  throw new ArgumentException(
694  "Operator <= not supported for this BoundedLinearExpression");
695  }
696  return new BoundedLinearExpression(a.Lb, a.Left, v);
697  }
698 
700  long v)
701  {
702  if (a.CtType != Type.BoundExpression || a.Ub != Int64.MaxValue)
703  {
704  throw new ArgumentException(
705  "Operator < not supported for this BoundedLinearExpression");
706  }
707  return new BoundedLinearExpression(a.Lb, a.Left, v - 1);
708  }
709 
711  long v)
712  {
713  if (a.CtType != Type.BoundExpression || a.Lb != Int64.MinValue)
714  {
715  throw new ArgumentException(
716  "Operator >= not supported for this BoundedLinearExpression");
717  }
718  return new BoundedLinearExpression(v, a.Left, a.Ub);
719  }
720 
722  long v)
723  {
724  if (a.CtType != Type.BoundExpression || a.Lb != Int64.MinValue)
725  {
726  throw new ArgumentException(
727  "Operator < not supported for this BoundedLinearExpression");
728  }
729  return new BoundedLinearExpression(v + 1, a.Left, a.Ub);
730  }
731 
733  {
734  get { return left_; }
735  }
736 
738  {
739  get { return right_; }
740  }
741 
742  public long Lb
743  {
744  get { return lb_; }
745  }
746 
747  public long Ub
748  {
749  get { return ub_; }
750  }
751 
752  public Type CtType
753  {
754  get { return type_; }
755  }
756 
757  private LinearExpr left_;
758  private LinearExpr right_;
759  private long lb_;
760  private long ub_;
761  private Type type_;
762  }
763 
764 } // namespace Google.OrTools.Sat
static long GetVarValueMap(LinearExpr e, long initial_coeff, Dictionary< IntVar, long > dict)
IntVar(CpModelProto model, Domain domain, string name)
SumArray(IEnumerable< IntVar > vars, IEnumerable< long > coeffs)
override string ShortString()
Definition: Domain.cs:17
BoundedLinearExpression(LinearExpr left, LinearExpr right, bool equality)
SumArray(IEnumerable< LinearExpr > exprs)
override string ToString()
Definition: CpModel.pb.cs:352
IntVar NotVar()
override int GetIndex()
List< LinearExpr > Expressions
long Constant
LinearExpr Expr
SumArray(IEnumerable< IntVar > vars)
An integer variable.
Definition: CpModel.pb.cs:244
long Coeff
static BoundedLinearExpression operator<(BoundedLinearExpression a, long v)
static LinearExpr ScalProd(IEnumerable< IntVar > vars, IEnumerable< long > coeffs)
static BoundedLinearExpression operator<(LinearExpr a, long v)
static LinearExpr Sum(IEnumerable< IntVar > vars)
Type
Definition: SatHelper.cs:15
string Name()
ProductCst(LinearExpr e, long v)
ILiteral Not()
static BoundedLinearExpression operator!=(LinearExpr a, LinearExpr b)
static LinearExpr operator-(LinearExpr a, LinearExpr b)
static LinearExpr ScalProd(IEnumerable< IntVar > vars, IEnumerable< int > coeffs)
static LinearExpr operator*(LinearExpr a, long v)
static BoundedLinearExpression operator>(BoundedLinearExpression a, long v)
static BoundedLinearExpression operator>=(BoundedLinearExpression a, long v)
override string ShortString()
override int GetIndex()
string Name
For debug/logging only.
Definition: CpModel.pb.cs:286
A constraint programming problem.
Definition: CpModel.pb.cs:5663
void AddExpr(LinearExpr expr)
override string ShortString()
int Index
long Lb
static LinearExpr Sum(this IntVar[] vars)
virtual int GetIndex()
pbc::RepeatedField< global::Google.OrTools.Sat.IntegerVariableProto > Variables
The associated Protos should be referred by their index in these fields.
Definition: CpModel.pb.cs:5726
ILiteral Not()
static LinearExpr Prod(LinearExpr e, long v)
static BoundedLinearExpression operator==(LinearExpr a, LinearExpr b)
SumArray(IntVar[] vars, long[] coeffs)
long Ub
override string ToString()
IntegerVariableProto Proto
override string ToString()
long[] FlattenedIntervals()
Definition: Domain.cs:84
static BoundedLinearExpression operator>=(LinearExpr a, long v)
static BoundedLinearExpression operator>(LinearExpr a, long v)
static LinearExpr ScalProd(this IntVar[] vars, long[] coeffs)
BoundedLinearExpression(long lb, LinearExpr expr, long ub)
static LinearExpr ScalProd(this IntVar[] vars, int[] coeffs)
LinearExpr Left
SumArray(IEnumerable< IntVar > vars, IEnumerable< int > coeffs)
override string ToString()
NotBooleanVariable(IntVar boolvar)
static LinearExpr Sum(IEnumerable< LinearExpr > exprs)
static BoundedLinearExpression operator<=(LinearExpr a, long v)
static BoundedLinearExpression operator<=(BoundedLinearExpression a, long v)
Type CtType
BoundedLinearExpression(LinearExpr left, long v, bool equality)
static Domain VariableDomain(Google.OrTools.Sat.IntegerVariableProto variable_proto)
Definition: SatHelper.cs:124
LinearExpr Right
Definition: Domain.cs:11
ILiteral Not()
static LinearExpr operator+(LinearExpr a, LinearExpr b)
virtual string ShortString()
int Index
int GetIndex()
pbc::RepeatedField< long > Domain
The variable domain given as a sorted list of n disjoint intervals [min, max] and encoded as [min_0,...
Definition: CpModel.pb.cs:318
SumArray(LinearExpr a, long b)
static LinearExpr Term(IntVar var, long coeff)
SumArray(LinearExpr a, LinearExpr b)
Definition: CpModel.pb.cs:12