Cutting stock problem

The one-dimensional cutting problem ( engl. one- dimensional cutting stock problem) is a heavy - integer linear optimization problem with the goal of one-dimensional parts to tailor a given length at predetermined requirement figures from as little pieces of material. This problem owes its great importance and the fact that it is used as a relaxation for complex multi-dimensional packing and cutting problems, for example the container loading problem with hewn stone, when all the parts you think is divided into strips.

Problem statement and basic definitions

Given an unlimited number of pieces of one-dimensional raw material of predetermined length. As a part of the length to be cut with; a total parts. For as few pieces of raw material to be consumed. Leftovers can not be connected together and count as waste. Are the required numbers very small, one also speaks of ( one-dimensional ) container problem (bin packing problem).

Immediate applications include the cutting of pipes or the storage of non- divisible and not compressible files on as few volumes as uniform capacity. The generalization to several different lengths of raw material will be covered later.

If a certain section width are taken into account, this is possible by all lengths, ie and () be increased by. Thus, the problem is attributed to a cutting width of 0.

First, the lengths and the required numbers are ( for ) to vectors and summarized. The summary of all data to an instance occurs as quad. Here, the term always means a problem class problem, while only with concrete data exists one instance.

A blank version is a vector of non-negative integers indicating how many times each part in this variant. The variant is exactly admissible if

Applies. The index set of all admissible variations is denoted by. This is the integer linear optimization problem:

This problem is always solvable if and only if for all parts of lengths, since the objective function ( 2) is bounded from below and accepts only integer values and a feasible solution exists to manufacture about each piece starting material only a part. The need to be cropped parts of all types will be covered due to the condition (3). If we replace in it the equal sign by ≥, creates a model for ( 2) - ( 4) equivalent, because you can cut out variants that lead to overproduction, let out individual parts. In this way is obtained from a optimal solution of the modified problem, one for the problem ( 2) - ( 4) with the same objective function value.

As the number of permissible variations and thus the variables in the problem (2 ) - (4 ) is often very large, was also looking for alternative models. Such is, inter alia, in the formulation as an optimization of a flow in a network. That flow model turns out to be equivalent to the above problem formulation. For details, we refer to eg.

An admissible cut variant is actually called, if true, that is the variant used alone again, no over-production supplies. Obviously rich actual variants of solving the problem (2) - from (4).

The problem is -difficult, because even the question of whether all parts can be cut from only two pieces of source material, carries on the knapsack problem, and this is -complete. According to the one-dimensional bin packing problem is even strongly -complete. Despite this unfavorable complexity optimal solutions can be determined for many instances in a reasonable time, for example by means of suitable heuristics. To evaluate the quality of a feasible solution, we need the sharpest possible lower bounds.

A simple lower bound on the optimal objective function value of the integer optimization problem, the barrier material

Dar. However, this bound is usually too inaccurate, because the difference generally grows indefinitely with the demand figures. By alleviating the condition (4) is obtained from the problem ( 2) - ( 4) with relaxations often significantly sharper bounds, namely the

Continuous relaxation:

Restriction on actual versions:

The optimal objective function values of the two relaxations are denoted by and. Then this is easy. Of particular interest is the theoretical gap

It turns out that it is -difficult to check for any instance.

A worsening of the relaxation ( 6) is obtained with the introduction of upper bounds for the variant frequencies. How about a cross-sectional variation may be used at most times. But even for these more complicated relaxation is easily constructed instances after failure of the barriers tightening.

Example

The data indicated in the illustration are again ( pink colored) For instance, this (colored green ) the unique optimal solution of the continuous relaxation ( 5). Only the second blank variant, namely, has waste. Besides this variant are all in the Relaxationslösung in positive frequency occurring variants improperly. How to solve the relaxations explains a later section. It is true. The instance results found for the case that no part accounts for more than half of the starting material, largest known gap (as of 2007 ).

If we multiply the demand figures with eleven or do you replace them with the new vector, arises again the gap, however, is for the modified instance. Only the tightening of relaxation ( 6) reveals. However, a slight shortening of the individual in accordance to be cut 25 parts possible to make the tightening of relaxation ( 6) ineffective.

Equivalent instances

Two instances and are called equivalent if and applies and any permissible for one of the two instances variant is also permissible for the other instance. Equivalent instances are obtained from a given, for example, by multiplying all lengths by a positive constant, or by up to ε reduced part lengths and the source material extended by ε, if is sufficiently small, because no new variant is added. Thus, one can always be rational and go after multiplication by the denominator to integer data.

A according to (1 ) admissible variant is called maximal if and only if, that is, the blend is less than the smallest part to be trimmed. To check whether the instances and are at equivalent, it is enough apparently to investigate whether any maximum for an instance variant also for the other instance is allowed and vice versa. In contrast, must not already be closed for equivalence if each is designed for maximum variation for maximum as the counter-example shows.

Example of equivalence: Thomas Gau found in test calculations the instance with gap. Replacing the 3001 through 3125, there is an equivalent instance, since all other lengths are divisible by 250 and the variant is maximum. Therefore do not lose any permissible variant. Dividing now all lengths by 125, result is again an equivalent instance, viz. Another equivalent instance created from this by multiplying all lengths and suitable rounds, namely.

In order to prove that no equivalent instance exists with continuous integer data and shorter length of the starting material, the dual simplex method can be used without any objective function. Three types of inequalities to be satisfied by the equivalent instances:

For due to the sorting
Maximum for each variant
For any improper variant because of the integer.

Most of these inequalities are redundant, ie, they follow from the other. Simplex scheme, such lines can be deleted if they contain any negative entries, and not a part of the associated base variable to or. Last remain only rows for the desired lengths. However, there are examples that require more inequalities to describe all equivalent instances with continuous integer data, so where additional lines remain with at least one negative entry in Endschema.

Example: We are looking for all equivalent to the instance with instances throughout integer lengths, which applies to all. Obviously, to demand. In addition to the admissibility conditions and many redundant inequalities could still be listed, including not listed above, other variants maximum. The belonging to these six inequalities non-negative slack variables are denoted with. They are calculated as the difference of integer variables is also an integer. The following diagram is created:

Consequently, the slack variable must not be increased independently of the other. If you exchange against the integrality goes from lost if all the non-basic slack variables are then set to 0. Overall, can be described and that the four parameters, while valid, so are to take the integer points of an interval. In other examples, such features can look even more complicated. Another difficulty is in each case is to completely control the equivalence, ie, if not a necessary inequality, especially in impermissible variants lacking.

Another type of equivalence is obtained by conceives parts with demand numbers greater than 1 as the number of different parts, each of which is called exactly once. For example, if three times a portion of the length 5 is desired, one may write a part with the required number 3 as well as and instead of. Consequently, the one-dimensional bin packing problem in which each part is precisely to pack into containers the size once, equivalent to one-dimensional cutting problem introduced above ( 2) - ( 4).

The Teilbarkeitsfall; modified integer Aufrundungseigenschaft

An acceptable variant is called elementary if it contains only one type of part, ie is of the form with, where the - th base unit vector called the.

The Teilbarkeitsfall is when integer multiple of each part length. Then follows at once by only maximal elementary variants are used in the continuous relaxation ( 5).

For example, the instance has for relaxation ( 5) for the optimal objective function value. But here is valid, ie it is impossible with only two pieces of raw material to manufacture all parts. This instance provides the largest known in Teilbarkeitsfall difference, namely ( 2007).

For the above instance the integer Aufrundungseigenschaft does not apply. Since all previous experience could suggest that the gap for any instances of the one-dimensional cutting problem ( 2 ) - (4 ) is always small, the term of the modified integer Aufrundungseigenschaft ( MIRUP engl. modified integer round-up property, ) was coined. An instance has this property if and only if. The assumption that each instance of the one-dimensional cutting problem ( 2) - ( 4) MIRUP own, could so far (as of 2007 ) could be detected only in special cases, for example for the Teilbarkeitsfall. A simpler proof of Guntram Scheithauer and Johannes Terno was exacerbated in the dissertation. We have the following

Sentence: For each instance of the Teilbarkeitsfalls. Are all the parts greater than the starting material, even applies.

The existence of infinitely many pairwise non-equivalent instances of Teilbarkeitsfalls with follows inter alia from these statements:

Be pairwise relatively prime integers and. For all was, and there was no solution to the integer problem (2 ) - ( 4), in which these parts housed ( with the required numbers) in at most variants. Furthermore, let and. The so- defined instance has a gap.
For arbitrary is the least common multiple of ( or multiples thereof). Then the instance has a gap.
Be arbitrary and. Then for the instance.

Solution of the continuous relaxation

Even for relatively small parameter is the cardinality of the set is often so large that a complete enumeration of all admissible cut versions does not come into question. The situation will change nothing, if only waste- poor variants are considered. Since, however, also occur in an optimal solution occasionally waste- rich variants, this approach would be wrong. From necessity Gilmore and Gomory made a virtue by the relaxation solved with the revised simplex method, began as a start with the simplest versions and better investigated in the course of the optimization, if required.

In the revised simplex method belonging to the objective function coefficients in base and non- base percentage and be divided, as are the constraints in such a way, the base matrix is regular. Solving by and sets it into the objective function, we obtain. Since all objective function coefficients are 1 in our cut problem, an improvement in the objective function value of the continuous relaxation of ( 5) is therefore only possible if one of (1) allowable variation exists with. Thus these columns each generation a knapsack problem

To solve, which is true. A simple computational control consists of.

In order to avoid cycles in the simplex method, the rule of Bland recommends (see simplex method # row selection ). To implement this rule, raises one on each variant found and verified before the column generation problem ( 7) is solved, if earlier, a variant was stored applies. In this case, not the knapsack problem (7 ) is processed, but a replaced by the stored versions in the base, which gives the maximum value for the scalar product. Otherwise, the column generation task has to be solved. The cost of an exact solution of the problem should not be afraid to, otherwise usually much more simplex steps are needed.

A simple example: from one-dimensional starting material of the length 11 of the lengths 6, 4 and 1 are to be cut in particularly high numbers parts in proportion. The material utilization is to be maximized. This means here an optimal solution of the continuous relaxation ( 5) of the instance is searched. For the first base maximum basic variants are selected, that is, and so that at the beginning is a diagonal matrix. This results in the following revised simplex schemes, under which the new variant is specified. The pivot elements are each marked with a star (). For ease of programming, the right-hand sides and the vector were placed in the first column or row. On the far right is the transformed each new column consisting of and.

Optimal The variants and are consequently to be cut in proportion. The last exchange was (and failed) to replace the base in order to obey the rule of Bland, namely a plurality of selectable rows always select the one that leads to the replacement of the variable with the smallest index of the base. Although this example may seem academic, it shows that negative values ( ) may occur in the course of the invoice, if the demand figures were given suitable. If the relaxation ( 6) are solved with restriction to actual versions, this effect can occur even more significantly. In the column generation problem, the use of those parts is prohibited, so that simplifies the column generation task.

Residual instances

To the integer problem (2) - (4) at least approximately optimum solution, is the relaxation first (5) or (6 ) can be used. By simply rounding results in a feasible solution, if overproduction is allowed. In single blank variants perhaps can even be rounded. However, even with optimal rounding one would obtain in general an objective function value significantly higher than the optimal value. Therefore, this approach appears useful only when the number of different variants to be minimized, because the conversion of the production system is very complicated on different cutting patterns. Otherwise, it is advisable to consistently round and continue for the remaining parts either with a new heuristic or again to use the Relaxation (6).

Be one determined by the simplex method based optimal solution to the continuous relaxation ( 5). If, in the instance of the vector of demand figures by, a situation called a residual instance. It may well also zeros occur in the demand vector. Many estimates of the gap following helps

Lemma: Let arbitrary. Then for residual instances the implication

Proof: By assumption, there is an optimal basic solution in which each variant has a frequency. An integer cutting plan with over-production is obtained from the optimal solution to the relaxation ( 5) by simply rounding. The results thus

For times this inequality we add the valid inequality according to requirement and condition. Division by delivering the claim.

At all times, so that for theoretical investigations sufficient consideration of residual instances. In particular, it can consist of an optimal solution of the problem, the integer (2) - (4) for a construct, if the integer Aufrundungseigenschaft met. If you know a good integer solution for, then for. Unfortunately this is not always for the optimality, as the following counterexample shows:

Has a unique optimal solution to the relaxation ( 5), namely, where the ( in relaxation) waste- free variants, and were used. It applies and where there are several different optimal solutions for the integer problem (2) - is (4). The residual instance is here clearly ( with ), and it is, so that separating the integer part from the optimal solution of the continuous relaxation led to an increase of the gap. When using the relaxation ( 6), this effect would not have occurred. But in default of the demand vector is not able to prevent this inconvenience, the limitation on actual variations.

An approximation algorithm using relaxation

If the integer problem (2 ) - (4 ) can be solved exactly, it often proves to be advantageous to occasionally search within the optimization using an approximate method for good feasible solutions. A corresponding method sketch is this:

The cost of item 6 is to be estimated with. The selected in point 1 variants can be reworked before disconnecting sometimes as described in points 2-7. The resulting improvement heuristics found in pseudo-randomly generated test instances often optimal solutions. If the achieved objective value for the integer problem ( 2) - ( 4) but is larger than, even once the relaxation (6 ) are dissolved in point 2.

To obtain a good feasible solution of the integer cut problem ( 2) - to determine ( 4), sometimes enough a valid, non-optimal solution to the relaxation ( 5) or ( 6). If you want to stop the tuning prematurely for this reason, for example because the objective function values obtained begin to stagnate, it still requires a guarantee that you are actually close to the optimum. This provides a lower bound by AA Farley, based on the duality theory of linear programming.

The constant for relaxation ( 5) corresponding dual optimization problem is

Each, which belongs to the permissible range of the dual problem, thus provides a lower bound for the optimal objective function value. A suitable can be found easily once the knapsack problem ( 7) has been solved. The variant was identified. Applies, there is an optimal solution of the relaxation. Otherwise we set and get for any allowable cut variant, the assessment according to assumption. Consequently, the chosen for the dual task is allowed. This gives the desired lower bound

Which is in continuation of the optimization the optimal objective function value of the relaxation approaches. Analog looks the barrier for (6).

Example: above the calculated simplex schemes have been specified for the instance. Before the first exchange were and as well, ie. After Redeem the variant in the base were, and determined. Consequently, the lower bound drops to temporary and does not grow monotonically.

For multi-dimensional cutting issues a corresponding lower bound can also be established. According to AA Farley this barrier allows the saving of many column generation and exchange cycles, without running the risk to be far from optimum.

Instances

Is a positive integer. The instance name instance, if the case for everyone, so each part exactly - or times (plus wastage) in the starting material fits. The study of these instances one hand, allows the construction of particularly vicious examples, on the other hand estimates - in the general case - for the gap. Contains extensive investigations, while contributions in this regard constitute in and precursors.

Under a Part - variant we understand any valid blank variant parts are precisely tailored to the ( ), ie, where is the one vector consisting of all ones.

Instances with

Obviously applies to the integer Aufrundungseigenschaft because only is possible. However, when the situation changes fundamentally. If, resulting and for the instance

Wherein the parts have not been sorted by length. If, in the continuous relaxation ( 5) the waste- free variants, and each time, the variants, and each time, so you quickly confirmed.

Is valid for the following instances and:

There is no with ( 2.3 ) instance. On the other hand, and for which instances

At
With.

Complementary instances

First, we consider ( 2.3 ) instances with. By fixing for all we obtain a ( 2,3 ) instance to which we call complementary instance. The instance is complementary to again. Is a ( for ) waste- free variant with exactly three parts, is also admissible and without waste. In contrast, correspond waste- prone 3 -part variations in impermissible in and vice versa. Consequently, one can not of optimal solutions of the problems (2) - close to ( 4) or ( 5) or ( 6) for the corresponding optimal solutions. However, the generalization to instances is not difficult.

Consider now with an instance, for the true, are thus used in the in every optimal solution of the continuous relaxation only waste- free variants, each with parts in the positive frequency. Then the instance for sufficiently large

To an equivalent instance, because instances are all variants with a maximum permissible parts and all variations permitted with at least parts while the blend of a Part - variant is as great as in. For our purposes, the demand is sufficient

From. The complementary instance to which we define as

This need not be a necessary instance. If the instance is a gap, which is also true for almost everyone in the instance, since there are only finitely many combinations of at most parts, which result in a waste- free variant. Accordingly, where not even the complementary instance for almost all that satisfy the above condition, the integer Aufrundungseigenschaft.

For example, has a gap for all 1, and it is true. For all is a (2,3) - instance. The corresponding instance is complementary to all, and has also the gap is 1 for a (2,3) instance.

( 2.3 ) instances with flashy denominators

Before ( 2.3 ) instances are marked with gap, we demonstrate how diverse the denominator can be of. To this end was chosen arbitrarily. The specifications, and deliver with a (2,3) - instance. The break may be reduced only by 9. In contrast, arise in the (2,3) - instance

For the optimal objective function values and for the continuous relaxation of ( 5), leading to the assumption

Leads. The proof is still lacking. For the numerator and denominator are relatively prime natural numbers.

By varying the lengths slightly or cross out individual parts from the instance, there could be quite different denominators arise, for example:

( 2.3 ) instances with

If you link the entities with the power of two denominators and those with gap 1 suitably arise after a few other transformations ( 2.3 ) instances with gap, namely

The instances with the odd denominators are only conditionally suitable for this construction because they cause relatively much waste.

Return to simpler instances

To prove upper bounds on the gap, it seems necessary basis of the above results to simplify the instances. This is easily possible. In order not to exceed the scope, we do not here on evidence.

Let an arbitrary instance., Respectively, and the frequencies of all parts variations in the relaxation optimal solutions (5) and the integer problem ( 2) - ( 4) applies. Applies to most parts can be cut into parts variants, and after their separation remains an instance and. In contrast to the residual instances here the gap is not growing. With each further separating the respective largest remaining part of the optimal objective function value of the continuous relaxation of ( 5) takes over from to. This results in an important

Conclusion: Each instance with can be reduced to an instance, and. This means in particular: Is such that for all instances with the modified integer Aufrundungseigenschaft ( MIRUP ) holds, then for all instances with.

Example: In the (2,3) - instance

Applies and, therefore. In Optimal solutions of the integer problem ( 2) - ( 4) are thus at least two options in front with more than two parts. Four parts of the length 4097 can be cut into two 2- part variations. In the resulting instance is valid and. If you cut now the two largest parts, ie with lengths 4097 and 3073, in a separate variant, the optimal objective function value of the relaxation ( 5) drops to. If you separate now two parts of length from 3073, results for the remaining instance. Nevertheless, there are many non-integer optimal solutions of the relaxation ( 5).

According to the conclusion it is not a limitation when only instances are considered with and from here. Without loss of generality, the parts were ordered by random lengths, ie. The total number of parts is cropped above with length. For each call, the overall incidence of all occurring in an existing optimal solution of the continuous relaxation ( 5) variants that contain the exact parts (and larger parts).

Based on this classification of parts into larger and smaller results and so also. Applies only to the largest parts are cut in a separate variant, and the separation of this variant does not change the gap. May be found in place of this an acceptable parts - variant, which contains a larger part, but not smaller. Then, the reduction can be carried out any more frequently.

Example: In the (2,3) - instance

Applies, so that certainly seven three parts of length 2731 can be separated into a variant. This variant is however dominated by and. These two waste- free variants can be two to five times higher tailored to achieve without over-production. In the instance obtained again applies, and now, the variant may be separated again. ( Part 5 was consumed. ) This leads to the instance

With and such that the variant is still separate nine without changing the gap. On the basis of the above statements no further reduction is possible. Using heuristics to find now easily an integer optimal solution, and.

A priori admissibility of variants

When also applies. According to the reductions in the previous section, this can be enforced, and also. This is assumed in the following, if the above very technical statements are applied to ( 2.3 ) instances. Then also applies.

Under the conditions listed above is in a (2,3) - instance variant permissible short written when one of the following conditions is true:

The according to these criteria adequate allowable cutting variants are to (a) - hot or ( d ) variant -, (b) - (c). Of these criteria can be expressed by none other, although each ( d) variant with also ( a) variant and the ( a) variants, the ( b ) variants dominate. Condition (a) but is not applicable to. (a ) variants are for preferred, (c) - variants as is.

Example: Let and. When one finds, for example, (a ) variant ( 5,16,26 ), because. ( d) would have brought because no result. A ( b ) variant is ( 2,18,27 ), because. Was allowed for (a ) can not be used. When one finds for any (a) - and ( b ) variants. A ( d ) variant is ( 9,10,27 ), because. Because (as reductions ) and is therefore ( 9,19,21 ) a ( c ) variant, for and. Here the criterion ( d) would have failed because.

Well are, and where. Then and so that it ( 1,4,6 ), ( 2,3,6 ) and ( 3,4,5) are (a) variants. Would, could quickly construct or show that (2,4,5 ) would be the only variant used for part 2 in the relaxation ( 5) a contradiction. Both cases arise.

Installation integral intersection plans

It is not only important to prove the admissibility of individual blank variants, but that no only once existing part is used in multiple variants. Again we consider only instances in which the above reductions were made, and where, consequently and apply. Alone by, and dependent estimates for can be specified.

Two cutting variants are uncorrelated hot when they are really and no part occurs simultaneously in two variants, ie applies. Be the number of the elements which simultaneously uncorrelated parts variants can not be accommodated in pairs, no matter which plan for the problem ( 2) - ( 4) shall be used. Then:

With
, Especially at.

It follows for ( 2.3 ) instances with immediately MIRUP so. When you can appropriate (a) - and / or ( d ) variants to select, so that at most six major parts left over, which also MIRUP results. For example, there are at, always the ( d) - variants ( 7,17,30 ), ( 8,18,29 ), ( 9,19,28 ), ( 10,20,27 ), ( 11,21, 26), ( 12,22,25 ), and ( 13,23,24 ). In so everything is shown, otherwise you replace the first variant by (a ) variant ( 7,14,30 ) and other variants accordingly. Contrast, can not be proved solely by means of the above statements MIRUP in the case.

Statements to the general case

To what extent the gap for any instance is limited, could not yet be explored. For example, remained open whether is bounded by a constant or linear can grow with or about an estimate of the type having a constant for all instances of the one-dimensional cutting problem applies.

From the consideration of residual instances the almost trivial statement follows

Much more complicated is the proof of the estimates

And the proof of the integer Aufrundungseigenschaft for all instances. However, it is an easy exercise to prove, if is an integer.

Furthermore, it was MIRUP, therefore, be proved in the following cases:

When all the parts are also greater than one quarter of the starting material.

These also served following statement, for containing a good template:

Lemma: Via the instance for all, as well as further and provided. Applies, as is, and otherwise. Then have the instances and the same gap, ie during a single cropping of the majority and of the possibly largest matching part changes under the specified conditions, the gap is not.

None of the grounds may be omitted, as the counter-examples and with and show.

The MaxGap problem; Construction sets for large

The MaxGap problem (gap gap, ravine, recess, ...) is: You find instances of the one-dimensional cutting problem ( 2) - ( 4) with the largest possible gap.

The largest so far ( as of 2007) is reached gap.

An instance with and is this:

Evidence that the integer Aufrundungseigenschaft not apply was conducted using cutting-plane method.

Should be unlimited for that MaxGap problem can usefully be amended as follows: Determine instances with the largest possible gap to predetermined upper bound on the number of different parts.

Meanwhile, could be found with the help of two construction sets, among other instances with the following values for:

First construction set: The instance with rational lengths, on the gap. Be. It should also be selected so that also applies to any vector and. Then the instance has a gap greater than or equal.

If all data are integers, always meets the requirements as any improper variant requires at least one unit too much material. The application of this construction set with the instances, and the specified at the beginning illustrated example, which have the gaps, respectively, results in the instances, and with the gaps and.

Before further constructions, for instances with a large gap, we explain composite instances. For two instances and initially applies. In this case, the composite instance is of the order, all parts and trim in the respective required numbers from the uniform material length. In the situation in all the length of an instance to be multiplied by a suitable constant. You can also adjust both instances so. Up to equivalence results in the same order.

For example, is exactly the above with the picture illustrated example instance. Here add the gaps 0.1 and 1.0 to 1.1.

Special parameterized instances with gap are the following:

These instances prove to be useful for the construction of large gaps. The lengths of the two parts of the first instances approach for, while in the third instance of the fourth to ninth partial are relatively small. For any with, there are natural numbers, so that for the case. The same applies to.

Second sentence construction: In the instance and is explicitly allowed. If one increases by 1, so suppose the optimal objective function value of the integer problem (2 ) - to (4). Then there are natural numbers with, so have the composite instances and the gap., See also

For example, the instance satisfies the conditions, because in any optimal solution of the problem ( 2) - ( 4) found a blank variant with at least twelve units blend. With created the instance with gap.

The assumption means account that the greatest waste in a variant in an optimal solution of the integer problem ( 2) - ( 4) can occur in the positive frequency is less than half of the smallest part in the instance. To fulfill this condition, the main difficulty in the application of the second sentence construction dar. So it is not enough if the maximum blend is exactly half as large as the smallest part. For example, the gap is not constructible, but requires some more parts.

With the additional condition that the notification under waste- free variants may not be used once each. In Optimal solutions of the integer problem ( 2) - ( 4) for the model instance of the overall blend of nine units of length is divided into or, and because of the blending condition is met. Instead of this plausibility Statement exact procedure must be used for the instances constructed ready to prove.

In contrast to the first sentence of the second construction is hardly repeatedly applied to an instance, since a small part of which can be transferred to another variant, leaves too much waste. To this could be built up with the second sentence construction gaps; with the first there were.

To reduce the number of necessary parts of different lengths and still maintain the same gap, one could try to modify the corresponding block instances suitable. So the instance was essentially in that same part lengths were enforced. However, this comes across obstacles such as the following lemma shows from:

Minimum instances without integer Aufrundungseigenschaft

We assume without loss of generality that all data are integers. Then the minimality of an instance can be understood with still different:

Minimum number of different part lengths: with such an instance. Due to be had.
Minimum length of the starting material: To date ( 2007) is known here only; would be used for example in the auxiliary exposure. Whether smaller than 16 or 18 are possible, is still open. Is in Teilbarkeitsfall.
Minimum number of total zuzuschneidender parts or in other words, minimal number of parts in the bin - packing problem: It can be shown with a longer case distinction that at least five parts are needed and will in this case. Such instances are and, respectively.

Online Optimization

For online optimization problems, the data will be announced during the course of optimization, for example, if a continuous process is to be controlled optimally. In such a case, it is required not only to provide the best possible feasible solution in real time, but the parts can not even be pre- sorted according to size. Sometimes a few parts may be returned, so that there is some freedom at least for those parts. It goes without saying that when online optimization problems, careful optimization is excluded and one must be content with fast heuristics.

An overview of approximation algorithms and their quality are for example. Some results of this review article are presented in the following.

The problem ( 2) - ( 4) would be dealt with the approximation algorithm. For any instance is the determined objective function value. An absolute quality ratio in the worst case is given by. For an asymptotic quality assessment of sequences of instances are considered with. The corresponding limit superior of the ratio will be denoted by.

The heuristic Next Fit ( NF), always just keep a cutting or packing variant open, and if the next piece no longer fits with the opening of a new pack variant to close the last, so for no other part to use more, resulting in worst case for almost as achieved objective function value, such as when alternately parts of sizes and are to be packed with very small. Consequently.

The heuristics First Fit (FF) and Best Fit (BF ) are about equally well; both can be found for different instances. Both heuristics in common is that all you've already started variants may be used for still gripping parts if the part fits. In the first matching First Fit Pack variant is selected, at best fit a residual with minimal free space. A particularly unfortunate consequence to gripping parts for these heuristics exists, for example, when repeated items are to be packed with the lengths with very small positive in the order of monotonically increasing size. An even less favorable example contains with (any) and. Since the same is true in that Article, and for each instance that follows.

Any Fit (AF) hot heuristics, the new pack versions does not start until the next to be packed part does not fit any previous version. For any such online heuristics.

If ever a maximum pack variants may be open simultaneously, a finite constant that limits the one the possible heuristics. Under this condition is always on -line algorithms.

In order to ensure a better asymptotic behavior, one needs thus heuristics that may arbitrarily keep open many variants and are ready depending on the part size, start a new pack variant, although the next to be packed part still fits into an existing variant. Even without sorting can be achieved in this way an asymptotic ratio, but there is no on-line algorithm. Better ratios can be obtained if the are relatively small compared to thrilling parts.

If the parts are sorted before beginning optimization by monotonic decreasing size, can be spoken only by off-line optimization. Rules apply for the First Fit and Best Fit belonging corresponding heuristics. The absolute quality assessment is here. With sophisticated algorithms can after sorting the asymptotic ratio can be arbitrarily approached the value of 1, while still linear time is required, ie, for all, there are approximation algorithms. Moreover, approximation algorithms exist with polynomial complexity and. However, the absolute difference in such algorithms strongly increases.

The above statements each look at the behavior in the worst case. To be examined, the average case, additional assumptions about the incoming random variables are required. Under appropriate conditions are possible statements about certain expectation values .

Generalizations and extensions

If several different materials are given with lengths and prices, instead of the column generation problem ( 7) to solve several problems backpack, namely with backpack capacity. An improvement in the objective function value of the continuous relaxation is possible and when it is no degeneracy. Anticipatory restrictions on certain materials can be easily incorporated into the linear optimization model. In order to obtain a feasible initial solution, borrows it, where appropriate, fictional output material of sufficient length and with a very high price. If, despite supply constraints the problem is solvable, all fictional materials are replaced by actually existing. This idea is also applicable for panel cutting problems and the like.

Now, conversely, will be asked which supplies different lengths starting material must be purchased in order to handle multiple cutting orders as cheaply as possible can. It is assumed that longer pieces of material are always more expensive than shorter and cutting orders can not be mixed for organizational reasons. That is, must always parts of a piece of material to be cut only for an order. This assortment problem is treated including numerical experiments in the Habilitation thesis.

Another generalization of the one-dimensional cutting problem is the multi-dimensional vector packing problem, which may arise from planning tasks. Instead of the admissibility condition (1), several such conditions are imposed at the same time here, for example, that a certain geometric length and at the same time a certain total weight of the packed parts should not be exceeded. Also, could also be the time lead to such constraint.

The strip packing problem is a further generalization of the scheduling problems arising from one-dimensional cutting problem represents the task is to pack into a rectangle of dimensions with specified width and the smallest possible height non-rotatable smaller rectangles of given dimensions and demand figures overlap. Had the heights of all rectangles to be arranged the same, it was the one-dimensional cutting problem. A direct application of the strip packing problem consists in planning with a limited available resource, so that after a short time as possible, has been completely processed a list of jobs that need the resource.

A completely different extension of the one-dimensional cutting problem is when required due to limited space next to the trim system in a large order that always maintain a level different parts places are in progress, where the positive integer is fixed. So before the -th species can be started, a different type of part must have been completed. Wanted is in addition to the blank variants an order that ensures that as little material consumed and the additional condition is met.

An overview of a variety of other packing and cutting problems for which the one-dimensional problem ( 2) - ( 4) also can serve as relaxation is given in, among other things.

The " cutting problem with pattern - minimization" ( "cutting stock problem with pattern minimization " ) is an extension of the classical cutting problem. The extension " pattern minimization " means that in addition the number of different cutting options used should be minimized in addition to the consumption of raw materials. This problem occurs incurred if, for each blank variant unique production costs ( setup costs ), regardless of how often the variant is produced, for example, if for each variant, to saw a tube into several pieces, own blank template is required. Refers to the cost of a piece of raw material as well as the one-time costs that are incurred for each blank variant, the following value must be minimized here in place of equation (2):

This problem applies since the 1960s as unresolved. The articles deal with the problem by approximating and work with non-linear optimization, the non-continuous function (8) by continuous functions.

The History

Back in 1939, gave Leonid Kantorovich Vitalyevich an integral model for the one-dimensional cutting problem, but which belongs to his model continuous relaxation is very weak; it only provides the material barrier. Having to 1960, were the foundations of linear programming, including the revised simplex method has been provided, Gilmore and Gomory published already 1961/63 to combine the solution method for the continuous relaxation, namely the simplex method with column generation. This could, provided sufficient computing time, for not too large instances ( almost) optimal solutions are identified. However, since the computing time for larger instances is unacceptably high because many simplex steps are necessary and many backpack problems must be solved, interested one also for fast heuristics and their qualities. This happened in the 1970s. As always, so integer Aufrundungseigenschaft was observed to a similar presumption urged, to Odile Marcotte could demonstrate, by 1985 the 3- matching problem, that there must be instances of the one-dimensional cutting problem with gap. 1986 published Ms. Marcotte a concrete example. Since this example but (whole ) numbers between one and ten million was contained, said that such incidents were not available in practice. As Fieldhouse in 1990 indicated the much simpler instance, we saw a while, that such things really occurs in practice, but if it were singular individual cases. With the specification of infinitely many pairwise non-equivalent instances with difference the false thesis about the integer one-dimensional cutting problem in Aufrundungseigenschaft finally fell. Even at the end of the 20th century, it was possible for the exact solution of the integer problem ( 2 ) - (4 ) as an alternative to the branching process, the cutting-plane method Gomory I successfully adapt. Meanwhile, the method was further developed to Branch and price and cut.

Some still open questions

In addition to the issues of complexity theory is to the one-dimensional cutting problem still some research needed, for example:

Identifies the set of all instances of the one-dimensional cutting problem with at most different part lengths, we ask for. As can be estimated as sharp as possible?
We ask the same questions for special cases such as the Teilbarkeitsfall or if an integer exists with all or if no portion is longer than half of the starting material.
If a total of exactly five parts are to be cut, ie, one can calculate that of all these instances, the proportion of instances with gap is about a twenty- thousandth. What is the percentage if more parts are to be cut?
Thereby, those instances in which have a difference smaller than the corresponding residual instances?
For what minimum at consistently integer data can? Are possible for smaller than 30, 18 and 16?

Sources

Null vector Thesis statement

211955