Relaxation

How do we attack integer optimization problems? The first step is to relax. No, I don’t mean you should close your eyes and chant your mantra (although nothing is stopping you from doing so, either). In operations research, relaxation means that we loosen or eliminate some of the constraints and see if the modified problem has an easy (or at least easier) solution that gives us some information about the solution to our original problem. 

[In fact, as others have noted, this is a general life lesson as well. When we feel stuck on some big issue, we are told to imagine that something we feel is holding us back is no longer a constraint. (“What if money were no object?” “What if you could have any job you wanted?”) The trick is to relax just enough that we learn something, yet still close enough to reality to be relevant. (As opposed to, for instance, “What if we had magic powers and could fly?”)]

Linear Relaxation

The most common form of relaxation for discrete optimization problems is to ignore the requirement that the solution be an integer, thus converting the problem back to the type of linear program we’ve been studying up until now. This is called the “linear relaxation,” and it is often useful as a starting point for further analysis.

For instance, say we own a spa and we’re thinking of adding some new massage stations and sauna rooms. We have 200 square feet of available space and $40,000 to spend.

Each massage station \(x_m\) costs $8,000 for the equipment, insurance and personnel; takes up 15 sq. ft. of floor space; and will add $100 to our daily profit. Each sauna room \(x_s\) costs $4,000 to build, takes up 30 sq. ft. of space, and is estimated to add $150 profit per day. Our linear programming problem is thus:

\begin{aligned} \max_{x_i} \quad & 100 x_m + 150 x_s\\ \textrm{s.t.}\quad & 8x_m+4x_s\leq 40 \\ \quad & 15x_m+30x_s\leq 200 \\ & x_m,x_s\geq 0 \textrm{ and integer} \\ \end{aligned}

Run this through the simplex algorithm and you will get a global optimum with \(x_m=2.22\), \(x_s=5.55\), and an objective value of $1,056. If we remove the fractional parts of the solutions, so that \(x_m=2\) and \(x_s=5\), our profit becomes $950.

With only this, we know a fair bit about the solution to the original integer-valued problem. First, we have an upper bound of \$1,055, so any possible solution that purports to give us greater profits than this must be infeasible. 

Similarly, we know of at least one feasible solution that gives us \$950 in profit, so anything that gives us less than that can also be discarded immediately. (This will be of great value when we discuss branch and bound below.)

Finally, we have a bit of perspective on what we can expect overall. If we find a solution that yields \$1,000 in profit, we’ll probably want to keep looking. But if we find one that gives us \$1,054, we can quit if we like, knowing that we are less than 1% away from the optimum.

I should add, though, that there is one thing we cannot infer. It may be tempting to assume that since the optimal number of massage stations lies between 2 and 3, and the optimal number of sauna rooms lies between 5 and 6, then the best integer solution must comprise some combination of these four values. But this is not the case in general (which makes solving these problems all the more difficult.) 

In the present problem, in fact the optimal integer solution has \(x_m=2\) and \(x_s=5\). But if we change the per-sauna profit from \$150 to \$175 then the solution to the simplex problem remains the same but, as the reader can verify, the optimal integer solution becomes \(x_m=1\) and \(x_s=6\).

Lagrangean Relaxation

Another useful approach, called Lagrangean Relaxation, asks whether those things you call constraints are really so absolute. Instead of requiring, for instance, that all tables at a wedding reception have the same number of people sitting at them, we can allow our plans to deviate from equality and then impose a penalty on any scheme that does so. 

This means that we will be moving expressions from the list of constraints to the objective function. Instead of requiring \(x+3y\leq 5\), for example, we can remove this constraint and add the expression \(-M(5-(x+3y))\) to the quantity we’re trying to maximize, where M is some large number.

This should give you a feeling for how, in a relaxation regime, the boundaries of our problems become much more fluid. In fact, this is how the schedule for Major League Baseball is created. Many people think that, for instance, the New York Yankees and the New York Mets never play home games on the same day. This is true in general, but a few times each season this “rule” is broken in service of other scheduling considerations.