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