DotNet Reference

DotNet Reference

BinPackingProblemSat.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 using System;
15 using Google.OrTools.Sat;
16 
18 {
19  static void Main()
20  {
21  // Data.
22  int bin_capacity = 100;
23  int slack_capacity = 20;
24  int num_bins = 5;
25 
26  int[,] items = new int[,] { { 20, 6 }, { 15, 6 }, { 30, 4 }, { 45, 3 } };
27  int num_items = items.GetLength(0);
28 
29  // Model.
30  CpModel model = new CpModel();
31 
32  // Main variables.
33  IntVar[,] x = new IntVar[num_items, num_bins];
34  for (int i = 0; i < num_items; ++i)
35  {
36  int num_copies = items[i, 1];
37  for (int b = 0; b < num_bins; ++b)
38  {
39  x[i, b] = model.NewIntVar(0, num_copies, String.Format("x_{0}_{1}", i, b));
40  }
41  }
42 
43  // Load variables.
44  IntVar[] load = new IntVar[num_bins];
45  for (int b = 0; b < num_bins; ++b)
46  {
47  load[b] = model.NewIntVar(0, bin_capacity, String.Format("load_{0}", b));
48  }
49 
50  // Slack variables.
51  IntVar[] slacks = new IntVar[num_bins];
52  for (int b = 0; b < num_bins; ++b)
53  {
54  slacks[b] = model.NewBoolVar(String.Format("slack_{0}", b));
55  }
56 
57  // Links load and x.
58  int[] sizes = new int[num_items];
59  for (int i = 0; i < num_items; ++i)
60  {
61  sizes[i] = items[i, 0];
62  }
63  for (int b = 0; b < num_bins; ++b)
64  {
65  IntVar[] tmp = new IntVar[num_items];
66  for (int i = 0; i < num_items; ++i)
67  {
68  tmp[i] = x[i, b];
69  }
70  model.Add(load[b] == LinearExpr.ScalProd(tmp, sizes));
71  }
72 
73  // Place all items.
74  for (int i = 0; i < num_items; ++i)
75  {
76  IntVar[] tmp = new IntVar[num_bins];
77  for (int b = 0; b < num_bins; ++b)
78  {
79  tmp[b] = x[i, b];
80  }
81  model.Add(LinearExpr.Sum(tmp) == items[i, 1]);
82  }
83 
84  // Links load and slack.
85  int safe_capacity = bin_capacity - slack_capacity;
86  for (int b = 0; b < num_bins; ++b)
87  {
88  // slack[b] => load[b] <= safe_capacity.
89  model.Add(load[b] <= safe_capacity).OnlyEnforceIf(slacks[b]);
90  // not(slack[b]) => load[b] > safe_capacity.
91  model.Add(load[b] > safe_capacity).OnlyEnforceIf(slacks[b].Not());
92  }
93 
94  // Maximize sum of slacks.
95  model.Maximize(LinearExpr.Sum(slacks));
96 
97  // Solves and prints out the solution.
98  CpSolver solver = new CpSolver();
99  CpSolverStatus status = solver.Solve(model);
100  Console.WriteLine(String.Format("Solve status: {0}", status));
101  if (status == CpSolverStatus.Optimal) {
102  Console.WriteLine(String.Format("Optimal objective value: {0}",
103  solver.ObjectiveValue));
104  for (int b = 0; b < num_bins; ++b)
105  {
106  Console.WriteLine(String.Format("load_{0} = {1}",
107  b, solver.Value(load[b])));
108  for (int i = 0; i < num_items; ++i)
109  {
110  Console.WriteLine(string.Format(" item_{0}_{1} = {2}",
111  i, b, solver.Value(x[i, b])));
112  }
113  }
114  }
115  Console.WriteLine("Statistics");
116  Console.WriteLine(String.Format(" - conflicts : {0}",
117  solver.NumConflicts()));
118  Console.WriteLine(String.Format(" - branches : {0}",
119  solver.NumBranches()));
120  Console.WriteLine(String.Format(" - wall time : {0} s",
121  solver.WallTime()));
122  }
123 }
Wrapper class around the cp_model proto.
Definition: CpModel.cs:24
void OnlyEnforceIf(ILiteral lit)
Definition: Constraints.cs:28
static LinearExpr Sum(IEnumerable< IntVar > vars)
CpSolverStatus
The status returned by a solver trying to solve a CpModelProto.
Definition: CpModel.pb.cs:186
static LinearExpr ScalProd(IEnumerable< IntVar > vars, IEnumerable< int > coeffs)
double WallTime()
Definition: CpSolver.cs:183
IntVar NewIntVar(long lb, long ub, string name)
Definition: CpModel.cs:45
Constraint Add(BoundedLinearExpression lin)
Definition: CpModel.cs:104
long NumBranches()
Definition: CpSolver.cs:173
double ObjectiveValue
Definition: CpSolver.cs:76
long NumConflicts()
Definition: CpSolver.cs:178
CpSolverStatus Solve(CpModel model)
Definition: CpSolver.cs:22
Definition: CpSolver.cs:20
long Value(LinearExpr e)
Definition: CpSolver.cs:96
void Maximize(LinearExpr obj)
Definition: CpModel.cs:593
IntVar NewBoolVar(string name)
Definition: CpModel.cs:67
Definition: CpModel.pb.cs:12