DotNet Reference

DotNet Reference

AssignmentMip.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 public class AssignmentMip
21 {
22  static void Main()
23  {
24  // Data.
25  // [START data_model]
26  int[,] costs = {
27  {90, 80, 75, 70},
28  {35, 85, 55, 65},
29  {125, 95, 90, 95},
30  {45, 110, 95, 115},
31  {50, 100, 90, 100},
32  };
33  int numWorkers = costs.GetLength(0);
34  int numTasks = costs.GetLength(1);
35  // [END data_model]
36 
37  // Model.
38  // [START model]
39  Solver solver = Solver.CreateSolver("AssignmentMip", "CBC_MIXED_INTEGER_PROGRAMMING");
40  // [END model]
41 
42  // Variables.
43  // [START variables]
44  // x[i, j] is an array of 0-1 variables, which will be 1
45  // if worker i is assigned to task j.
46  Variable[,] x = new Variable[numWorkers, numTasks];
47  for (int i = 0; i < numWorkers; ++i)
48  {
49  for (int j = 0; j < numTasks; ++j)
50  {
51  x[i, j] = solver.MakeIntVar(0, 1, $"worker_{i}_task_{j}");
52  }
53  }
54  // [END variables]
55 
56  // Constraints
57  // [START constraints]
58  // Each worker is assigned to at most one task.
59  for (int i = 0; i < numWorkers; ++i)
60  {
61  Constraint constraint = solver.MakeConstraint(0, 1, "");
62  for (int j = 0; j < numTasks; ++j)
63  {
64  constraint.SetCoefficient(x[i, j], 1);
65  }
66  }
67  // Each task is assigned to exactly one worker.
68  for (int j = 0; j < numTasks; ++j)
69  {
70  Constraint constraint = solver.MakeConstraint(1, 1, "");
71  for (int i = 0; i < numWorkers; ++i)
72  {
73  constraint.SetCoefficient(x[i, j], 1);
74  }
75  }
76  // [END constraints]
77 
78  // Objective
79  // [START objective]
80  Objective objective = solver.Objective();
81  for (int i = 0; i < numWorkers; ++i)
82  {
83  for (int j = 0; j < numTasks; ++j)
84  {
85  objective.SetCoefficient(x[i, j], 1);
86  }
87  }
88  objective.SetMinimization();
89  // [END objective]
90 
91  // Solve
92  // [START solve]
93  Solver.ResultStatus resultStatus = solver.Solve();
94  // [END solve]
95 
96  // Print solution.
97  // [START print_solution]
98  // Check that the problem has a feasible solution.
99  if (resultStatus == Solver.ResultStatus.OPTIMAL || resultStatus == Solver.ResultStatus.FEASIBLE)
100  {
101  Console.WriteLine($"Total cost: {solver.Objective().Value()}\n");
102  for (int i = 0; i < numWorkers; ++i)
103  {
104  for (int j = 0; j < numTasks; ++j)
105  {
106  // Test if x[i, j] is 0 or 1 (with tolerance for floating point
107  // arithmetic).
108  if (x[i, j].SolutionValue() > 0.5)
109  {
110  Console.WriteLine($"Worker {i} assigned to task {j}. Cost: {costs[i, j]}");
111  }
112  }
113  }
114  } else {
115  Console.WriteLine("No solution found.");
116  }
117  // [END print_solution]
118  }
119 }
120 // [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()
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)