each other (both in terms of width and length). Therefore, there are similarities with the multi-machine problem mentioned above. The presence of length variations creates a 2-D problem, because waste can occur both width-wise and length-wise. The guillotine problem is another 2-D problem of cutting sheets into rectangles of specified sizes, however only cuts that continue all the way across each sheet are allowed. Industrial applications of this problem can be found in the glass industry. The cutting stock problem of determining, for the one-dimensional case, the best master size that will meet given demand is known as the assortment problem. History The cutting stock problem was first formulated by Kantorovich in 1939. In 1951 before computers became widely available, L. V. Kantorovich and V. A. Zalgaller suggested solving the problem of the economical use of material at the cutting stage with the help of linear programming. The proposed technique was later called the column generation method. Mathematical formulation and solution approaches The standard formulation for the cutting-stock problem (but not the only one) starts with a list of m orders, each requiring pieces, where . We then construct a list of all possible combinations of cuts (often called "patterns" or "configurations"). Let be the number of those patterns. We associate with each pattern a positive integer variable , representing how many times pattern is to be used, where . The linear integer program is then: , integer where is the number of times order appears in pattern and is the cost (often the waste) of pattern . The precise nature of the quantity constraints can lead to subtly different mathematical characteristics. The above formulation's quantity constraints are minimum constraints (at least the given amount of each order must be produced, but possibly more). When , the objective minimises the number of utilised master items and, if the constraint for the quantity to be produced is replaced by equality, it is called the bin packing problem. The most general formulation has two-sided constraints (and in this case a minimum-waste solution may consume more than the minimum number of master items): This formulation applies not just to one-dimensional problems. Many variations are possible, including one where the objective is not to minimise the waste, but to maximise the total value of the produced items, allowing each order to have a different value. In general, the number of possible patterns grows exponentially