An Evolutionary Stochastic-Local-Search Framework for One-Dimensional Cutting-Stock Problems
Georgios C. Chasparis Michael Rossbory Verena Haunschmid
cs.NE





An Evolutionary SLS Framework for One-Dimensional Cutting-Stock Problems        





   Software Competence Center Hagenberg GmbH 

              Softwarepark 21 

              4232 Hagenberg, Austria 

              Tel.: +43 7236 3343 857

              Fax: +43 7236 3343 888

              {georgios.chasparis,michael.rossbory,verena.haunschmid}@scch.at           










An Evolutionary Stochastic-Local-Search Framework for One-Dimensional Cutting-Stock Problems
Preliminary versions of part of this paper appeared in <cit.>, <cit.>.
The research reported in this article has been supported by the Austrian Ministry for Transport, Innovation and Technology, the Federal Ministry of Science, Research and Economy, and the Province of Upper Austria in the frame of the COMET center SCCH. Partially this work has also been supported by the European Union grant EU H2020-ICT-2014-1 project RePhrase (No. 644235)

    Georgios C. Chasparis Michael Rossbory Verena Haunschmid 

    Received: December 30, 2023/ Accepted: date
==========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




We introduce an evolutionary stochastic-local-search (SLS) algorithm for addressing a generalized version of the so-called 1/V/D/R cutting-stock problem. Cutting-stock problems are encountered often in industrial environments and the ability to address them efficiently usually results in large economic benefits. Traditionally linear-programming-based techniques have been utilized to address such problems, however their flexibility might be limited when nonlinear constraints and objective functions are introduced. To this end, this paper proposes an evolutionary SLS algorithm for addressing one-dimensional cutting-stock problems. The contribution lies in the introduction of a flexible structural framework of the optimization that may accommodate a large family of diversification strategies including a novel parallel pattern appropriate for SLS algorithms (not necessarily restricted to cutting-stock problems). We finally demonstrate through experiments in a real-world manufacturing problem the benefit in cost reduction of the considered diversification strategies.









§ INTRODUCTION
 

Cutting-stock problems formulate economic optimization problems aiming at the minimization of stock use so that certain job requirements are satisfied. They are concerned with the efficient slitting of bands of material out of a set of given rolls of material. Apparently, due to the immediate economic incentives, cutting-stock problems have attracted considerable attention, especially with respect to the development of optimization techniques for more efficient solutions. Cutting-stock problems have a long history, starting with the first known formulation of <cit.>, and the first advanced solution procedures based on linear programming proposed in <cit.>. 

In industrial environments, such as in the electrical transformers industry <cit.>, linear-programming techniques may not be appropriate due to the large number of constraints, some of which may be nonlinear in the parameters. Examples of such nonlinear constraints may include constraints imposed through eco-design measures (cf., <cit.>). Due to these nonlinear constraints, heuristic-based optimization techniques seem more appropriate for addressing this family of problems. To this end, this paper introduces a stochastic-local-search (SLS) algorithm for addressing a class of one-dimensional cutting-stock problems, namely the category 1/V/D/R according to the typology of <cit.>.

In the remainder of this section, Section <ref> presents related work and Section <ref> states the main contribution of this paper. In the remainder of this paper, Section <ref> presents the class of the cutting-stock problems addressed by this paper and Section <ref> presents the proposed evolutionary SLS algorithm. In Sections <ref>–<ref>, we provide a more detailed description of the building blocks of the proposed algorithm, namely the set of possible operations for local search in Section <ref> and the set of diversification strategies in Section <ref>. Finally, in Section <ref>, we provide an experimental evaluation of the proposed algorithm, and Section <ref> presents concluding remarks.
 



 §.§ Related work
 

The one- or two-dimensional cutting stock problem is the problem of optimizing the slitting of material into smaller pieces of predefined sizes subject to several constraints. Almost 80 years ago the cutting stock problem was first addressed by Kantorovich in 1939 (translated to English in 1960 <cit.>) and Brooks in 1940 (reprinted in 1987 <cit.>) (but not yet using that name). This problem first arose in the field of cutting paper rolls <cit.> and was later also used for the processing of metal sheets <cit.>, wood <cit.>, glass, plastics, textiles and leather <cit.>. More recent publications also deal with stent manufacturing <cit.> and cutting liquid crystal display panels from a glass substrate sheet <cit.>.

The cutting stock problem is closely related to bin packing, strip packing, knapsack, vehicle loading and several other problems <cit.>. A very commonly used objective is trim-loss or waste minimization. Other potential objectives that are mentioned in <cit.> can be the minimization of a generalized total cost function (consisting of material inputs, number of setups, labour hours and overdue time), subject to material availability, overtime availability and date constraints. Another interesting characteristic is the possibility to have multiple stock lengths <cit.> or the possibility of using leftovers <cit.>. An additional difficulty is when both the master rolls and the customer order can have multiple quality gradations <cit.>. 





Due to the fact that many different types of cutting stock problems can be found in the literature, e.g. with respect to dimensionality, characteristics of large and small objects, shape of figures and so forth, it is highly desirable that the scientific community is using the same language and terminology when describing problems and the corresponding solution approaches. In <cit.> a typology that covered the most important four characteristics at the time to classify optimization problems like the cutting stock problems was introduced. This typology was improved by <cit.>. An overview of characteristics how to classify the problems in the literature can be found in <cit.>.
The problem can further be distinguished whether it is off-line (full knowledge of the input) or on-line (no knowledge of the next items) <cit.>. 



The cutting stock problem can be expressed as an integer programming problem with the downside that the large number of variables involved makes the computation of an optimal solution infeasible <cit.>. To solve such integer optimization problems a broad range of algorithms exist. First advanced solution procedures based on linear programming were proposed by <cit.>. 
A review and classification of approaches into heuristics, item-oriented or cutting pattern-oriented can be found in <cit.>.

Most publications in this field employ exact algorithms which guarantee to find the optimal solution <cit.>. Exact solution approaches comprise column generation <cit.>, branch-and-bound methods <cit.> or a combination of them, e.g., the so-called branch-and-price algorithm <cit.>. A review of several linear programming formulations for the one-dimensional cutting stock and bin packing problem can be found in <cit.>.

Another group of publications is dealing with heuristic solution approaches. Contrary to exact algorithms, heuristic approaches do not guarantee to find the optimal solution <cit.>. Heuristic methods can be split into three categories: sequential heuristic procedures, linear programming based methods and metaheuristics <cit.>. A procedure that is often mentioned in the literature is the sequential heuristic procedure <cit.>. Many other publications deal with heuristics as well.
In <cit.> a very simple greedy heuristic is used. Some authors use heuristic-based column generation <cit.> or reduction <cit.> techniques. An example for an approach which combines an exact (branch-and-bound) with a heuristic (sequential heuristic procedure) method can also be found in the literature <cit.>.

It appears that the first mention of using genetic algorithms for the cutting stock problem can be found in <cit.>. The authors state that the earliest use of heuristic search techniques in the field of operations research was published in 1985. Whereas reference <cit.> uses an improved version of the traditional chromosome representation, reference <cit.> represents cutting patterns as tree graphs. Genetic algorithms have also been used for related combinatorical problems, e.g. integrating processing planning and scheduling (usually those problems are considered separately) <cit.> and solving the variable sized bin-packing problem <cit.>.
Further genetic algorithm approaches have been published in <cit.>. An overview over previous genetic algorithm applications can be found in <cit.>. The authors also provide a genetic algorithm model which was used to study three real-world case studies. Recently, an efficient genetic algorithm for the cutting stock problem is proposed by <cit.>. While most publications describe the crossover and mutation operators implemented <cit.>, none of them elaborate on diversification strategies which are an essential part of genetic algorithms.




 §.§ Contribution
	

The main objective of this paper is the development of an evolutionary SLS algorithm to efficiently address 1/V/D/R cutting-stock problems including nonlinear constraints. In particular, our goal is to provide an optimization framework that a) exploits the capabilities of modern computing systems through parallelization, and b) provides a flexible integration and tuning of a large family of diversification strategies. 

In fact, the proposed optimization framework led to the development of a novel high-level parallel pattern specifically tailored for evolutionary SLS algorithms, an earlier version of which presented by the authors in <cit.>. The proposed diversification strategies are easily incorporated to the structural characteristics of the parallel pattern and demonstrate the flexibility of this framework to accommodate a great variety of settings depending on both user demands and computational capabilities. Finally, we present an experimental evaluation demonstrating the relative cost reduction incurred due to the introduction of the proposed diversification strategies.

A preliminary version of the proposed methodology first introduced by the authors in <cit.>, however, without providing the details of the optimization algorithm. The present paper provides a ready-to-use comprehensive treatment of one-dimensional cutting-stock problems usually encountered in the industry.




 §.§ Notation


For convenience, we summarize here some generic notation that is used throughout the paper.



  * 𝕀_A denotes the index function such that 

    𝕀_A≐
    1     A=𝚝𝚛𝚞𝚎, 
    0


  * e_i∈ℝ^n denotes the unit vector of size n, such that its ith entry is equal to 1 and the rest are equal to 0;

  * For a matrix X=[x_ij]_i∈ℐ,j∈𝒥, we denote the row vector corresponding to the ith row as X_i: = [x_ij]_j∈𝒥 and the column vector corresponding to the jth column as X_:j = [x_ij]_i∈ℐ.

  * For a finite set A, A denotes its cardinality.






















§ PROBLEM FORMULATION
		

We consider a general class of one-dimensional (1/V/D/R) cutting stock problems. In particular, we are given a set of items (or bands) of certain types ℐ={1,2,...,n}, each of which is characterized by its width b_i and its desired weight w_i. The set of desired items ℐ need to be placed to a set of objects (or rolls) of material, denoted by 𝒥={1,2,...,m} each of which is characterized by its width b_j, its length ℓ_j and its specific weight d_j, j∈𝒥. Let also w_j denote the overall weight of roll j.





We define an assignment of bands into rolls, denoted x_ij∈ℤ_+, so that x_ij denotes the number of bands of type i assigned to roll j. The objective is to find an assignment X≐{x_ij}_i,j of bands into the available rolls, so that:


  * the overall weight of each band type i exceeds its desired weight w_i, i.e., 
    b_i∑_j=1^mx_ijℓ_j d_j ≥ w_i.
 To simplify notation, let us denote α_j≐ℓ_jd_j, in which case the constraint above may equivalently be written as

    y_i(X)  w_i - b_i∑_j=1^mx_ijα_j≤ 0,

where y_i(X) corresponds to the rest weight of item i.


  * the overall width assigned to each roll i does not exceed the width of the roll, b_i, while at the same time the residual band, denoted 

    r_j(X) ≐ b_j - ∑_i=1^nx_ijb_i ∈ℛ_j,

where ℛ_j⊆[0,∞) is a union of closed intervals of allowable residual bands, which might be different for each roll j∈𝒥.


Both of the above constraints are hard constraints and need to be satisfied for any assignment. Unfortunately, in most but trivial cases, there might be a multiplicity of admissible assignments, each of which might be utilizing a different subset of rolls 𝒥. We wish to minimize the overall weight of the rolls utilized by an assignment, i.e., we wish to address the following optimization problem:

    min_X∈ℤ_+^m×n g(X),

where

    g(X) ∑_j∈𝒥w_j𝕀_{∃ i∈ℐ:x_ij>0}

is the total weight of rolls used by assignment X. 






Then, the overall optimization problem may be written in the following form:
 

    min_X      g(X)       
           y_i(X) ≤ 0       
           r_j(X) ∈ℛ_j       
           X∈ℤ_+^n×m



Note that we allow for ℛ_j to depend on the roll j∈𝒥. This is due to the fact that some extra processing of the rolls may be necessary for each item which depends on the roll itself (e.g., seaming of the edges). Furthermore, we do not allow all possible residual bands in ℛ_j, since not all residual bands can be stored in stock. This constraint introduces a nonlinearity. 

The details of the optimization problem (<ref>) (i.e., the characteristics of items ℐ and objects 𝒥 and the set of allowable rest-widths ℛ_j, j∈𝒥), define an instance of the optimization problem, denoted π. Let also Π be the family of such optimization instances.

We have currently chosen a rather small number of constraints, namely the job-admissibility and rest-width constraint. However, it is important to point out that additional constraints may also be added, depending on the application of interest, such as the eco-design measures mentioned in <cit.>. Such constraints may be nonlinear in the parameters. Furthermore, alternative objective criteria may be considered (e.g., minimization of trim loss, as considered in <cit.>, or minimization of rolls needed by the assignment when the objects are identical, as considered in <cit.>). 

It is important to note that the forthcoming algorithm does not depend on the specifics of the considered constraints in optimization (<ref>). In fact, there is no restriction on the type and number of constraints imposed. Thus, the reader should consider optimization problem (<ref>) more as an example that will convenience the discussion throughout the paper, rather than as a restriction.




§ EVOLUTIONARY STOCHASTIC-LOCAL-SEARCH (SLS) ALGORITHM
	

The proposed algorithm consists of the following phases:


  * Initialization ();

  * Optimization ();

  * Filtering ();

  * Selection ().


The role of the initialization () phase is the establishment of candidate solutions (not necessarily satisfying all the constraints). The performance of the initialization function is rather important to the performance of the overall optimization, since a good head-start may significantly improve the performance of the SLS algorithm. 

The role of the optimization () phase is the execution of admissible local improvement steps, accompanied with admissible perturbations. Responsible for the execution of these improvement steps and/or perturbations of the existing candidate solutions are the working units, namely , each of which plays a distinctive role (explained in detail in the forthcoming Section <ref>). We may argue that the core of the proposed architecture lies in the design of the working units.

The role of the filtering () phase is the observation of the current status of the optimization algorithm, the storage and/or re-processing of candidate solutions. In other words, it supervises the state of all candidate solutions and decides on their future use. 

Finally, the role of the selection () phase is to decide on whether the optimization algorithm should be terminated according to some criteria (e.g., the size of the pool or time constraints) and, if yes, what should be the best estimate X̂ of the optimal solution. 

The details of the (SLS) optimization algorithm are presented in Figure <ref>, and they will be explained progressively in the forthcoming sections. 






























































 §.§ Initialization ()
	

The initialization phase discovers initial candidate solutions (i.e., assignments X which satisfy the job-admissibility constraint). The benefit of discovering such candidate solutions is rather important since it may fasten significantly the following optimization phase. Furthermore, if there exist a large number of local optima[We use the term local optima to refer to assignments X at which any local search (based on some predefined operations/modifications) may not result in a strictly better assignment with respect to the objective function.] (as it is often the case), the starting point may influence significantly the resulting performance. To this end, it is necessary that we consider alternative fitness functions for the generation of candidate solutions.

The goal of the initialization routine is to create an initial set of job-admissible assignments X, denoted 𝔓 (main pool) of bounded maximum size (𝔓_max). This pool of candidate solutions will then be used for optimization.  The possibilities for designing such a routine are, in fact, open ended. Here, we would like to provide one general structure, the specifics of which are provided in Table <ref>. 





As a first step, we sort both items ℐ and objects 𝒥 in descending order with respect to their width, similarly to a standard First-Fit-Decreasing (FFD) algorithm <cit.>. This is usually necessary, at least in cutting-stock problems, since large items may only fit in large objects. Then, for each item i (with positive rest weight), we go through each available object j (which may fit i), and we check whether an assignment of i to j maximizes a fitness criterion. In particular, we introduce here three candidate fitness functions:



  * negative weight of residual band of object j, i.e., 

    f_i(X;j) ≐ - r_j(X)α_j.

This fitness function is maximized when the weight of the residual band takes values that are close to zero. In other words, we try to fit as many objects as possible in each object j∈𝒥.


  * negative absolute rest weight of item i minus the weight of the residual band of object j∈𝒥, i.e., 

    f_i(X;j) ≐ - |y_i(X)| - r_j(X)α_j.

Note that this function takes large values when both a) the rest weight of item i and b) the residual weight of object j are close to zero. In other words, under this criterion, we try to fit as many items as possible within object j without though generating large rest weight for the selected items.


  * band i's weight minus the weight of object j's residual band, i.e.,

    f_i(X;j) ≐α_jb_i - α_jr_j(X).

Note that this function takes large values when the weight of item i is large compared to the residual band's weight, i.e., we try to fit as many bands as possible in each single object j.


Alternative fitness functions may be defined. Note that all the above fitness criteria employ a form of weight optimization (contrary to standard First-Fit-Decreasing algorithms). Such form of weight optimization is motivated primarily by two practical reasons: a) the difficulty in finding admissible assignments when the stock material is limited (something that cannot be guaranteed by standard First-Fit-Decreasing algorithms), and b) the limited time offered to solve the optimization problem, which makes the initial assignment a rather important factor over the final performance. In the forthcoming experimental evaluation (Section <ref>), we will demonstrate the impact of this good head-start in the final performance.

In the remainder of this paper, we will assume that an initial candidate solution X that satisfies the job-admissibility constraint is available as a result of this initialization phase. Note that we do not impose the rest-width constraint during this initialization phase, due to the fact that in several cases it is rather difficult to meet this constraint. A special treatment of the rest-width constraint is suggested as part of the following optimization phase.




 §.§ Optimization ()
	

As described in Figure <ref>, the results of the  routine are used to populate an initial set of candidate solutions (main pool 𝔓) that will later be processed with  to generate admissible solutions for the optimization instance π∈Π.

In particular, the following steps are executed. First, the available candidate solutions in 𝔓 are sequentially processed through a sequence of working units. They are responsible for performing the necessary steps for either establishing admissible solutions and/or for further improving the performance of a candidate solution. We introduce three types of working units, namely:


  * 

  * 

  * 

where ℭ{𝒞_ job,𝒞_ rw} is the family of constraints considered, corresponding to the job-admissibility (<ref>) and rest-width (<ref>) constraints. 

The role of the  is to address the rest-width admissibility constraint, since it might not easily be satisfied for  the job-admissible assignments generated at . In case additional constraints were considered in the optimization problem (<ref>), then additional such workers would have to be introduced.

The role of the  is to generate improved assignments X with respect to the objective function in (<ref>).

Finally, the role of the  is to perform a sequence of perturbations in the currently admissible solutions in order to avoid convergence to local optima.

All these classes of working/processing units are based upon appropriately introduced modifications of the candidate solution X, so that either a constraint is satisfied or an improvement is observed in the cost function. These modifications, namely operations, constitute the core of the proposed optimization scheme and will be described in detail in the forthcoming Section <ref>. A set of available operations will be considered, denoted 𝒪. Let also o∈𝒪 denote a representative element of this set. For now, we will only assume that each operation o∈𝒪 is equipped with three alternative modes, denoted:


  * ,

  * ,

  * .

The above introduced modes designate three alternative possibilities for searching and executing operations in the candidate solution X. The better reply of an operation o∈𝒪, denoted  , is based upon a semi-stochastic search of neighboring assignments to X which improves the cost of the current assignment X, i.e., it generates an improved candidate solution with respect to the objective g() that also satisfies the constraints in ℭ. The  mode performs a similar type of search, however the objective is to guarantee that the resulting assignment satisfies the constraints within ℭ of the optimization. The set ℬ⊂𝒥 is the set of “bad” objects that currently do not satisfy the constraint. Such a mode may be particularly beneficial when X does not currently satisfy some of the constraints. Finally, the  mode of an operation o∈𝒪 is based upon a random generation of local to X assignments that satisfy the constraints ℭ, however they may not necessarily improve the cost of X.

In the remainder of this section, we describe in detail the three introduced working units of the optimization routine which utilize some or all of the three alternative operation modes stated above.




  §.§.§ Rest-width worker ()
	

Note that the initially generated assignments X in 𝔓 define candidate solutions that satisfy only the job-admissibility constraint (<ref>). The role of the rest-width worker is to operate on the candidate solutions on the main pool 𝔓, so that they satisfy the rest-width admissibility constraint for all objects j∈𝒥, without violating the job-admissibility constraint. The rest-width constraint is usually the most difficult constraint to be satisfied, and this is the reason it cannot be treated during the initialization phase of Section <ref>. Usually, a sequence of operations might be necessary before rest-width admissibility is achieved. 

The rest-width worker is governed by the parameter N_ con which corresponds to the total number of processing steps executed per each run of this worker. The architecture of the rest-width worker is presented in Table <ref>. 



As we can see, it simply executes a number of operations under the  mode until a rest-width admissible solution is found.

It is important to point out that if a candidate solution X satisfies this constraint (after passing through this worker), then it will satisfy this constraint for the remaining of its processing history, i.e., no further processing will be requested for X within this working unit. This is due to the fact that any subsequent working unit will never violate any of the constraints in ℭ.



  §.§.§ Local optimization worker ()
	

The local optimization worker receives a candidate solution, X, which satisfies both constraints (<ref>)–(<ref>), i.e., job-admissibility and rest-width constraint. The objective is to perform local operations in the candidate solution X under the  mode, so that the resulting assignment reduces the cost (<ref>), while maintaining admissibility. 

The operation of the local-optimization worker is governed by N_ loc∈ℕ which is the total number of operations executed per run of this worker. A description of this worker is provided in Table <ref>. Note that the number of steps executed within this worker is fixed and independent on whether a cost reduction is found or not.







  §.§.§ Perturbation worker ()
	

With probability λ>0, a number of operations under the  mode are executed while maintaining admissibility and without necessarily reducing the cost (<ref>). A fixed number of N_ per operations is executed per each run of this worker. The goal of such operations is to escape from local optima by temporarily accepting worse performances. A description of the architecture of the perturbation worker is provided in Table <ref>.







 §.§ Filtering ()
	

The role of the  is to assess the quality of the produced candidate solutions and to decide which of the candidate solutions need to be reprocessed and which should be reserved for later use. 

The operation of the  is based upon the notions of reprocessing and reservation. In particular, the filter is responsible for updating two sets of candidate solutions, namely the main pool 𝔓 and the reserve pool ℜ.
The pool, 𝔓, is the set of candidate solutions that are currently getting processed (i.e., they go through the optimization steps in ). The reserve pool, ℜ, maintains candidate solutions from earlier stages of the optimization of high potential that may replace candidate solutions within the main pool 𝔓 upon request.  

More specifically, the main steps of the  are shown in Figure <ref>. In words, for each candidate solution X_i of the main pool 𝔓, we first assess its good standing and decide on whether it should further be processed based on prior performances summarized in memory 𝔐(X_i). In particular, if X_i is not of a good standing, then it is removed from the main pool (i.e., ) and replaced by another candidate solution from the reserve pool (i.e.,  and ). If, instead, X_i is of a good standing, then it remains part of the main pool 𝔓 and continues on the assessment of its high potential, based again on prior performances summarized in memory 𝔐(X_i). If X_i is identified as having high potential, then it is saved into the reserve pool ℜ (i.e., ). When all candidate solutions have been filtered (i.e., assessed with respect to their good standing and high potential), then the main pool 𝔓 exits the .

The reserve pool ℜ is initially empty and it is gradually populated by solutions of high-potential. However, we assume that ℜ has a bounded maximum size ℜ_max, which means that when its capacity is reached, the newly entered solution will replace the oldest one in the pool. The reason for selecting a bounded maximum size is to allow for dynamic restarts within a bounded fitness-distance from the current best. In many practical scenarios, performing dynamic restarts from very early stages may delay significantly the optimization speed. However, by properly selecting the maximum size of the reserve pool, we may find an appropriate balance between earlier dynamic restarts and optimization speed. 

It is also important to note that the maximum size of the main pool 𝔓 is also bounded by 𝔓_max (as discussed in Section <ref>). When a reserved solution needs to replace another one from the main pool, the oldest one in ℜ is always picked. Also, when a reserved solution is requested to replace X∈𝔓 but ℜ is currently empty, then a replacement is not possible and the size of the main pool is going to reduce by one. When the main pool 𝔓 becomes empty, then the optimization should terminate.







































  §.§.§ Good standing ()
		

The function  assesses the potential of a candidate solution X to continue providing reductions in the cost value. It depends on the current version of the candidate solution X, its prior memory 𝔐(X), and the currently best candidate solution X̂. Informally, the role of the good-standing assessment is to capture whether a candidate solution X is currently able to follow the path of the currently best candidate X̂, and this is achieved by evaluating a) the fitness-distance of X from the current best X̂, b) the steps elapsed since the last time X provided an improvement to X̂, and c) the gradient of the cost reduction during the most recent processing steps of X. In fact, we would like that the candidate solution X is sufficiently close to the current best, and its cost gradient is sufficiently large.

To accomplish this assessment, we first introduce the following parameters: 


  * N_ gs^* denotes the number of processing steps over which the good standing of a candidate solution is evaluated.

  * D(X,X̂) denotes the normalized fitness-distance between X and the current best X̂, defined as follows:

    D(X,X̂) g(X)-g(X̂)/g(X̂).


  * D_ gs^* denotes the maximum allowed normalized fitness distance from the current best for which the good standing is maintained.

  * G(X,𝔐(X),N_ gs^*) denotes the gradient of cost reduction observed in the candidate solution X, defined as follows:

    G(X,𝔐(X),N_ gs^*) g(X[N_ ps-N_ gs^*]) - g(X[N_ ps])/N_ gs^* · g(X[N_ ps-N_ gs^*])≥ 0,

for N_ ps > N_ gs^*, where N_ gs^* denotes the number of recent processing steps over which we estimate the gradient change of the cost function. 


  * G_ gs^* denotes a threshold based on which the gradient G of cost reduction is being evaluated.

  * N_ rb(X) denotes the number of processing steps since the candidate solution path leading to X has provided a recent best (i.e., a reduction to the cost function).



In particular, the exact steps for assessing the good standing of X are provided in Table <ref>.


First, we check whether enough processing steps have elapsed for the good standing criterion to be evaluated (i.e., N_ ps(X) ≥ N_ gs^*). This initial check is required due to the absence of any prior knowledge regarding the potential of a candidate solution X. Then, we evaluate a) the normalized fitness-distance of X from the current best X̂, D(X,X̂), and b) the processing steps elapsed since the last improvement offered by X, N_ rb(X). Both have to be small enough to maintain a good standing. Lastly, we check whether X exhibits a sufficiently large progress rate. If its progress rate is larger than G_ gs^*, then X will retain its good standing. In other words, for maintaining a good standing, it is not sufficient that X is close enough (with respect to fitness) to the current best, rather it should also provide a progress rate that is promising for improving the current best.

The parameters D_ gs^*, G^*, and N_ gs^* need to be determined by the user.








































  §.§.§ High potential ()
	

The notion of high potential of a candidate solution X captures its ability to provide significant reductions to the objective function (<ref>). For example, an indicative criterion of a high potential is an extremely high progress rate G(X,𝔐(X)). We wish to store candidate solutions exhibiting high potential at different stages of their processing paths, so that we are able to restart the processing from these stages. This form of restarts may serve as a mechanism for escaping from local optima, while at the same time it may increase the probability of converging to the optimal solution.

To assess the high potential of a candidate solution, we first introduce the following notation:


  * N_ hp^* denotes the number of processing steps over which the high potential of a candidate solution is evaluated.

  * D_ hp^* denotes the maximum allowed normalized fitness-distance from the current best for which the high potential property can be assessed.






  * G_ hp^* denotes a threshold based on which the gradient of cost reduction G is being evaluated.

  * N_ lr(X) denotes the elapsed processing steps since the candidate solution X was last reserved into ℜ.



The exact steps for assessing the high potential of a candidate solution X are provided in Table <ref>. First we check whether enough processing steps have elapsed for the high-potential criterion to be evaluated. Then, we evaluate a) the normalized fitness-distance of X from the current best X̂, D(X,X̂), and b) the processing steps elapsed since the last reservation offered by the processing path of X. We would like X to be close enough to the current best, however we would also like X not to have provided recently any reservations (thus not creating subsequent reservations from the same processing paths). Lastly, we check whether X exhibits a sufficiently large progress rate, i.e., larger than G_ hp^*. 





We should expect that D_ gs^*>D_ hp^* and that G_ gs^*<G_ hp^*, since high-potential should also imply good-standing but not the other way around.























































 §.§ Selection ()
		

The last part of the optimization algorithm is the selection phase (). In this phase, the main pool 𝔓 of candidate solutions has already been filtered, and the question is whether we should terminate processing and select the current best estimate X̂ or continue processing 𝔓. The specifics of this phase are shown in Figure <ref>. The terminate decision is taken upon the current size of the main pool 𝔓 as well as the maximum allowed processing time t_max imposed by the user. In particular, when the size of the main pool is zero, or when the elapsed processing time has exceeded t_max, then the optimization is terminated and the current best estimate X̂ is provided as an output.





§ OPERATIONS
	

As we mentioned in the description of the optimization phase (), the means by which local modifications of candidate solutions are created/searched is through a set of available operations 𝒪. In this section, we would like to provide a description of the operations considered, as well as a description of their alternative modes (as initially introduced in Section <ref>), namely ,  and . 

The operations implemented are the following:


  * ,


  * ,

  * ,

  * ,

  * ,

  * ,














 §.§  operation
	



The move operation moves a single item from one object (or roll) to another object (see Figure <ref>). The details of the  mode of this operation are described in Table <ref>.



Note that this mode implements a form of nested search over the source object (), an item from this object () and the destination object (). Then, it operates a move of the  from  to . The  should be selected from the set of objects that are currently used (), i.e., from the set of objects with at least one item assigned to them. Given that the number of objects might be large, we can bound the size of this nested search via the parameter N_ br_trials. The selection of this parameter depends on the number of available objects 𝒥, and the desired time of optimization t_max determined by the user.

Similar in architecture is the  mode of this operation, however the objective is to simply generate admissible assignments for those objects that do not satisfy the constraint. The details are shown in Table <ref>.


In particular, for N_ con_trials times, we go through the set of “bad” objects that do not satisfy the constraint. For each one of the items of this object, we go through a number of destination objects (different than the “bad” object), and we check whether admissibility of the modified assignment has been resolved with respect to the “bad” object (without violating the job-admissibility requirements for the moved item). Similarly to the  mode, this mode is controlled by appropriately selecting the parameter N_ con_trials.

The  mode of this operation is described in Table <ref>. 



It simply relies on a random selection of two (distinct) objects, one of which should have a non-zero number of items assigned to it. Then, an item is randomly picked from one of the objects and is assigned to the second object. The objective is to generate a new assignment X' that maintains ℭ-admissibility. The effect of this mode into the cost is not considered. 

Finally, note that there is not a unique way to initialize the objects/items involved in these modes, and this is also true for all the operations that follow. For example, in  mode, we have selected a nested type of search to initialize the objects/items involved, while in  mode, we implement a completely random initialization. This is not restrictive. In practice, a nested type of initialization of the parameters provided a faster discovery of better replies, however formulating the most efficient architecture for these modes requires a separate investigation.

























































































 §.§  operation
	



The  operation swaps one or more items from one object (or roll) with one or more items from another object (see Figure <ref>). 

In particular, the  operation is based upon the selection of two objects (among all objects with non-zero items) and the selection of a combination of items from these objects. Then, the selected items from both objects are swapped with each other. Figure <ref> provides an example, where two items from object 1 are swapped with one item from object 2. 
































The  mode of this operation, for the case of 2 objects, is described in Table <ref>. 



This mode incorporates the swap of a combination of items from object 1 with another combination of items from object 2 (different than object 1). This mode can be augmented by alternative swap types, where more objects are involved. 

The  and  modes of the  operation are similar to the corresponding modes of the  operation, however following the structure of the swap operation. Accordingly, the  mode is based upon a random selection of objects, and a random selection of a combination of items from these objects. 





 §.§  operation
	



The  operation splits one item currently allocated in one object into two other distinct objects (see Figure <ref>). 




























The  mode of this operation is described in Table <ref>. 


This mode randomly selects an object () from the set of  and a combination of 2 distinct objects ( and ) that are different from . Then it assigns a randomly selected item from  to both  and . This selection of objects and an item is repeated for a fixed number of times controlled by N_ br_trials or until a better reply is found. 

The  and  modes of the  operation are similar to the random mode of the  operation, however following the structure of the  operation.





 §.§  operation
	

The  operation involves an object with two or more items and moves a combination of its items to new distinct objects (which may or may not have items assigned to them), see Figure <ref>. In a way, the  operation compliments the  operation, since it involves more than one item and more than one destination objects. 





The  mode of this operation is described in Table <ref>. 



According to this mode, we select a) a source object, b) a combination of items from the source object, and c) a combination of distinct destination objects equal in number to the selected items. Then, each one of the items moves to one of the destination objects, so that the cost of the optimization is reduced (e.g., see example of Figure <ref>).

Similarly, we may define the  and  models of this operations (the same way we did for the  operation in Section <ref>).





 §.§  operation
	

The  operation performs a reverse form of the  operation. In particular, the goal of this operation is to combine items from several source objects and move them into a new destination object, see Figure <ref>. 



The  mode of this operation is described in Table <ref>. 



According to this mode, we find a) a combination of source objects, b) an item from each source object, and c) a destination object. We, then, move the selected items to the destination object and we check whether the cost has been reduced. 

The  and  modes of this operation can be defined in a similar way, as we did for the  operation in Section <ref>.






 §.§  operation
	

The  operation checks whether an item assigned to an object can be removed without violating any of the constraints (i.e., job-admissibility and rest-width constraints). Obviously if any such item can be removed without violating the constraints, then it is likely that the objective function will be reduced. For example, this might be the case when there are objects with a single item assigned to them. The  mode of this operation is described in Table <ref>. 



Similar is the reasoning in  and  modes of this operation.






§ DIVERSIFICATION STRATEGIES
		

The proposed structure of the optimization algorithm may naturally incorporate several diversification strategies. Diversification strategies aim at preventing the search process getting trapped in local optima. In this section, we present a set of possible diversification strategies that can be exploited.

Given that optimization problems of the form (<ref>) may differ significantly from each other, both in the number of feasible solutions as well as in the search space, the development of a unified selection and tuning of diversification strategies becomes almost impossible. The goal of this paper is to demonstrate that the diversification strategies considered here can make a difference at least on average.

We may group the set of diversification strategies considered here in the following categories.



  * Diverse initialization strategies

  * Bounded-distance dynamic restarts

  * Random perturbations

  * Parallelization

  * Cost-free operations






 §.§ Diverse initialization strategies
 	

As we discussed in Section <ref>, we introduced three alternative criteria in the formulation of initial candidate solutions. Our objective is to generate initial admissible solutions that a) are close enough to the optimal solution, and b) are diverse enough to increase the possibility for convergence to the optimal solution. 




 §.§ Bounded-distance dynamic restarts
		

A candidate solution may currently be located at search spaces with no significant potential in reducing the current cost. Thus, in order to avoid stagnation, we allow such candidate solution to be replaced by another one from an earlier stage but within a bounded fitness distance from the current best. There are two operations that indirectly control the process of dynamic restarts, namely the  and  functions. As already described in Section <ref>, the  function and its parameters (i.e., D_ gs^*, G_ gs^* and N_ gs^*) control the criteria for dropping a candidate solution, while the  function and its parameters (i.e., D_ hp^*, G_ hp^* and N_ hp^*) control the criteria for reserving a candidate solution. Apart from these parameters, the size of the main and reserve pool also affect the evolution of the optimization algorithm. These parameters need to be carefully tuned so that the bounded-distance dynamic restarts increase the probability of escaping from a local optimum without though delaying significantly the optimization process. The response to these parameters may differ significantly between application scenarios.




 §.§ Random perturbations


Random perturbations constitute an alternative way to avoid stagnation, through the introduction of a sequence of randomly generated operations. In particular, with a small positive probability λ>0, a candidate solution goes through the , in which a sequence of operations is randomly selected, and a random initialization of this operation is set ( mode). If the perturbation leads to an admissible solution, then the modification is accepted independently of the resulting objective value. This is essentially similar in spirit with the random-walk extension introduced in <cit.>. 




 §.§ Parallelization
		

The implementation of the optimization algorithm depicted in Figure <ref> suggests a high-level (domain-specific) parallel architecture that does not fit to standard parallel patterns. Simple for-loop parallelization, using, e.g., 
a parallel-for pattern, is not possible, since the iteration space is not known a-priori. In fact, we do not know how many times a candidate solution should pass through the optimization worker () before we stop processing it. 

To this end, first we partition the main pool 𝔓 into K sets of candidate solutions (where K is our planned parallel degree). We then process these sets in parallel through the  function. Finally, we decide on whether a candidate solution should continue processing through the implementation of the . The proposed parallelization architecture is depicted in Figure <ref>.

The proposed parallel pattern is a modification of the so-called pool-pattern, first implemented in <cit.> and incorporated in the FastFlow parallel programming framework in <cit.>. The modification lies in the introduction of the reserve pool ℜ that simplifies the implementation of the bounded-distance dynamic restarts, which is an essential part of several SLS algorithms. 

As probably expected, the larger the parallel degree, the larger the probability of getting closer to the optimal solution. This will be demonstrated through experiments in the forthcoming Section <ref>, but it may also be supported by the statistical literature <cit.> as pointed out in <cit.>.





 §.§ Cost-free operations


By cost-free operations we mean operations that may result in (practically) the same cost. The role of such operations may be proven rather important mainly because they introduce perturbations with no impact to the objective. Thus, through such operations, we may diversify the search of optimal solutions without necessarily restarting from worse assignments. More formally, let X' be a modification over an initial candidate solution X. A modification becomes acceptable subject to a better-reply criterion if the following smooth condition is satisfied:

    g(X') < g(X) + ζ(X,X'),

for some real-valued function ζ. Function ζ applies a form of extra allowance in the acceptance of an improvement. For example, we may assume that ζ=ϵ for some small positive constant ϵ>0. Alternative criteria may be defined. 






§ EXPERIMENTAL EVALUATION
 		

The goal in this section is to evaluate the behavior of the evolutionary algorithm and understand the role of the alternative diversification strategies introduced. In particular, we are going to demonstrate the effect of each one of the proposed diversification strategies in the overall performance of the algorithm. To this end, we consider a number of optimization problems of the form (<ref>) borrowed from the industry of manufacturing transformer cores (cf., <cit.>). Each optimization problem is fully described by a set of available rolls and a set of required items to be produced (characterized by their width and weight). The optimization problems considered span from jobs of small number of items  to medium or large number of items, thus covering a range of possibilities and enough variety to test the effect of the proposed algorithm and the diversification strategies.

The optimization problem (<ref>) minimizes the used objects' weight. Since the performance of the optimization might be affected by the size of the problem (i.e., the weight of the produced items), we introduce a performance metric normalized by the size of the problem. Let us assume that a set Π of different optimization problems is considered. Let X̂_π denote the best estimate discovered by the algorithm, and W_π be the total weight of the required items, i.e., W_π∑_i∈ℐw_i. We introduce the following evaluation metric, 𝒢:Π→ℝ_+, such that 

    𝒢(π) g(X̂_π)/W_πg(X̂_π)/∑_π∈Πg(X̂_π).

The first part of the performance metric corresponds to the ratio of objects' weight over the items' weight. Naturally the higher this ratio is, the less efficient the solution would be. However, an inefficient solution at a small-size problem does not have the same impact with an inefficient solution at a large-size problem. To this end, the role of the second ratio is to normalize the effect of the solution in the overall cost.
Furthermore, note that ∑_π∈Π𝒢(π) is the weighted average ratio of the used objects' weight over the required items' weight, i.e., it captures the efficiency of the optimization. 

In the following subsections, we will investigate the effect of the alternative diversification strategies proposed here (as well as some of the optimization parameters) and their impact in the overall performance of the algorithm via metric (<ref>).





















  §.§.§ Diverse initialization strategies


We start our investigation by varying the set of strategies considered in the initialization phase of the algorithm. In Figure <ref>, we see the impact of the initially considered candidate solutions when we restrict the set of strategies used to generate them. In the first scenario (dashed line), we employ the initialization criterion of Equation (<ref>), while in the second scenario (solid line), we consider all available initialization criteria of Equations (<ref>)–(<ref>). In either case, the initial set of candidate solutions (main pool 𝔓) has the same size and it is populated equally by each one of the considered initialization strategies.



It is important to point out that the benefit of the larger variety of initialization strategies is also due to the fact that the considered strategies employ a form of weight optimization therein. We should not expect that the same improvement occurs when we consider initialization strategies that do not apply a form of weight optimization. 

In Figure <ref>, as well as in the following experiments, we also demonstrate how the performance varies as we increase the parallel degree (K). This corresponds to the effect of parallelization following the architecture of Figure <ref>. Furthermore, in all these experiments, t_max=5min, unless otherwise specified.





  §.§.§ Random perturbations


In this set of experiments, we would like to test the effect of the random perturbations controlled by the parameter λ>0. Figure <ref> shows the increase in performance when λ increases to λ=0.1 (i.e., with probability 0.1, a candidate solution goes through the . 



Note that the random perturbations have a positive impact in the optimization performance.





  §.§.§ Optimization time


We would also like to investigate how the optimization algorithm responds when the maximum allowed optimization time (t_max) increases. It is natural to expect that the performance in this case should increase, since some of the candidate solutions will be processed for a longer period of time. Note further that the increase in performance seems to reduce as we increase the parallel degree. One explanation for this behavior is the fact that an increased parallel degree already allows for a faster processing, thus it is highly likely that we are already sufficiently close to the optimal solution.








  §.§.§ High-potential threshold


Recall that D_ hp^* and G_ hp^* are two thresholds that control the reservation of candidate solutions into the reserve pool ℜ. We would like here to investigate the effect of D_ hp^* which corresponds to the normalized fitness-distance from the current best within which a high-potential candidate solution can be stored into the reserve pool ℜ. In other words, we would like to investigate how the performance of the optimization varies when we move the reservation threshold towards earlier stages.

When candidate solutions from earlier stages are stored into the reserve pool ℜ, we should expect that the escape probability from local optima should increase. However, the size of the reserve pool ℜ is fixed, which means that the oldest candidate solutions may be dropped to create space for more recent reservations. Thus, when we just increase the threshold D_ hp^* the benefit is not guaranteed (Figure <ref>). However, if we also increase the size of the reserve pool, then the benefit for increasing the threshold can be materialized (Figure <ref>).









  §.§.§ Good-standing threshold


Recall that D_ gs^* and G_ gs^* are two thresholds that control the assessment over allowing a candidate solution to continue processing (Section <ref>). In particular, D_ gs^* denotes the normalized fitness distance from the current best within which a candidate solution is allowed to continue processing. We wish to investigate how the performance of the optimization will change as we increase D_ gs^*, i.e., if we allow candidate solutions to remain longer within the main pool 𝔓. 

Figure <ref> demonstrates how the performance changes as we progressively increase D_ gs^*. As expected, the longer we allow a candidate solution to remain within the main pool, the slower the rate of using reserved candidate solutions, and the greater the probability that the process is trapped in a local optimum. Thus, we should expect that the performance may degrade as we increase D_ gs^* more than necessary (Figure <ref>). However, if we also increase the optimization time, then we may achieve better performance (since we exploit better the fact that solutions remain in the pool for longer periods of time), Figure <ref>.









  §.§.§ Cost-free operations


In the last experiment, we wish to investigate the effect of cost-free operations in the performance of the optimization. Cost-free operations essentially allow for local operations that do not have any significant impact in the overall performance. As probably expected, this allows for a candidate solution to escape from a local optimum with no impact in the performance. Figure <ref> demonstrates the fact that cost-free operations can indeed increase the overall performance rather constantly over the parallel degree.




































§ CONCLUSIONS
		

This paper presented an evolutionary SLS algorithm specifically tailored for one-dimensional cutting-stock optimization problems. The novelty of the proposed algorithm lies in its architecture that allowed for the introduction of a novel parallel pattern and the easy integration of a large family of diversification strategies. Although the proposed SLS algorithm was presented within the context of one-dimensional cutting-stock problems, its architecture is generic enough to be integrated into a larger family of combinatorial optimization problems. Finally, the presented experimental evaluation demonstrated a significant improvement in efficiency due to both the proposed parallel pattern as well as the additional diversification strategies presented.










splncs03

   
















