Although the above is useful, and used, in some sense we are not doing anything new. We are simply mimicking the simplex algorithm, separating out its rule to find a variable to enter the basis. Sometimes, it is possible to come up with very specialized variable entry rules, which permits the solution of problems with billions of variables.
The following is a description of the classic cutting stock problem. I actually used the notions here as a subroutine in a project for scheduling a cardboard cutting machine in Canada.
We begin with a paper (or textile, or steel) company. This company has a number of wide rolls of paper. These rolls are cut into smaller rolls (called pieces) to meet customer (or internal) orders. If the size of the roll does not exactly equal the sum of the pieces, there is some waste (or trim loss). The company would like to minimize this waste (or equivalently, the number of rolls used).
To simplify matters, suppose we have one stock width (say, 500 cm). There are orders for pieces from 20 cm to 200 cm wide (all in multiples of 5 cm).
The first step is to formulate this problem. One not so obvious model
is to write the model in terms of cutting patterns. A cutting pattern
is a feasible division of the roll into pieces. For instance, one
pattern is 5 pieces of 50 cm, 1 of 150 cm, and 1 of 80, leaving 20 cm
waste. In this example, there are billions of patterns. Leaving
aside the problem of calculating all these patterns for the moment,
suppose we let 
be the number of times pattern j is used.
Suppose the demand for width i is 
, and pattern j makes
pieces of width i. The formulation then is:
Minimize 
Subject to
for all i
and integer.
As long as the are large enough it is not unreasonable to drop
the integrality restrictions and simply round the resulting solution.
How can we solve this linear program with billions and billions of variables? Well, as long as you haven't been asleep, you know the answer is via variable generation. Here though, there are far too many variables to let us simply check each one. We are going to have to be more clever.
Let's take a simple, specific example. This example is small enough that we could manage by enumerating all patterns, but I want to illustrate a different concept.
Suppose the roll is 17 units wide, and the demands for pieces of width 3, 5, and 9 are 25, 20 and 15 respectively. How can we minimize the number of rolls used to meet demand?
We begin with a limited portfolio of patterns. Suppose we begin with the following three patterns:
1) 5 pieces of width 3
2) 3 pieces of width 5
3) 1 piece of width 9
Let the variables associated with these three patterns be 
respectively. Our linear program with just these patterns is:
Minimize 
Subject to
which has optimal solution 
and 
for a
total of 26.667. The duals are 1/5, 1/3, and 1. We would like to
determine if there is a better pattern to add to our linear program.
Consider the effect of adding one roll of a pattern with 
pieces
of width 3, 
of width 5, and 
of width 9. What will this do
to the objective? First, it will cost us 1 in the objective function.
But it will also save us 
, because 1/5 is the marginal saving
of one unit on the righthandside of constraint one. Similarly, it
will save 
due to constraint two, and due to constraint
3. Therefore, the net cost is 
. If the net cost
is negative, then we have a cutting pattern that is worth considering.
For instance, consider the pattern of cutting 2 pieces of width three and 2 of width 5. The net cost is 1-2/5-2/3 ;SPMlt; 0 so this pattern is worth considering.
But what is the best pattern to consider? Which gives us the most profit? We can solve this problem by solving the following subproblem:
Maximize 
Subject to
and integer.
This problem is the knapsack problem. With some luck, you know how to solve knapsack problems with dynamic programming. Otherwise, it is only important to know that the knapsack problem is relatively easy to solve as long as the numbers are not too big (so LINDO will solve these integer programs quickly).
The optimal solution is 
, and 
with objective
8/15. Therefore, this pattern is the most profitable to add to the
formulation. Call the variable associated with this pattern 
.
Our formulation is now:
Minimize 
Subject to
The optimal solution to this is 
with duals
1/5, 1/3, and 7/15. Notice that we have reduced the objective from
26.667 to 18.667. As an exercise, now give a pattern that would not
be attractive to add to the solution (2 of width three and 1 of width
9 is one).
To determine if there is another good pattern to add, solve the following knapsack problem:
Maximize 
Subject to
and integer.
The optimal solution to this is 
with value
2/15. This is pattern 
. We add this pattern to our problem and
reoptimize. The solution is 
with value
just under 18.5. The dual values are 1/6, 1/3, and 1/2. This gives a
new knapsack problem:
Maximize 
Subject to
and integer.
which has value 0. Therefore, there are no good patterns
left, and we are done. The best linear solution is which can be rounded up to 
for 19
rolls used (which must be optimal (why?)).
There are a number of important things to notice here, even in this small example. We did not need to enumerate all patterns, and we did not examine the majority of patterns at all. Also, we could stop this process at any time and say that this is as good as we could get (this is an extremely nice property to have). Finally, we do have to solve an integer program (albeit a ``nice'' one) at each step. But remember, we couldn't even come up with a nice formulation initially.