Because the combination of relaxations and heuristics provide the only reasonable approach for optimally (or near optimally) solving hard problems, there has been a lot of work put into finding better relaxations for problems. The examples given above for the traveling salesman problem represent some problem specific relaxations. You already know of one very general relaxation technique: formulate the problem as an integer program and then solve the corresponding linear program. This is known as the linear relaxation.
Example: Consider the knapsack problem:
Maximize 
Subject to
for all i
The linear relaxation to this is simply:
Maximize
Subject to
for all i
The solution to this is 
for a value of
19.5. No feasible knapsack can have value more than 19.5 (remember we
are maximizing, so the relaxation provides an upper bound).
We would like to find the strongest relaxations possible. There are a couple of techniques used to find strong relaxations. These are lagrangian relaxation and cutting planes. Before I talk about these techniques, let me talk about some work I am doing for the Navy Personnel Department.
Every year, the Navy must make thousands of job assignments based on readiness requirements, asset utilization, and job rotation. These assignments are made by a group called detailers. Each detailer is responsible for a group of people (called sailors in this proposal, but encompassing a variety of occupations) and attempt to match the Navy's needs with each sailor's personal needs and objectives.
In the past, these assignments have been made on an ad-hoc basis where assignments are based on individual negotiations. The detailer had complete flexibility in trading off the Navy's goals and assets. This can easily lead to very poor solutions where the Navy's goals are not being met even when the assets (such as the moving budget) are overutilized. One facet of this problem is a chronic lack of funds at the end of a fiscal year, resulting in very poor assignments.
One alternative to this approach is to formulate and solve a large mathematical program to determine the optimal assignments. This too has great difficulties because the needs of the sailors are not met, resulting in low morale and low reenlistment rates.
The objective of this research to determine a mechanism so that the detailers will have the flexibility in offering sailors a variety of jobs but the Navy's goals will be met and its assets effectively utilized.
Let me now formalize some of these concepts. The detailer's problem over a period (generally a year) is as follows:
and 
are
feasible (written 
), based on such aspects as when the job
is available and certain skill requirements.
for 
. These might represent the moving fund budget,
fleet balance constraints, readiness requirements, and so on.
for each asset . Each assignment also has a cost
representing the hard, measurable costs of the assignment.
This leads to the mathematical optimization problem:
Minimize 
Subject to
for all i
for all j
for all k
for all .
The first constraint states that every person shall be assigned a job. The second constraint says that every job has at most one person assigned to it. The third constraint implements the asset limitations, while the final integrality constraints ensure a well defined assignment.
We know, of course, very fast ways of solving the assignment problem (without the asset limitations). Such methods, based on network optimization approaches, naturally provide integer solutions. How can we approach this problem with asset limitations?