Fundamentals of Supply Chain Theory, 2nd Edition

Appendix D Integer Optimization Techniques

In this appendix, we provide a brief overview of two optimization techniques that are used repeatedly in this book: Lagrangian relaxation and column generation.

D.1 Lagrangian Relaxation

D.1.1 Overview

Consider an optimization problem of the form

(D.1)

(D.2)

(D.3)

(D.4)

Here, x is a vector of decision variables, b, c, and e are vectors of coefficients, and A and D are matrices. (It's not necessary that all of the x variables be binary; some or all can be continuous.) Suppose that (P) itself is hard to solve, but that the problem obtained by omitting constraints (D.2) is easier. In this section, we discuss Lagrangian relaxation, a method that is well suited to solve problems like this one. Similar approaches can also be applied to other types of problems, such as nonlinear programming problems.

There are many sources of additional information about Lagrangian relaxation in journal articles and textbooks; among the most user‐friendly treatments are the articles by Fisher (1981,1985).

The idea behind Lagrangian ...