DotNet Reference

.Net Reference

LinearSolverTests.cs
Go to the documentation of this file.
1 // Copyright 2010-2022 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 Xunit;
16 using Google.OrTools.LinearSolver;
17 
18 namespace Google.OrTools.Tests
19 {
20 public class LinearSolverTest
21 {
22  [Fact]
23  public void VarOperator()
24  {
25  Solver solver = Solver.CreateSolver("CLP");
26  if (solver is null)
27  {
28  return;
29  }
30  Variable x = solver.MakeNumVar(0.0, 100.0, "x");
31  Assert.Equal(0.0, x.Lb());
32  Assert.Equal(100.0, x.Ub());
33 
34  Constraint ct1 = solver.Add(x >= 1);
35  Assert.Equal(1.0, ct1.GetCoefficient(x));
36  Assert.Equal(1.0, ct1.Lb());
37  Assert.Equal(double.PositiveInfinity, ct1.Ub());
38 
39  Constraint ct2 = solver.Add(x <= 1);
40  Assert.Equal(1.0, ct2.GetCoefficient(x));
41  Assert.Equal(double.NegativeInfinity, ct2.Lb());
42  Assert.Equal(1.0, ct2.Ub());
43 
44  Constraint ct3 = solver.Add(x == 1);
45  Assert.Equal(1.0, ct3.GetCoefficient(x));
46  Assert.Equal(1.0, ct3.Lb());
47  Assert.Equal(1.0, ct3.Ub());
48 
49  Constraint ct4 = solver.Add(1 >= x);
50  Assert.Equal(1.0, ct4.GetCoefficient(x));
51  Assert.Equal(double.NegativeInfinity, ct4.Lb());
52  Assert.Equal(1.0, ct4.Ub());
53 
54  Constraint ct5 = solver.Add(1 <= x);
55  Assert.Equal(1.0, ct5.GetCoefficient(x));
56  Assert.Equal(1.0, ct5.Lb());
57  Assert.Equal(double.PositiveInfinity, ct5.Ub());
58 
59  Constraint ct6 = solver.Add(1 == x);
60  Assert.Equal(1.0, ct6.GetCoefficient(x));
61  Assert.Equal(1.0, ct6.Lb());
62  Assert.Equal(1.0, ct6.Ub());
63  }
64 
65  [Fact]
66  public void VarAddition()
67  {
68  Solver solver = Solver.CreateSolver("CLP");
69  if (solver is null)
70  {
71  return;
72  }
73  Variable x = solver.MakeNumVar(0.0, 100.0, "x");
74  Assert.Equal(0.0, x.Lb());
75  Assert.Equal(100.0, x.Ub());
76 
77  Variable y = solver.MakeNumVar(0.0, 100.0, "y");
78  Assert.Equal(0.0, y.Lb());
79  Assert.Equal(100.0, y.Ub());
80 
81  Constraint ct1 = solver.Add(x + y == 1);
82  Assert.Equal(1.0, ct1.GetCoefficient(x));
83  Assert.Equal(1.0, ct1.GetCoefficient(y));
84 
85  Constraint ct2 = solver.Add(x + x == 1);
86  Assert.Equal(2.0, ct2.GetCoefficient(x));
87 
88  Constraint ct3 = solver.Add(x + (y + x) == 1);
89  Assert.Equal(2.0, ct3.GetCoefficient(x));
90  Assert.Equal(1.0, ct3.GetCoefficient(y));
91 
92  Constraint ct4 = solver.Add(x + (y + x + 3) == 1);
93  Assert.Equal(2.0, ct4.GetCoefficient(x));
94  Assert.Equal(1.0, ct4.GetCoefficient(y));
95  Assert.Equal(-2.0, ct4.Lb());
96  Assert.Equal(-2.0, ct4.Ub());
97  }
98 
99  [Fact]
100  public void VarMultiplication()
101  {
102  Solver solver = Solver.CreateSolver("CLP");
103  if (solver is null)
104  {
105  return;
106  }
107  Variable x = solver.MakeNumVar(0.0, 100.0, "x");
108  Assert.Equal(0.0, x.Lb());
109  Assert.Equal(100.0, x.Ub());
110 
111  Variable y = solver.MakeNumVar(0.0, 100.0, "y");
112  Assert.Equal(0.0, y.Lb());
113  Assert.Equal(100.0, y.Ub());
114 
115  Constraint ct1 = solver.Add(3 * x == 1);
116  Assert.Equal(3.0, ct1.GetCoefficient(x));
117 
118  Constraint ct2 = solver.Add(x * 3 == 1);
119  Assert.Equal(3.0, ct2.GetCoefficient(x));
120 
121  Constraint ct3 = solver.Add(x + (2 * y + 3 * x) == 1);
122  Assert.Equal(4.0, ct3.GetCoefficient(x));
123  Assert.Equal(2.0, ct3.GetCoefficient(y));
124 
125  Constraint ct4 = solver.Add(x + 5 * (y + x + 3) == 1);
126  Assert.Equal(6.0, ct4.GetCoefficient(x));
127  Assert.Equal(5.0, ct4.GetCoefficient(y));
128  Assert.Equal(-14.0, ct4.Lb());
129  Assert.Equal(-14.0, ct4.Ub());
130 
131  Constraint ct5 = solver.Add(x + (2 * y + x + 3) * 3 == 1);
132  Assert.Equal(4.0, ct5.GetCoefficient(x));
133  Assert.Equal(6.0, ct5.GetCoefficient(y));
134  Assert.Equal(-8.0, ct5.Lb());
135  Assert.Equal(-8.0, ct5.Ub());
136  }
137 
138  [Fact]
139  public void BinaryOperator()
140  {
141  Solver solver = Solver.CreateSolver("CLP");
142  if (solver is null)
143  {
144  return;
145  }
146  Variable x = solver.MakeNumVar(0.0, 100.0, "x");
147  Assert.Equal(0.0, x.Lb());
148  Assert.Equal(100.0, x.Ub());
149 
150  Variable y = solver.MakeNumVar(0.0, 100.0, "y");
151  Assert.Equal(0.0, y.Lb());
152  Assert.Equal(100.0, y.Ub());
153 
154  Constraint ct1 = solver.Add(x == y);
155  Assert.Equal(1.0, ct1.GetCoefficient(x));
156  Assert.Equal(-1.0, ct1.GetCoefficient(y));
157 
158  Constraint ct2 = solver.Add(x == 3 * y + 5);
159  Assert.Equal(1.0, ct2.GetCoefficient(x));
160  Assert.Equal(-3.0, ct2.GetCoefficient(y));
161  Assert.Equal(5.0, ct2.Lb());
162  Assert.Equal(5.0, ct2.Ub());
163 
164  Constraint ct3 = solver.Add(2 * x - 9 == y);
165  Assert.Equal(2.0, ct3.GetCoefficient(x));
166  Assert.Equal(-1.0, ct3.GetCoefficient(y));
167  Assert.Equal(9.0, ct3.Lb());
168  Assert.Equal(9.0, ct3.Ub());
169 
170  Assert.True(x == x);
171  Assert.True(!(x != x));
172  Assert.True((x != y));
173  Assert.True(!(x == y));
174  }
175 
176  [Fact]
177  public void Inequalities()
178  {
179  Solver solver = Solver.CreateSolver("CLP");
180  if (solver is null)
181  {
182  return;
183  }
184  Variable x = solver.MakeNumVar(0.0, 100.0, "x");
185  Assert.Equal(0.0, x.Lb());
186  Assert.Equal(100.0, x.Ub());
187 
188  Variable y = solver.MakeNumVar(0.0, 100.0, "y");
189  Assert.Equal(0.0, y.Lb());
190  Assert.Equal(100.0, y.Ub());
191 
192  Constraint ct1 = solver.Add(2 * (x + 3) + 5 * (y + x - 1) >= 3);
193  Assert.Equal(7.0, ct1.GetCoefficient(x));
194  Assert.Equal(5.0, ct1.GetCoefficient(y));
195  Assert.Equal(2.0, ct1.Lb());
196  Assert.Equal(double.PositiveInfinity, ct1.Ub());
197 
198  Constraint ct2 = solver.Add(2 * (x + 3) + 5 * (y + x - 1) <= 3);
199  Assert.Equal(7.0, ct2.GetCoefficient(x));
200  Assert.Equal(5.0, ct2.GetCoefficient(y));
201  Assert.Equal(double.NegativeInfinity, ct2.Lb());
202  Assert.Equal(2.0, ct2.Ub());
203 
204  Constraint ct3 = solver.Add(2 * (x + 3) + 5 * (y + x - 1) >= 3 - x - y);
205  Assert.Equal(8.0, ct3.GetCoefficient(x));
206  Assert.Equal(6.0, ct3.GetCoefficient(y));
207  Assert.Equal(2.0, ct3.Lb());
208  Assert.Equal(double.PositiveInfinity, ct3.Ub());
209 
210  Constraint ct4 = solver.Add(2 * (x + 3) + 5 * (y + x - 1) <= -x - y + 3);
211  Assert.Equal(8.0, ct4.GetCoefficient(x));
212  Assert.Equal(6.0, ct4.GetCoefficient(y));
213  Assert.Equal(double.NegativeInfinity, ct4.Lb());
214  Assert.Equal(2.0, ct4.Ub());
215  }
216 
217  [Fact]
218  public void SumArray()
219  {
220  Solver solver = Solver.CreateSolver("CLP");
221  if (solver is null)
222  {
223  return;
224  }
225 
226  Variable[] x = solver.MakeBoolVarArray(10, "x");
227  Constraint ct1 = solver.Add(x.Sum() == 3);
228  Assert.Equal(1.0, ct1.GetCoefficient(x[0]));
229 
230  Constraint ct2 = solver.Add(-2 * x.Sum() == 3);
231  Assert.Equal(-2.0, ct2.GetCoefficient(x[0]));
232 
233  LinearExpr[] array = new LinearExpr[] { x[0] + 2.0, x[0] + 3, x[0] + 4 };
234  Constraint ct3 = solver.Add(array.Sum() == 1);
235  Assert.Equal(3.0, ct3.GetCoefficient(x[0]));
236  Assert.Equal(-8.0, ct3.Lb());
237  Assert.Equal(-8.0, ct3.Ub());
238  }
239 
240  [Fact]
241  public void Objective()
242  {
243  Solver solver = Solver.CreateSolver("CLP");
244  if (solver is null)
245  {
246  return;
247  }
248  Variable x = solver.MakeNumVar(0.0, 100.0, "x");
249  Assert.Equal(0.0, x.Lb());
250  Assert.Equal(100.0, x.Ub());
251 
252  Variable y = solver.MakeNumVar(0.0, 100.0, "y");
253  Assert.Equal(0.0, y.Lb());
254  Assert.Equal(100.0, y.Ub());
255 
256  solver.Maximize(x);
257  Assert.Equal(0.0, solver.Objective().Offset());
258  Assert.Equal(1.0, solver.Objective().GetCoefficient(x));
259  Assert.True(solver.Objective().Maximization());
260 
261  solver.Minimize(-x - 2 * y + 3);
262  Assert.Equal(3.0, solver.Objective().Offset());
263  Assert.Equal(-1.0, solver.Objective().GetCoefficient(x));
264  Assert.Equal(-2.0, solver.Objective().GetCoefficient(y));
265  Assert.True(solver.Objective().Minimization());
266  }
267 
268  void SolveAndPrint(in Solver solver, in Variable[] variables, in Constraint[] constraints)
269  {
270  Console.WriteLine($"Number of variables = {solver.NumVariables()}");
271  Console.WriteLine($"Number of constraints = {solver.NumConstraints()}");
272 
273  Solver.ResultStatus resultStatus = solver.Solve();
274  // Check that the problem has an optimal solution.
275  if (resultStatus != Solver.ResultStatus.OPTIMAL)
276  {
277  Console.WriteLine("The problem does not have an optimal solution!");
278  }
279  else
280  {
281  Console.WriteLine("Solution:");
282  foreach (Variable var in variables)
283  {
284  Console.WriteLine($"{var.Name()} = {var.SolutionValue()}");
285  }
286  Console.WriteLine($"Optimal objective value = {solver.Objective().Value()}");
287  Console.WriteLine("");
288  Console.WriteLine("Advanced usage:");
289  Console.WriteLine($"Problem solved in {solver.WallTime()} milliseconds");
290  Console.WriteLine($"Problem solved in {solver.Iterations()} iterations");
291  foreach (Variable var in variables)
292  {
293  Console.WriteLine($"{var.Name()}: reduced cost {var.ReducedCost()}");
294  }
295 
296  double[] activities = solver.ComputeConstraintActivities();
297  foreach (Constraint ct in constraints)
298  {
299  Console.WriteLine($"{ct.Name()}: dual value = {ct.DualValue()}",
300  $" activity = {activities[ct.Index()]}");
301  }
302  }
303  }
304 
305  void RunLinearProgrammingExample(in String problemType)
306  {
307  Console.WriteLine($"------ Linear programming example with {problemType} ------");
308 
309  Solver solver = Solver.CreateSolver(problemType);
310  if (solver is null)
311  return;
312 
313  // x and y are continuous non-negative variables.
314  Variable x = solver.MakeNumVar(0.0, double.PositiveInfinity, "x");
315  Variable y = solver.MakeNumVar(0.0, double.PositiveInfinity, "y");
316 
317  // Objectif function: Maximize 3x + 4y.
318  Objective objective = solver.Objective();
319  objective.SetCoefficient(x, 3);
320  objective.SetCoefficient(y, 4);
321  objective.SetMaximization();
322 
323  // x + 2y <= 14.
324  Constraint c0 = solver.MakeConstraint(double.NegativeInfinity, 14.0, "c0");
325  c0.SetCoefficient(x, 1);
326  c0.SetCoefficient(y, 2);
327 
328  // 3x - y >= 0.
329  Constraint c1 = solver.MakeConstraint(0.0, double.PositiveInfinity, "c1");
330  c1.SetCoefficient(x, 3);
331  c1.SetCoefficient(y, -1);
332 
333  // x - y <= 2.
334  Constraint c2 = solver.MakeConstraint(double.NegativeInfinity, 2.0, "c2");
335  c2.SetCoefficient(x, 1);
336  c2.SetCoefficient(y, -1);
337 
338  SolveAndPrint(solver, new Variable[] { x, y }, new Constraint[] { c0, c1, c2 });
339  }
340  void RunMixedIntegerProgrammingExample(in String problemType)
341  {
342  Console.WriteLine($"------ Mixed integer programming example with {problemType} ------");
343 
344  Solver solver = Solver.CreateSolver(problemType);
345  if (solver == null)
346  return;
347 
348  // x and y are integers non-negative variables.
349  Variable x = solver.MakeIntVar(0.0, double.PositiveInfinity, "x");
350  Variable y = solver.MakeIntVar(0.0, double.PositiveInfinity, "y");
351 
352  // Objectif function: Maximize x + 10 * y.
353  Objective objective = solver.Objective();
354  objective.SetCoefficient(x, 1);
355  objective.SetCoefficient(y, 10);
356  objective.SetMaximization();
357 
358  // x + 7 * y <= 17.5.
359  Constraint c0 = solver.MakeConstraint(double.NegativeInfinity, 17.5, "c0");
360  c0.SetCoefficient(x, 1);
361  c0.SetCoefficient(y, 7);
362 
363  // x <= 3.5.
364  Constraint c1 = solver.MakeConstraint(double.NegativeInfinity, 3.5, "c1");
365  c1.SetCoefficient(x, 1);
366  c1.SetCoefficient(y, 0);
367 
368  SolveAndPrint(solver, new Variable[] { x, y }, new Constraint[] { c0, c1 });
369  }
370  void RunBooleanProgrammingExample(in String problemType)
371  {
372  Console.WriteLine($"------ Boolean programming example with {problemType} ------");
373 
374  Solver solver = Solver.CreateSolver(problemType);
375  if (solver == null)
376  return;
377 
378  // x and y are boolean variables.
379  Variable x = solver.MakeBoolVar("x");
380  Variable y = solver.MakeBoolVar("y");
381 
382  // Objectif function: Maximize 2 * x + y.
383  Objective objective = solver.Objective();
384  objective.SetCoefficient(x, 2);
385  objective.SetCoefficient(y, 1);
386  objective.SetMinimization();
387 
388  // 1 <= x + 2 * y <= 3.
389  Constraint c0 = solver.MakeConstraint(1, 3, "c0");
390  c0.SetCoefficient(x, 1);
391  c0.SetCoefficient(y, 2);
392 
393  SolveAndPrint(solver, new Variable[] { x, y }, new Constraint[] { c0 });
394  }
395 
396  [Fact]
397  public void OptimizationProblemType()
398  {
399  RunLinearProgrammingExample("GLOP");
400  RunLinearProgrammingExample("GLPK_LP");
401  RunLinearProgrammingExample("CLP");
402  RunLinearProgrammingExample("GUROBI_LP");
403 
404  RunMixedIntegerProgrammingExample("GLPK");
405  RunMixedIntegerProgrammingExample("CBC");
406  RunMixedIntegerProgrammingExample("SCIP");
407  RunMixedIntegerProgrammingExample("SAT");
408 
409  RunBooleanProgrammingExample("SAT");
410  RunBooleanProgrammingExample("BOP");
411  }
412 
413  [Fact]
414  static void testSetHintAndSolverGetters()
415  {
416  Console.WriteLine("testSetHintAndSolverGetters");
417  Solver solver = Solver.CreateSolver("glop");
418  // x and y are continuous non-negative variables.
419  Variable x = solver.MakeIntVar(0.0, double.PositiveInfinity, "x");
420  Variable y = solver.MakeIntVar(0.0, double.PositiveInfinity, "y");
421 
422  // Objectif function: Maximize x + 10 * y.
423  Objective objective = solver.Objective();
424  objective.SetCoefficient(x, 1);
425  objective.SetCoefficient(y, 10);
426  objective.SetMaximization();
427 
428  // x + 7 * y <= 17.5.
429  Constraint c0 = solver.MakeConstraint(double.NegativeInfinity, 17.5, "c0");
430  c0.SetCoefficient(x, 1);
431  c0.SetCoefficient(y, 7);
432 
433  // x <= 3.5.
434  Constraint c1 = solver.MakeConstraint(double.NegativeInfinity, 3.5, "c1");
435  c1.SetCoefficient(x, 1);
436  c1.SetCoefficient(y, 0);
437 
438  Constraint[] constraints = solver.constraints();
439  Assert.Equal(constraints.Length, 2);
440  Variable[] variables = solver.variables();
441  Assert.Equal(variables.Length, 2);
442 
443  solver.SetHint(new Variable[] { x, y }, new double[] { 2.0, 3.0 });
444  }
445 }
446 } // namespace Google.OrTools.Tests
Google.OrTools.LinearSolver.Solver.Add
Constraint Add(LinearConstraint constraint)
Definition: linear_solver/csharp/SolverHelper.cs:183