DotNet Reference

DotNet Reference

MultipleKnapsackMip.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 MultipleKnapsackMip
22 {
23  // [START data_model]
24  class DataModel
25  {
26  public static double[] Weights =
27  {48, 30, 42, 36, 36, 48, 42, 42, 36, 24, 30, 30, 42, 36, 36};
28  public static double[] Values =
29  {10, 30, 25, 50, 35, 30, 15, 40, 30, 35, 45, 10, 20, 30, 25};
30  public double[] BinCapacities = {100, 100, 100, 100, 100};
31  public int NumItems = Weights.Length;
32  public int NumBins = 5;
33  }
34  // [END data_model]
35  public static void Main()
36  {
37  // [START data]
38  DataModel data = new DataModel();
39  // [END data]
40  // [END program_part1]
41 
42  // [START solver]
43  // Create the linear solver with the CBC backend.
44  Solver solver = Solver.CreateSolver("MultipleKnapsackMip", "CBC_MIXED_INTEGER_PROGRAMMING");
45  // [END solver]
46 
47  // [START program_part2]
48  // [START variables]
49  Variable[,] x = new Variable[data.NumItems, data.NumBins];
50  for (int i = 0; i < data.NumItems; i++)
51  {
52  for (int j = 0; j < data.NumBins; j++)
53  {
54  x[i, j] = solver.MakeIntVar(0, 1, $"x_{i}_{j}");
55  }
56  }
57  // [END variables]
58 
59  // [START constraints]
60  for (int i = 0; i < data.NumItems; ++i) {
61  Constraint constraint = solver.MakeConstraint(0, 1, "");
62  for (int j = 0; j < data.NumBins; ++j) {
63  constraint.SetCoefficient(x[i, j], 1);
64  }
65  }
66 
67  for (int j = 0; j < data.NumBins; ++j)
68  {
69  Constraint constraint = solver.MakeConstraint(0, data.BinCapacities[j], "");
70  for (int i = 0; i < data.NumItems; ++i)
71  {
72  constraint.SetCoefficient(x[i, j], DataModel.Weights[i]);
73  }
74  }
75  // [END constraints]
76 
77  // [START objective]
78  Objective objective = solver.Objective();
79  for (int i = 0; i < data.NumItems; ++i)
80  {
81  for (int j = 0; j < data.NumBins; ++j)
82  {
83  objective.SetCoefficient(x[i, j], DataModel.Values[i]);
84  }
85  }
86  objective.SetMaximization();
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("Total packed value: " + solver.Objective().Value());
101  double TotalWeight = 0.0;
102  for (int j = 0; j < data.NumBins; ++j)
103  {
104  double BinWeight = 0.0;
105  double BinValue = 0.0;
106  Console.WriteLine("Bin " + j);
107  for (int i = 0; i < data.NumItems; ++i)
108  {
109  if (x[i, j].SolutionValue() == 1)
110  {
111  Console.WriteLine($"Item {i} weight: {DataModel.Weights[i]} values: {DataModel.Values[i]}");
112  BinWeight += DataModel.Weights[i];
113  BinValue += DataModel.Values[i];
114  }
115  }
116  Console.WriteLine("Packed bin weight: " + BinWeight);
117  Console.WriteLine("Packed bin value: " + BinValue);
118  TotalWeight += BinWeight;
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
double Value()
Definition: Objective.cs:91
Objective Objective()
static void Main()
void SetCoefficient(Variable var, double coeff)
Definition: Objective.cs:51
ResultStatus
Variable MakeIntVar(double lb, double ub, string name)
void SetMaximization()
Definition: Objective.cs:77
static Solver CreateSolver(String name, String type)
Constraint MakeConstraint(double lb, double ub)