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 // Solves a constrained shortest path problem via Lagrangian Relaxation. The
15 // Lagrangian dual is solved with subgradient ascent.
16 //
17 // Problem data:
18 // * N: set of nodes.
19 // * A: set of arcs.
20 // * R: set of resources.
21 // * c_(i,j): cost of traversing arc (i,j) in A.
22 // * r_(i,j,k): resource k spent by traversing arc (i,j) in A, for all k in R.
23 // * b_i: flow balance at node i in N (+1 at the source, -1 at the sink, and 0
24 // otherwise).
25 // * r_max_k: availability of resource k for a path, for all k in R.
26 //
27 // Decision variables:
28 // * x_(i,j): flow through arc (i,j) in A.
29 //
30 // Formulation:
31 // Z = min sum(c_(i,j) * x_(i,j): (i,j) in A)
32 // s.t.
33 // sum(x_(i,j): (i,j) in A) - sum(x_(j,i): (j,i) in A) = b_i for all i in N,
34 // sum(r_(i,j,k) * x_(i,j): (i,j) in A) <= r_max_k for all k in R,
35 // x_(i,j) in {0,1} for all (i,j) in A.
36 //
37 // Upon dualizing a subset of the constraints (here we chose to relax some or
38 // all of the knapsack constraints), we obtaing a subproblem parameterized by
39 // dual variables mu (one per dualized constraint). We refer to this as the
40 // Lagrangian subproblem. Let R+ be the set of knapsack constraints that we
41 // keep, and R- the set of knapsack constraints that get dualized. The
42 // Lagrangian subproblem follows:
43 //
44 // z(mu) = min sum(
45 // (c_(i,j) - sum(mu_k * r_(i,j,k): k in R)) * x_(i,j): (i,j) in A)
46 // + sum(mu_k * r_max_k: k in R-)
47 // s.t.
48 // sum(x_(i,j): (i,j) in A) - sum(x_(j,i): (j,i) in A) = b_i for all i in N,
49 // sum(r_(i,j,k) * x_(i,j): (i,j) in A) <= r_max_k for all k in R+,
50 // x_(i,j) in {0,1} for all (i,j) in A.
51 //
52 // We seek to solve the Lagrangian dual, which is of the form:
53 // Z_D = max{ z(mu) : mu <=0 }. Concavity of z(mu) allows us to solve the
54 // Lagrangian dual with the iterates:
55 // mu_(t+1) = mu_t + step_size_t * grad_mu_t, where
56 // grad_mu_t = r_max - sum(t_(i,j) * x_(i,j)^t: (i,j) in A) is a subgradient of
57 // z(mu_t) and x^t is an optimal solution to the problem induced by z(mu_t).
58 //
59 // In general we have that Z_D <= Z. For convex problems, Z_D = Z. For MIPs,
60 // Z_LP <= Z_D <= Z, where Z_LP is the linear relaxation of the original
61 // problem.
62 //
63 // In this particular example, we use two resource constraints. Either
64 // constraint or both can be dualized via the flags `dualize_resource_1` and
65 // `dualize_resource_2`. If both constraints are dualized, we have that Z_LP =
66 // Z_D because the resulting Lagrangian subproblem can be solved as a linear
67 // program (i.e., the problem becomes a pure shortest path problem upon
68 // dualizing all the side constraints). When only one of the side constraints is
69 // dualized, we can have Z_LP <= Z_D because the resulting Lagrangian subproblem
70 // needs to be solved as an MIP. For the particular data used in this example,
71 // dualizing only the first resource constraint leads to Z_LP < Z_D, while
72 // dualizing only the second resource constraint leads to Z_LP = Z_D. In either
73 // case, solving the Lagrandual dual also provides an upper bound to Z.
74 //
75 // Usage: blaze build -c opt
76 // ortools/math_opt/examples:lagrangian_relaxation
77 // blaze-bin/ortools/math_opt/examples/lagrangian_relaxation
78
79 #include <math.h>
80
81 #include <algorithm>
82 #include <iostream>
83 #include <limits>
84 #include <memory>
85 #include <string>
86 #include <vector>
87
88 #include "absl/flags/flag.h"
89 #include "absl/flags/parse.h"
90 #include "absl/flags/usage.h"
91 #include "absl/memory/memory.h"
92 #include "absl/status/statusor.h"
93 #include "absl/strings/str_format.h"
94 #include "absl/strings/string_view.h"
95 #include "ortools/base/container_logging.h"
96 #include "ortools/base/logging.h"
97 #include "ortools/base/mathutil.h"
98 #include "ortools/math_opt/cpp/math_opt.h"
99
100 ABSL_FLAG(double, step_size, 0.95,
101 "Stepsize for gradient ascent, determined as step_size^t.");
102 ABSL_FLAG(int, max_iterations, 1000,
103 "Max number of iterations for gradient ascent.");
104 ABSL_FLAG(bool, dualize_resource_1, true,
105 "If true, the side constraint associated to resource 1 is dualized.");
106 ABSL_FLAG(bool, dualize_resource_2, false,
107 "If true, the side constraint associated to resource 2 is dualized.");
108
109 ABSL_FLAG(bool, lagrangian_output, false,
110 "If true, shows the iteration log of the subgradient ascent "
111 "procedure use to solve the Lagrangian problem");
112
113 constexpr double kZeroTol = 1.0e-8;
114
115 namespace {
116 using ::operations_research::MathUtil;
117 using ::operations_research::math_opt::LinearExpression;
118 using ::operations_research::math_opt::MathOpt;
119 using ::operations_research::math_opt::Result;
120 using ::operations_research::math_opt::SolveParametersProto;
121 using ::operations_research::math_opt::SolverType;
122 using ::operations_research::math_opt::Variable;
123 using ::operations_research::math_opt::VariableMap;
124
125 struct Arc {
126 int i;
127 int j;
128 double cost;
129 double resource_1;
130 double resource_2;
131 };
132
133 struct Graph {
134 int num_nodes;
135 std::vector<Arc> arcs;
136 int source;
137 int sink;
138 };
139
140 struct FlowModel {
FlowModel__anon60ee2b690111::FlowModel141 explicit FlowModel(SolverType solver_type) {
142 model = std::make_unique<MathOpt>(solver_type, "LagrangianProblem");
143 }
144 std::unique_ptr<MathOpt> model;
145 LinearExpression cost;
146 LinearExpression resource_1;
147 LinearExpression resource_2;
148 std::vector<Variable> flow_vars;
149 };
150
151 // Populates `model` with variables and constraints of a shortest path problem.
CreateShortestPathModel(const Graph graph)152 FlowModel CreateShortestPathModel(const Graph graph) {
153 FlowModel flow_model(operations_research::math_opt::SOLVER_TYPE_GSCIP);
154 MathOpt& model = *flow_model.model;
155 for (const Arc& arc : graph.arcs) {
156 Variable var = model.AddContinuousVariable(
157 /*lower_bound=*/0, /*upper_bound=*/1,
158 /*name=*/absl::StrFormat("x_%d_%d", arc.i, arc.j));
159 flow_model.cost += arc.cost * var;
160 flow_model.resource_1 += arc.resource_1 * var;
161 flow_model.resource_2 += arc.resource_2 * var;
162 flow_model.flow_vars.push_back(var);
163 }
164
165 // Flow balance constraints
166 std::vector<LinearExpression> out_flow(graph.num_nodes);
167 std::vector<LinearExpression> in_flow(graph.num_nodes);
168 for (int arc_index = 0; arc_index < graph.arcs.size(); ++arc_index) {
169 out_flow[graph.arcs[arc_index].i] += flow_model.flow_vars[arc_index];
170 in_flow[graph.arcs[arc_index].j] += flow_model.flow_vars[arc_index];
171 }
172 for (int node_index = 0; node_index < graph.num_nodes; ++node_index) {
173 int rhs = node_index == graph.source ? 1
174 : node_index == graph.sink ? -1
175 : 0;
176 model.AddLinearConstraint(out_flow[node_index] - in_flow[node_index] ==
177 rhs);
178 }
179
180 return flow_model;
181 }
182
CreateSampleNetwork()183 Graph CreateSampleNetwork() {
184 std::vector<Arc> arcs;
185 arcs.push_back(
186 {.i = 0, .j = 1, .cost = 12, .resource_1 = 1, .resource_2 = 1});
187 arcs.push_back(
188 {.i = 0, .j = 2, .cost = 3, .resource_1 = 2.5, .resource_2 = 1});
189 arcs.push_back(
190 {.i = 1, .j = 3, .cost = 5, .resource_1 = 1, .resource_2 = 1.5});
191 arcs.push_back(
192 {.i = 1, .j = 4, .cost = 5, .resource_1 = 2.5, .resource_2 = 1});
193 arcs.push_back(
194 {.i = 2, .j = 1, .cost = 7, .resource_1 = 2.5, .resource_2 = 1});
195 arcs.push_back(
196 {.i = 2, .j = 3, .cost = 5, .resource_1 = 7, .resource_2 = 2.5});
197 arcs.push_back(
198 {.i = 2, .j = 4, .cost = 1, .resource_1 = 6.5, .resource_2 = 1});
199 arcs.push_back(
200 {.i = 3, .j = 5, .cost = 6, .resource_1 = 1, .resource_2 = 2.0});
201 arcs.push_back(
202 {.i = 4, .j = 3, .cost = 3, .resource_1 = 1, .resource_2 = 0.5});
203 arcs.push_back(
204 {.i = 4, .j = 5, .cost = 5, .resource_1 = 2.5, .resource_2 = 1});
205 const Graph graph = {.num_nodes = 6, .arcs = arcs, .source = 0, .sink = 5};
206
207 return graph;
208 }
209
210 // Solves the constrained shortest path as an MIP.
SolveMip(const Graph graph,const double max_resource_1,const double max_resource_2)211 FlowModel SolveMip(const Graph graph, const double max_resource_1,
212 const double max_resource_2) {
213 FlowModel flow_model(operations_research::math_opt::SOLVER_TYPE_GSCIP);
214 MathOpt& model = *flow_model.model;
215 for (const Arc& arc : graph.arcs) {
216 Variable var = model.AddBinaryVariable(
217 /*name=*/absl::StrFormat("x_%d_%d", arc.i, arc.j));
218 flow_model.cost += arc.cost * var;
219 flow_model.resource_1 += +arc.resource_1 * var;
220 flow_model.resource_2 += arc.resource_2 * var;
221 flow_model.flow_vars.push_back(var);
222 }
223
224 // Flow balance constraints
225 std::vector<LinearExpression> out_flow(graph.num_nodes);
226 std::vector<LinearExpression> in_flow(graph.num_nodes);
227 for (int arc_index = 0; arc_index < graph.arcs.size(); ++arc_index) {
228 out_flow[graph.arcs[arc_index].i] += flow_model.flow_vars[arc_index];
229 in_flow[graph.arcs[arc_index].j] += flow_model.flow_vars[arc_index];
230 }
231 for (int node_index = 0; node_index < graph.num_nodes; ++node_index) {
232 int rhs = node_index == graph.source ? 1
233 : node_index == graph.sink ? -1
234 : 0;
235 model.AddLinearConstraint(out_flow[node_index] - in_flow[node_index] ==
236 rhs);
237 }
238
239 model.AddLinearConstraint(flow_model.resource_1 <= max_resource_1,
240 "resource_ctr_1");
241 model.AddLinearConstraint(flow_model.resource_2 <= max_resource_2,
242 "resource_ctr_2");
243 model.objective().Minimize(flow_model.cost);
244 SolveParametersProto params;
245 params.mutable_common_parameters()->set_enable_output(false);
246 const Result result = model.Solve(params).value();
247 const VariableMap<double>& variable_values = result.variable_values();
248 std::cout << "MIP Solution with 2 side constraints" << std::endl;
249 std::cout << absl::StrFormat("MIP objective value: %6.3f",
250 result.objective_value())
251 << std::endl;
252 std::cout << "Resource 1: " << flow_model.resource_1.Evaluate(variable_values)
253 << std::endl;
254 std::cout << "Resource 2: " << flow_model.resource_2.Evaluate(variable_values)
255 << std::endl;
256 std::cout << "========================================" << std::endl;
257 return flow_model;
258 }
259
260 // Solves the linear relaxation of a constrained shortest path problem
261 // formulated as an MIP.
SolveLinearRelaxation(FlowModel & flow_model,const Graph & graph,const double max_resource_1,const double max_resource_2)262 void SolveLinearRelaxation(FlowModel& flow_model, const Graph& graph,
263 const double max_resource_1,
264 const double max_resource_2) {
265 MathOpt& model = *flow_model.model;
266 SolveParametersProto params;
267 params.mutable_common_parameters()->set_enable_output(false);
268 const Result result = model.Solve(params).value();
269 const VariableMap<double>& variable_values = result.variable_values();
270 std::cout << "LP relaxation with 2 side constraints" << std::endl;
271 std::cout << absl::StrFormat("LP objective value: %6.3f",
272 result.objective_value())
273 << std::endl;
274 std::cout << "Resource 1: " << flow_model.resource_1.Evaluate(variable_values)
275 << std::endl;
276 std::cout << "Resource 2: " << flow_model.resource_2.Evaluate(variable_values)
277 << std::endl;
278 std::cout << "========================================" << std::endl;
279 }
280
SolveLagrangianRelaxation(const Graph graph,const double max_resource_1,const double max_resource_2)281 void SolveLagrangianRelaxation(const Graph graph, const double max_resource_1,
282 const double max_resource_2) {
283 // Model, variables, and linear expressions.
284 FlowModel flow_model = CreateShortestPathModel(graph);
285 MathOpt& model = *flow_model.model;
286 LinearExpression& cost = flow_model.cost;
287 LinearExpression& resource_1 = flow_model.resource_1;
288 LinearExpression& resource_2 = flow_model.resource_2;
289 SolveParametersProto params;
290 params.mutable_common_parameters()->set_enable_output(false);
291
292 // Dualized constraints and dual variable iterates.
293 std::vector<double> mu;
294 std::vector<LinearExpression> grad_mu;
295 const bool dualized_resource_1 = absl::GetFlag(FLAGS_dualize_resource_1);
296 const bool dualized_resource_2 = absl::GetFlag(FLAGS_dualize_resource_2);
297 const bool lagrangian_output = absl::GetFlag(FLAGS_lagrangian_output);
298 CHECK(dualized_resource_1 || dualized_resource_2)
299 << "At least one of the side constraints should be dualized.";
300
301 // Modify the lagrangian problem according to the constraints that are
302 // dualized. We use a initial dual value different from zero to prioritize
303 // finding a feasible solution.
304 const double initial_dual_value = -10;
305 if (dualized_resource_1 && !dualized_resource_2) {
306 mu.push_back(initial_dual_value);
307 grad_mu.push_back(max_resource_1 - resource_1);
308 model.AddLinearConstraint(resource_2 <= max_resource_2);
309 for (Variable& var : flow_model.flow_vars) {
310 var.set_integer();
311 }
312 } else if (!dualized_resource_1 && dualized_resource_2) {
313 mu.push_back(initial_dual_value);
314 grad_mu.push_back(max_resource_2 - resource_2);
315 model.AddLinearConstraint(resource_1 <= max_resource_1);
316 for (Variable& var : flow_model.flow_vars) {
317 var.set_integer();
318 }
319 } else {
320 mu.push_back(initial_dual_value);
321 mu.push_back(initial_dual_value);
322 grad_mu.push_back(max_resource_1 - resource_1);
323 grad_mu.push_back(max_resource_2 - resource_2);
324 }
325
326 // Gradient ascent setup
327 bool termination = false;
328 int iterations = 1;
329 const double step_size = absl::GetFlag(FLAGS_step_size);
330 CHECK_GT(step_size, 0) << "step_size must be strictly positive";
331 CHECK_LT(step_size, 1) << "step_size must be strictly less than 1";
332 const int max_iterations = absl::GetFlag(FLAGS_max_iterations);
333 CHECK_GT(max_iterations, 0)
334 << "Number of iterations must be strictly positive.";
335
336 // Upper and lower bounds on the full problem.
337 double upper_bound = std::numeric_limits<double>().infinity();
338 double lower_bound = -std::numeric_limits<double>().infinity();
339 double best_solution_resource_1 = 0;
340 double best_solution_resource_2 = 0;
341
342 if (lagrangian_output) {
343 std::cout << "Starting gradient ascent..." << std::endl;
344 std::cout << absl::StrFormat("%4s %6s %6s %9s %10s %10s", "Iter", "LB",
345 "UB", "Step size", "mu_t", "grad_mu_t")
346 << std::endl;
347 }
348
349 while (!termination) {
350 LinearExpression lagrangian_function;
351 lagrangian_function += cost;
352 for (int k = 0; k < mu.size(); ++k) {
353 lagrangian_function += mu[k] * grad_mu[k];
354 }
355 model.objective().Minimize(lagrangian_function);
356 Result result = model.Solve(params).value();
357 const VariableMap<double>& vars_val = result.variable_values();
358 bool feasible = true;
359
360 // Iterate update. Takes a step in the direction of the gradient (since the
361 // Lagrangian dual is a max problem), and projects onto {mu: mu <=0} to
362 // satisfy the sign of the dual variable. In general, convergence to an
363 // optimal solution requires diminishing step sizes satisfying:
364 // * sum(step_size_t: t=1...) = infinity and,
365 // * sum((step_size_t)^2: t=1...) < infinity
366 // See details in Prop 3.2.6 Bertsekas 2015, Convex Optimization Algorithms.
367 // Here we use step_size_t = step_size^t which does NOT satisfy the
368 // first condition, but is good enough for the purpose of this example.
369 std::vector<double> grad_mu_vals;
370 const double step_size_t = MathUtil::IPow(step_size, iterations);
371 for (int k = 0; k < mu.size(); ++k) {
372 // Evaluate resource k and evaluate the gradient of z(mu).
373 const double grad_mu_val = grad_mu[k].Evaluate(vars_val);
374 grad_mu_vals.push_back(grad_mu_val);
375 mu[k] = std::min(0.0, mu[k] + step_size_t * grad_mu_val);
376 if (grad_mu_val < 0) {
377 feasible = false;
378 }
379 }
380 // Bounds update
381 const double path_cost = cost.Evaluate(vars_val);
382 if (feasible && path_cost < upper_bound) {
383 best_solution_resource_1 = resource_1.Evaluate(vars_val);
384 best_solution_resource_2 = resource_2.Evaluate(vars_val);
385 if (lagrangian_output) {
386 std::cout << "Feasible solution with"
387 << absl::StrFormat(
388 "cost=%4.2f, resource_1=%4.2f, and resource_2=%4.2f. ",
389 path_cost, best_solution_resource_1,
390 best_solution_resource_2)
391 << std::endl;
392 }
393 upper_bound = path_cost;
394 }
395 if (lower_bound < result.objective_value()) {
396 lower_bound = result.objective_value();
397 }
398
399 if (lagrangian_output) {
400 std::cout << absl::StrFormat("%4d %6.3f %6.3f %9.3f", iterations,
401 lower_bound, upper_bound, step_size_t)
402 << " " << gtl::LogContainer(mu) << " "
403 << gtl::LogContainer(grad_mu_vals) << std::endl;
404 }
405
406 // Termination criteria
407 double norm = 0;
408 for (double value : grad_mu_vals) {
409 norm += (value * value);
410 }
411 norm = sqrt(norm);
412 if (iterations == max_iterations || lower_bound == upper_bound ||
413 step_size_t * norm < kZeroTol) {
414 termination = true;
415 }
416 iterations++;
417 }
418
419 std::cout << "Lagrangian relaxation with 2 side constraints" << std::endl;
420 std::cout << "Constraint for resource 1 dualized: "
421 << (dualized_resource_1 ? "true" : "false") << std::endl;
422 std::cout << "Constraint for resource 2 dualized: "
423 << (dualized_resource_2 ? "true" : "false") << std::endl;
424 std::cout << absl::StrFormat("Lower bound: %6.3f", lower_bound) << std::endl;
425 std::cout << absl::StrFormat("Upper bound: %6.3f (Integer solution)",
426 upper_bound)
427 << std::endl;
428 std::cout << "========================================" << std::endl;
429 }
430
RelaxModel(FlowModel & flow_model)431 void RelaxModel(FlowModel& flow_model) {
432 for (Variable& var : flow_model.flow_vars) {
433 var.set_continuous();
434 var.set_lower_bound(0.0);
435 var.set_upper_bound(1.0);
436 }
437 }
438
SolveFullModel(const Graph & graph,double max_resource_1,double max_resource_2)439 void SolveFullModel(const Graph& graph, double max_resource_1,
440 double max_resource_2) {
441 FlowModel flow_model = SolveMip(graph, max_resource_1, max_resource_2);
442 RelaxModel(flow_model);
443 SolveLinearRelaxation(flow_model, graph, max_resource_1, max_resource_2);
444 }
445
446 } // namespace
447
main(int argc,char ** argv)448 int main(int argc, char** argv) {
449 google::InitGoogleLogging(argv[0]);
450 absl::ParseCommandLine(argc, argv);
451
452 // Problem data
453 const Graph graph = CreateSampleNetwork();
454 const double max_resource_1 = 10;
455 const double max_resource_2 = 4;
456
457 SolveFullModel(graph, max_resource_1, max_resource_2);
458
459 SolveLagrangianRelaxation(graph, max_resource_1, max_resource_2);
460 return 0;
461 }
462