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