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