Another important constraint is that all x j have to be non-negative. This seems obvious to us, for there can never be a negative number of patterns. Since integer linear programs are difficult to solve, we will relax the problem to first consider a fractional solution. Once we have obtain the fractional solution, we can apply an integer programming algorithm to remove the fractional portion. Now we have a linear programming problem to solve.
Linear programs are common optimization problems.
Fortunately there are good techniques for solving them. One method is the simplex method which starts from some nonoptimal point and iteratively finds better and better solutions. The algorithm concludes with the optimal solution when no steps can be made to improve the solution. There is one problem to our formulation so far. We first created all possible patterns that might be cut from a roll.