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 // Integer programming example that shows how to use the API.
15
16 #include "absl/flags/parse.h"
17 #include "absl/flags/usage.h"
18 #include "absl/strings/match.h"
19 #include "absl/strings/string_view.h"
20 #include "ortools/base/logging.h"
21 #include "ortools/linear_solver/linear_solver.h"
22
23 namespace operations_research {
RunIntegerProgrammingExample(absl::string_view solver_id)24 void RunIntegerProgrammingExample(absl::string_view solver_id) {
25 LOG(INFO) << "---- Integer programming example with " << solver_id << " ----";
26
27 MPSolver::OptimizationProblemType problem_type;
28 if (!MPSolver::ParseSolverType(solver_id, &problem_type)) {
29 LOG(INFO) << "Solver id " << solver_id << " not recognized";
30 return;
31 }
32
33 if (!MPSolver::SupportsProblemType(problem_type)) {
34 LOG(INFO) << "Supports for solver " << solver_id << " not linked in.";
35 return;
36 }
37
38 MPSolver solver("IntegerProgrammingExample", problem_type);
39
40 const double infinity = solver.infinity();
41 // x and y are integer non-negative variables.
42 MPVariable* const x = solver.MakeIntVar(0.0, infinity, "x");
43 MPVariable* const y = solver.MakeIntVar(0.0, infinity, "y");
44
45 // Maximize x + 10 * y.
46 MPObjective* const objective = solver.MutableObjective();
47 objective->SetCoefficient(x, 1);
48 objective->SetCoefficient(y, 10);
49 objective->SetMaximization();
50
51 // x + 7 * y <= 17.5.
52 MPConstraint* const c0 = solver.MakeRowConstraint(-infinity, 17.5);
53 c0->SetCoefficient(x, 1);
54 c0->SetCoefficient(y, 7);
55
56 // x <= 3.5
57 MPConstraint* const c1 = solver.MakeRowConstraint(-infinity, 3.5);
58 c1->SetCoefficient(x, 1);
59 c1->SetCoefficient(y, 0);
60
61 LOG(INFO) << "Number of variables = " << solver.NumVariables();
62 LOG(INFO) << "Number of constraints = " << solver.NumConstraints();
63
64 const MPSolver::ResultStatus result_status = solver.Solve();
65 // Check that the problem has an optimal solution.
66 if (result_status != MPSolver::OPTIMAL) {
67 LOG(FATAL) << "The problem does not have an optimal solution!";
68 }
69 LOG(INFO) << "Solution:";
70 LOG(INFO) << "x = " << x->solution_value();
71 LOG(INFO) << "y = " << y->solution_value();
72 LOG(INFO) << "Optimal objective value = " << objective->Value();
73 LOG(INFO) << "";
74 LOG(INFO) << "Advanced usage:";
75 LOG(INFO) << "Problem solved in " << solver.wall_time() << " milliseconds";
76 LOG(INFO) << "Problem solved in " << solver.iterations() << " iterations";
77 LOG(INFO) << "Problem solved in " << solver.nodes()
78 << " branch-and-bound nodes";
79 }
80
RunAllExamples()81 void RunAllExamples() {
82 RunIntegerProgrammingExample("CBC");
83 RunIntegerProgrammingExample("SAT");
84 RunIntegerProgrammingExample("SCIP");
85 RunIntegerProgrammingExample("GUROBI");
86 RunIntegerProgrammingExample("GLPK");
87 RunIntegerProgrammingExample("CPLEX");
88 }
89 } // namespace operations_research
90
main(int argc,char ** argv)91 int main(int argc, char** argv) {
92 absl::SetFlag(&FLAGS_alsologtostderr, true);
93 google::InitGoogleLogging(argv[0]);
94 absl::ParseCommandLine(argc, argv);
95 operations_research::RunAllExamples();
96 return EXIT_SUCCESS;
97 }
98