DotNet Reference

DotNet Reference

BinPackingMip.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 // [START program]
15 // [START import]
16 using System;
18 // [END import]
19 
20 // [START program_part1]
21 public class BinPackingMip
22 {
23  // [START data_model]
24  class DataModel
25  {
26  public static double[] Weights = {48, 30, 19, 36, 36, 27, 42, 42, 36, 24, 30};
27  public int NumItems = Weights.Length;
28  public int NumBins = Weights.Length;
29  public double BinCapacity = 100.0;
30  }
31  // [END data_model]
32  public static void Main()
33  {
34  // [START data]
35  DataModel data = new DataModel();
36  // [END data]
37  // [END program_part1]
38 
39  // [START solver]
40  // Create the linear solver with the CBC backend.
41  Solver solver = Solver.CreateSolver("BinPackingMip", "CBC_MIXED_INTEGER_PROGRAMMING");
42  // [END solver]
43 
44  // [START program_part2]
45  // [START variables]
46  Variable[,] x = new Variable[data.NumItems, data.NumBins];
47  for (int i = 0; i < data.NumItems; i++)
48  {
49  for (int j = 0; j < data.NumBins; j++)
50  {
51  x[i, j] = solver.MakeIntVar(0, 1, $"x_{i}_{j}");
52  }
53  }
54  Variable[] y = new Variable[data.NumBins];
55  for (int j = 0; j < data.NumBins; j++)
56  {
57  y[j] = solver.MakeIntVar(0, 1, $"y_{j}");
58  }
59  // [END variables]
60 
61  // [START constraints]
62  for (int i = 0; i < data.NumItems; ++i) {
63  Constraint constraint = solver.MakeConstraint(1, 1, "");
64  for (int j = 0; j < data.NumBins; ++j) {
65  constraint.SetCoefficient(x[i, j], 1);
66  }
67  }
68 
69  for (int j = 0; j < data.NumBins; ++j)
70  {
71  Constraint constraint = solver.MakeConstraint(0, Double.PositiveInfinity, "");
72  constraint.SetCoefficient(y[j], data.BinCapacity);
73  for (int i = 0; i < data.NumItems; ++i)
74  {
75  constraint.SetCoefficient(x[i, j], -DataModel.Weights[i]);
76  }
77  }
78  // [END constraints]
79 
80  // [START objective]
81  Objective objective = solver.Objective();
82  for (int j = 0; j < data.NumBins; ++j)
83  {
84  objective.SetCoefficient(y[j], 1);
85  }
86  objective.SetMinimization();
87  // [END objective]
88 
89  // [START solve]
90  Solver.ResultStatus resultStatus = solver.Solve();
91  // [END solve]
92 
93  // [START print_solution]
94  // Check that the problem has an optimal solution.
95  if (resultStatus != Solver.ResultStatus.OPTIMAL)
96  {
97  Console.WriteLine("The problem does not have an optimal solution!");
98  return;
99  }
100  Console.WriteLine($"Number of bins used: {solver.Objective().Value()}");
101  double TotalWeight = 0.0;
102  for (int j = 0; j < data.NumBins; ++j)
103  {
104  double BinWeight = 0.0;
105  if (y[j].SolutionValue() == 1)
106  {
107  Console.WriteLine($"Bin {j}");
108  for (int i = 0; i < data.NumItems; ++i)
109  {
110  if (x[i, j].SolutionValue() == 1)
111  {
112  Console.WriteLine($"Item {i} weight: {DataModel.Weights[i]}");
113  BinWeight += DataModel.Weights[i];
114  }
115  }
116  Console.WriteLine($"Packed bin weight: {BinWeight}");
117  TotalWeight += BinWeight;
118  }
119  }
120  Console.WriteLine($"Total packed weight: {TotalWeight}");
121  // [END print_solution]
122  }
123 }
124 // [END program_part2]
125 // [END program]
Definition: Variable.cs:13
Solver.ResultStatus Solve()
void SetCoefficient(Variable var, double coeff)
Definition: Objective.cs:13
void SetMinimization()
Definition: Objective.cs:73
Objective Objective()
static void Main()
void SetCoefficient(Variable var, double coeff)
Definition: Objective.cs:51
ResultStatus
Variable MakeIntVar(double lb, double ub, string name)
static Solver CreateSolver(String name, String type)
Constraint MakeConstraint(double lb, double ub)