# A Hybrid Simulated Annealing/Linear Programming Approach for the Cover Printing Problem

Authors: Federico Alonso-Pecina; David Romero
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

TheNP-hard cover printing problem addressed here consists in determining the number and composition of equal size impression grids, as well as the number of times each grid is printed, in order to fulfill the demand of different book covers at minimum total printing cost. The considered costs come from printing sheets and for composing grids. Thus, to deal with this combinatorial optimization problem we investigated two heuristics: one combines simulated annealing and linear programming techniques and the other is a hybrid of Tabu Search and an ad hoc procedure. Through intensive testing on available instances, these algorithms proved to be superior to previous approaches.


---

## Body

## 1. Introduction

This paper deals with a scheduling problem motivated by the printing industry. We will refer to it as the cover printing problem, although including its variants is also known as the job splitting [1], the label printing [2, 3], and the advertisement printing [4] problem.Central to the process of producingm types of equal size book covers is to print an impression grid (or press, template, master, etc.) composed of a set of t equal size plates, where some of them may be identical. To fulfill a given demand of book covers interrelated decisions must be made on the number and composition of impression grids (grids, for short) and on the amount of imprints made with each. One imprint of a grid produces one large printed sheet of paper which, once cut into t parts, yields t cover copies.Two constants are relevant to the decision process: the cost for printing one sheetC1 and the cost for composing one grid C2. Thus, the cover printing problem (CPP) consists in determining —at minimum total cost—the number and composition of grids, and the number of imprints made with each, so as to fulfill the required demand for each type of cover.A Toy Example. Let m=5 be the number of covers, t=4 the grid size, and (12,18,44,47,79) the required demand vector, for a total of 200 copies. A feasible solution of the CPP is found by composing k=3 grids as described by the (m×k)-matrix A=(aij) of (1) (matrices B to be discussed later), where aij is the number of plates of cover i in grid j, and ∑i=1m‍aij=t, for j=1,2,3. Then, if grids 1, 2, 3, are printed 29, 16, and 22 times, respectively, the covers’ demand is satisfied. Observe that 29+16+22=67 imprints are made, producing 67t=268 copies, with 268-200=68 wasted, namely, 34% of wastage. Further, 67C1+3C2 is the total cost of this solution, whose optimality clearly depends on the relative values of C1 and C2.(1)Matrices  corresponding  to  selected  solutions  of  the  toy  example.200011002030201A1001110001111111122002101B010101011111111010211B^0102101120B∗The computational complexity of the CPP is not known to date. However, some special cases have been polynomially solved by Ekici et al. [1] and Romero & Alonso-Pecina [5]. On the other hand, the CPP is stronglyNP-hard when C1≫C2 [1]. Besides a handful of graduate thesis (namely, four Belgian graduate thesis cited in [6–8], not available to the authors, and the Latin American graduate thesis by Calderón [9] and Carrera [10]) few internationally published papers have studied heuristic approaches for this highly combinatorial problem and its variants. These approaches are assorted, going from simulated annealing (Teghem et al. [7], Yiu et al. [3]) to GRASP (Tuyttens & Vandaele [8, 11]), as well as from evolutionary algorithms (Elaoud et al. [6], Hsieh et al. [2]) to ad hoc heuristics (Ekici et al. [1], Mohan et al. [4], and Romero & Alonso-Pecina [5]).Several CPP variants have been investigated. Romero & Alonso-Pecina [5] proposed to add a Hamiltonian path procedure to their ad hoc heuristic when there is also a cost for each produced plate. Other variants consist in the inclusion of additional constraints: while Mohan et al. [4] tackle the case of lower and upper bounds on the number of imprints made with each grid, Yiu et al. [3] and Mohan et al. [4] assume the number of grids as prescribed. Finally, Yiu et al. [3], Hsieh et al. [2], and Tuyttens & Vandaele [11] consider the constraint that all copies of any cover should be produced by one single grid.The aim of this paper is to propose two new heuristics to successfully approach the solution of the CPP. One, hybridized with linear programming, has the simulated annealing technique as motif; the other strategically combines Tabu Search and ad hoc procedures. We are witnessing a recent, interesting trend about the hybridization of metaheuristics and other techniques for optimization, like local search or exact algorithms (see the excellent survey by Blum et al. [12], as well as Gomes & Oliveira [13], Caserta & Voss [14], Popović et al. [15], López-Ibáñez et al. [16], and Mestria [17], among others). Such types of hybridization are intended to take advantage of strengths from each algorithm to improve the algorithms’ performance when solving different combinatorial optimization problems.This paper is organized as follows. Section2 provides an integer programming formulation of the CPP. Then, our simulated annealing programming and Tabu Search/ad hoc heuristics are described in Sections 3 and 4, respectively. Computationally tested on the 88 instances available in the specialized literature, our heuristics, taken together, improved the known best solution of more than two-thirds of them; this is discussed in Section 5. Finally, Section 6 contains our conclusions.


## 2. Integer Programming Formulation

The following mathematical formulation of the cover printing problem improves on the one proposed by us in [5]. Let M={1,…,m}, (d1,…,dm) and t, C1, and C2 be the set of covers, the requirements vector, the grid size, the cost for printing one sheet, and the cost for composing one grid, respectively. Without loss of generality assume 0<d1≤d2≤⋯≤dm. Letting N={1,…,n} be the set of possible impression grids, where n can be computed as n=m+t-1t, consider the m-by-n matrix A=(aij) where aij is the number of plates of cover i in grid j. Obviously each A column sums up to t.Thus, the CPP can be posed as one problem of integer programming:PminC1∑j∈Nxj+C2∑j∈Nwjsubjectto∑j∈Nxjaij≥dii∈M,1xj≤wjdmj∈N,2xj≥0andintegerj∈N,3wj∈0,1j∈N,4where xj and wj are the decision variables, with wj=1 if and only if grid j is selected and xj being the number of its imprints. Problem P is intractable since the number n of possible grids is exponential. For the toy example of Section 1 we have n=70, yielding 140 integer variables and 3n+m=215 constraints.LetB=(bij) be an m-by-k submatrix of A, whose columns have been reindexed, 1,…,k, and consider the integer programming problemQmin∑j=1kxjsubjectto∑j=1kxjbij≥dii∈M,5xj≥0j=1,…,k,6xjintegerj=1,…,k.7Obviously, any feasible solution ofQ can be extended to an also feasible solution of problem P by making xj=0 for all A columns not belonging to B, and wj=1⟺xj>0 for j∈N. In the sequel we assume this extension is implicitly made.It has been remarked [1, 5] that no feasible solution to the CPP exists with less than ⌈m/t⌉ grids, and there is no optimal solution to the CPP with more than m grids. Hence, define Ω as the set of m-by-k submatrices of A without zero rows, with k satisfying ⌈m/t⌉≤k≤m.Now, forB∈Ω, denote by X′(B) the optimal solution of problem Q, and denote by X(B) the rounded up, optimal solution of problem Q when solved without integrality constraints (7). From the previous paragraph not only the pair (B,X(B)) is a feasible solution to the CPP, but there exists B∗∈Ω such that (B∗,X′(B∗)) is an optimal solution to the CPP.In view of the high demand values normally found in the internationally published instances (most demand values are between104 and 105[6–8]), in our approach we opted to only deal with the CPP solutions of type (B,X(B)), considering its inherent error immaterial.


## 3. Simulated Annealing/Linear Programming Approach

In this section we present the first of the two heuristic approaches we propose for the solution of the cover printing problem. This heuristic—we call itsalp—is centered in the simulated annealing concept hybridized with linear programming techniques. A recent, good overview of simulated annealing can be found in [18], and for linear programming we refer the reader to [19].salp is similar in essence to the Teghem et al. proposal [7]; however, arising from the final remarks of Section 2, it differs in regard to the neighborhood definition. Namely, for a given matrix B=(bij)∈Ω, theneighborhood of solution S=(B,X(B)) is the set N(S) containing every solution (Bˇ,X(Bˇ)) such that Bˇ∈Ω is obtainable from B by either(i)
adding 1 tobu,w and subtracting 1 from bv,w, for some indexes u,v,w, or(ii)
adding 1 tobu,w and bv,x and subtracting 1 from bu,x and bv,w, for some indexes u,v,w,x.Thus,salp consists in performing the procedureanneal followed by the procedurerefinement, the former drawing upon procedureslinprog,rand,initialsol,resize, andneighbor. Each is described below. We thoroughly assume all random numbers are generated with uniform probability distribution.linprog ( B ). Given an m-by-k matrix B=(bij)∈Ω, this procedure consists of a standard implementation of the Simplex method for linear programming. It is aimed at finding X(B)=(x1,…,xk) as defined in Section 2, namely, the rounded up optimum of the linear programming relaxation of problem Q. Hence, the solution S=(B,X(B)) is delivered, as well as its cost z(S)=C1∑j=1k‍xj+C2×n>0, where n>0 stands for the number of positive entries in X(B). Recall that C1 and C2 are the unit costs for sheet printing and grid composing, respectively. Although the Simplex method has computational complexity Ok+mm, its general good behavior is a well known fact: the observed average of iterations is roughly 1.5m.initialsol. An initial, feasible solution to CPP is built in two steps. First, an m-by-m matrix Bo=(bij)∈Ω is constructed, where bij is randomly generated in the set {0,1,…,t}, for (i,j)∈M×M, ensuring that Bo has no zero rows, and each of its columns sums up to t. It proceeds as follows: Lines (1) to (10) build an integer, nonnegative matrix with no zero rows, whose column sums are equal t or less; then lines (11) to (20) ensure that each column sums up to t. To end, procedurelinprog(Bo) is called to determine X(Bo), completing the construction of the initial solution So=(Bo,X(Bo)), and its cost z(So).The overall complexity of this procedure isOm2+k+mm, namely, the same as that forlinprog(B) (Algorithm 1).Algorithm 1:Procedure initialsol.
(1) Bij←0, ∀i,j∈M×M; (2)i←1; (3)While  i≤m  do (4)ban←false; (5)While  ban≠true  do (6)j←⌊RAND×m⌋+1; (7)If  ∑i∈M‍Bij<t  then  Bij←Bij+1; ban←true; (8)EndWhile; (9)i←i+1; (10)EndWhile; (11)j←1; (12)While  j≤m  do (13)cont←∑i∈M‍Bij; (14)While  cont<t  do (15)i←⌊RAND×m⌋+1; (16)Bij←Bij+1; (17)cont←cont+1; (18)EndWhile (19)j←j+1; (20)EndWhile; (21)[z0,X(B0)]←linprog(B0).rand. This function delivers a random real number in the interval (0, 1).neighbor ( S ). Using the neighborhood N as defined in the first paragraph of this section, this procedure—of computational complexity O(mk)—randomly produces a feasible solution in N(S).resize. This procedure takes a solution S=(B,X(B)) as input and produces a solution S′=(B′,X(B′)) as follows. First B′←B and let q be the number of zeros in X(B′). If q≥2 then delete the first q-1 columns j such that xj=0. Otherwise, if q=0 and B′ has less than m columns then a nonnegative integer column (α1,…,αm) is added to it, where(i)
∑i=1m‍αi=t,(ii)
|αr-αs|≤1, for all r,s∈[1,m], and(iii)
dr<ds implies αr≤αs, for all r,s∈[1,m].To end, procedurelinprog(B′) is called to determine X(B′) and cost z(S′), where S′=(B′,X(B′)). The computational complexity of this procedure is clearly O(m2). The rationale for this procedure is to allow the number of grills in the solutions found during the search to increase.anneal. This procedure basically consists of standard simulated annealing iterations where parameters φ,λ,To,Tf, denote, resp., the cooling factor, the internal cycle length, the initial temperature, and the final temperature (Algorithm 2).Algorithm 2:Procedure anneal.
initialsol; [to generate So=(Bo,Xo) and z(So)] S ← S o; z m i n ← z ( S o ); θ ← T o; [variable θ holds the system temperature] S a c t ←  resize(S); S b e s t ← S a c t; While  θ≥Tf  do w ← 0; While  w≤λ  do S ←  neighbor(Sact); linprog ( S ); δ ← z ( S ) - z ( S a c t ); If  δ<0  or  rand<e-δ/θ  then S a c t ← S; Sact←  resize(S); EndIf w ← w + 1; If  z(Sact)<z(Sbest)  then S b e s t ← S a c t; w←0; EndIf EndWhile θ ← φ θ; EndWhile.The complexity of the algorithm is given by the number of times the two cycles are performed times the complexity oflinprog(S). While the first cycle is performed until T reaches Tf, say, κ times, where κ=(ln⁡Tf-ln⁡To)/ln⁡(θ) [20], the inner cycle is performed m×t times, andlinprog(S) has complexity k+mm. So, the total time is Oκmtk+mm.Above, we have pointed out that our proceduresalp is similar in essence to that of Teghem et al. [7]. Besides the fact that we use a different and larger neighborhood, the main difference between both approaches is that, along the search, in ours the number of grids equals the number of nonzero variables in the optimal solutions given by linear programming (LP), while in theirs it is just the opposite: the number of grids is determined by an element of the neighborhood employed in simulated annealing (SA). We mention that [7] is one of the pioneering papers on the CPP. Among the small instances I001–I004 considered therein, the authors found the optimal solution of two of them; while in our present approach as well as in those in [5, 8, 11] the four instances were solved to optimality.refinement. A local search procedure (LS) attempts to deterministically improve a given solution S∗. LS considers all the elements of N(S∗) one at a time; if none improves on cost z(S∗), the procedure stops; otherwise S∗ is replaced by the first found solution of N(S∗) with lower cost than S∗, and LS starts anew. The complexity of LS is that of entirely exploring the neighborhood N(S∗) multiplied by k+mm, namely, Om2k2×k+mm.Now, let us return to the toy example of Section1 and consider the matrices B0, B^, and B∗, in (1). Also, let C1=1 and C2=100, and assumeinitialsol generates S0=(B0,X(B0)), where X(B0)=(11,36,0,0,7) is obtained bylinprog. This is to say, solution S0 consists of three grids (columns 1, 2, and 5 of B0), imprinted 11, 36, and 7 times, respectively, yielding z(S0)=354.TakingB0 as input, the procedureresize produces B^, X(B^)=(10,20,4,9), and z(B^)=443. Then, from B^ and after a few iterations,salp successively obtains B∗, X(B∗)=(44,12), S∗=(B∗,X(B∗)), and z(S∗)=256, which turns out to be the global optimum of the toy example.


## 4. Tabu Search/H Approach

Our second approach consists of the hybridization of two heuristics: the Tabu Search technique (TS) and an ad hoc procedure called hereH, whose aim is to provide an initial solution to TS.A thorough description of theH heuristic can be found in [5]; however, we find it convenient to sketch here its main idea: at each of the outer iterations a solution is sought that minimizes the number of required grids subject to the constraint that for any cover the wastage is lower or equal to a given upper bound. This upper bound is initialized with the maximum demand dm and is monotonically decreased in each outer iteration as long as new solutions are found or until it reaches zero. In the end, the solution with the minimum cost among those produced in the outer iterations is retained.Successfully used to tackle combinatorial optimization problems galore (see, for example, [21] and the references therein), Tabu Search [22] is based on a tabu list of forbidden movements that is updated during the iterations to avoid cycling and get stuck in local minima. Our approach TS/H considered an enlargement of the neighborhood N—defined in Section 3—so as to include the feasible solutions that can be obtained by deleting any one grid; we denote by NTS this neighborhood. In the pseudocode TS/H below the proceduresneigh(S) andnottabuneigh(S) produce the best feasible solution, respectively, in NTS and in NTS\T (Algorithm 3).Algorithm 3:Procedure TS/H.
(1) S←H(); (2)zmin←zact←z(S); (3)count←0; Sbest←S; iter←0; (4)T←⌀; Sact←  resize(S); (5)While  count≤ψ  do (6)Snew←neigh(S); (7)znew←z(Snew); (8)If  znew<zmin  then (9)Sbest←S←Snew; (10)zmin←z←znew; (11)count←0; (12)else (13)Snew←  nottabuneigh(S); (14)z←z(Snew); S←Snew; (15)update(T); (16)count←count+1; (17)EndIf (18)iter←iter+1; (19)EndWhile (20)return  Bbest;In line (1) a solutionS is heuristically produced by procedure H, which is hereupon used as initial solution by the Tabu Search algorithm. In lines (2–4) several variables are initialized, among them is a nonnegative integer m-by-m matrix T={Tij} to represent the tabu list (here, ⌀ denotes the zero matrix). The main cycle (5–19) is performed a maximum of ψ times without improving the best solution found. In our experiments we set ψ=100. The procedureneigh (line 6) obtains a solution (using first-best strategy) in the neighborhood NTS improving the best solution found so far (if such solution exists). The solution Snew is evaluated in lines (8–11); then, if Snew improves on the so far best solution found, the latter is updated and the integercount is reset (lines 9–11); otherwise (lines 13–17) the best solution without tabu status is chosen as Snew.In line 15 the functionupdate(T) makes Tij←iter+1+rand()∗(m-1) for each entry (i,j) of B that has been modified (recall that B is part of the solution Snew, as defined in Section 3). Thus, the entry (i,j) of matrix B cannot be changed as long as Tij≥iter; namely, it gets tabu status for a number of iterations randomly chosen in the range [1,m].The complexity of procedure TS/H is the complexity of H plus the TS complexity. From computational experimentation we found that, in general, 3×ψ is a reasonable upper bound for the number of times the main cycle of TS is performed. As 3×ψ is a constant, the complexity of Tabu Search comes to that of LS: Om2k2×k+mm. As this dominates that of H, O(d1m2tlog⁡(mt)) [5], the overall complexity of TS/H is Om2k2×k+mm.


## 5. Numerical Results

The procedures described in Sections3 and 4 were implemented on a computer with Xeon 3.5 GHz processor, 64 GB RAM, and g++ compiler in an Ubuntu Operating System. They were tested on all instances proposed in [8], available in www.matcuer.unam.mx/~davidr/cpp.html. Also, to find the global optimum of some instances we used the exact algorithm E described in [5].As for thesalp parameters we selected To=z(So) and Tf=1, because from our computational experiments they yielded, respectively, an average of accepted solutions close to 99%, and an average of accepted solutions of around 2.5%. Also, we experimentally found that in terms of solution quality and computational effort a desirable combination of cooling factor and cycle length was, respectively, φ=0.99 and λ=t×m. Each considered instance was solved 100 times.Tables1 and 2 show the achievements of our procedures for instances I001–I009 and I013–I016, compared with the best found in the literature. Global optima are marked with an asterisk (∗). The Appendix provides a detailed description of our solutions for I013–I016. In Table 1, column β indicates the number of times the best solution was obtained by SA/LP. In the case of instance I016, one hundred runs were made, the lower and the higher costs found being 264145 and 278778, respectively. Each run took 7×105 seconds on average.Table 1
Best known results for instancesI001–I009 and I013–I015.
Instance m t Best solution found Obtained by β worst solution I001 3 4 136 472∗ [5–8, 11] & SA/LP &H/TS 100 136 472∗ I002 4 4 247 916∗ [1, 5–8, 11] & SA/LP &H/TS 100 247 916∗ I003 5 4 1 851 948∗ [5, 8, 11] & SA/LP 86 1 856 155 I004 8 4 264 348∗ [1, 5, 6, 8, 11] & SA/LP &H/TS 100 264 348∗ I005 12 4 269 584∗ [5, 8, 11] & SA/LP &H/TS 33 286 384 I006 15 4 515 256∗ [5, 8, 11] & SA/LP &H/TS 4 530 180  I007 9 8 5 283.53∗ [5] & SA/LP &H/TS 73 5 465.95 I008 17 8 11 455.64 (11 400.27∗) SA/LP 8 11 839.52 I009 18 7 11 052.09 (11 047.96∗) SA/LP 1 11 601.24  I013 30 4 1 745 800 SA/LP 1 1 801 828 I014 40 4 2 557 828 SA/LP 1 2 615 480 I015 50 4 6 507 340 SA/LP 1 6 599 908Table 2
Comparison of our results with the previous best for instanceI016.
GRASP [11] SA/LP Instance m t cost wastage cost wastage I016 100 25 264 697 1.939% 264 145 1.705%To test several heuristics, a set of 15 instances, see [5, 8, 11], all with t=4, has been used in combination with grid costs: 4C2,2C2,C2,0.5C2,0.25C2 (C2=18676), yielding a total of 75 cases. Table 3 displays our results on this set, comparing them with the best found so far, namely, those obtained with GRASP [11] (excepting instance 50-4 with grid cost C2). The first portion of the instance name corresponds to the number m of covers. For each of the 75 cases the best results are shown in bold face. An asterisk (∗) marks global optima (when able to compute them). The number of times SA/LP obtains the best solution is 17 for instance (30-1,4C2), nine for instance (30-4,4C2), five for instance (30-3,4C2), two for instances (30-2,4C2), (30-5,4C2), (40-1,4C2), (40-2,4C2), (40-3,4C2), and (30-3,2C2), and once for the remaining 66 instances. On average, linear programming took 97.65% of the total time of each run.Table 3
Results for instances 30-x, 40-x, and 50-x with five distinct grid costs. All results obtained with GRASP come from [11].
Instance Method 4C2 2C2 C 2 0.5C2 0.25C2 30-1 GRASP 2 252 096 ∗ 1 946 280 1 774 024 1 674 526 1 623 167 H/TS 2 252 096 ∗ 1 942 248 1 774 938 1 678 558 1 625 376 SA/LP 2 252 096 ∗ 1 933 512 ∗ 1 765 288 1 673 252 1 625 820 30-2 GRASP 2 139 200 1 832 040 1 657 096 1 563 716 1 516 991 H/TS 2 140 544 1 832 040 1 659 784 1 566 404 1 519 714 SA/LP 2 137 856 ∗ 1 822 632 ∗ 1 654 548 1 563 044 1 519 007 30-3 GRASP 2 396 576 2 083 368 1 903 048 1 802 878 1 749 468 H/TS 2 392 544 ∗ 2 093 728 1 908 424 1 806 840 1 749 468 SA/LP 2 392 544 ∗ 2 082 024 1 900 360 1 802 206 1 750 175 30-4 GRASP 2 930 816 ∗ 2 618 000 2 427 740 2 324 280 2 266 873 H/TS 2 937 536 2 613 296 2 427 068 2 323 272 2 266 201 SA/LP 2 930 816 ∗ 2 604 560 2 425 864 2 323 608 2 269 897 30-5 GRASP 3 064 656 2 728 488 2 537 733 2 429 112 2 371 033 H/TS 3 082 688 2 741 648 2 541 168 2 431 800 2 374 022 SA/LP 3 064 656 2 724 848 2 534 588 2 427 768 2 373 014  40-1 GRASP 4 931 696 4 509 512 4 264 353 4 133 621 4 062 366 H/TS 4 931 696 4 520 824 4 273 304 4 141 088 4 066 384 SA/LP 4 912 880 4 490 304 4 262 552 4 135 782 4 068 330 40-2 GRASP 4 226 096 3 800 552 3 557 764 3 427 494 3 355 744 H/TS 4 233 488 3 808 616 3 562 328 3 427 494 3 356 717 SA/LP 4 215 344 3 786 048 3 552 388 3 428 838 3 365 418 40-3 GRASP 4 846 464 4 386 536 4 143 748 4 005 414 3 935 379 H/TS 4 836 944 4 389 224 4 145 484 4 005 414 3 937 024 SA/LP 4 822 832 4 378 752 4 141 592 4 018 854 3 949 421 40-4 GRASP 6 053 376 5 605 152 5 359 928 5 218 304 5 139 533 H/TS 6 066 032 5 604 200 5 361 412 5 218 304 5 138 826 SA/LP 6 037 920 5 590 368 5 358 584 5 218 304 5 149 960 40-5 GRASP 5 707 968 5 247 368 4 993 548 4 848 032 4 769 898 H/TS 5 717 936 5 262 152 5 000 268 4 848 634 4 770 234 SA/LP 5 684 336 5 239,976 4 991 000 4 854 010 4 779 607  50-1 GRASP 6 850 592 6 301 568 6 002 752 5 849 914 5 764 388 H/TS 6 844 432 6 300 504 6 009 472 5 849 102 5 760 391 SA/LP 6 827 744 6 296 472 6 004 628 5 860 526 5 778 360 50-2 GRASP 8 650 992 8 070 272 7 771 456 7 609 070 7 518 308 H/TS 8 649 648 8 062 880 7 764 064 7 603 834 7 520 324 SA/LP 8 619 296 8 066 520 7 781 396 7 625 870 7 540 078 50-3 GRASP 9 599 184 9 038 904 8 720 040 8 547 854 8 455 006 H/TS 9 595 824 9 030 840 8 716 008 8 545 096 8 450 122 SA/LP 9 581 600 9 035 264 8 732 136 8 567 874 8 471 325 50-4 GRASP 10 217 424 9 650 536 9 314 480 9 127 720 9 026 171 H/TS 10 235 008 9 639 504 9 309 776 9 124 290 9 024 827 SA/LP 10 199 280 9 641 800 9 316 636 9 139 676 9 038 834 50-5 GRASP 10 628 688 10 050 656 9 717 960 9 536 296 9 440 795 H/TS 10 656 240 10 051 048 9 718 352 9 531 592 9 437 505 SA/LP 10 624 656 10 051 048 9 730 905 9 554 300 9 458 869We observe the dominance of SA/LP for instances 30-x when the grid cost is in the range [0.5C2,4C2], for instances 40-x when this cost is in the range [C2,4C2] and for instances 50-x when the cost is 4C2. Also, SA/LP seems the best choice when the grid cost is relatively high or the number of covers is low. In total, SA/LP finds the best result in 45 of the 75 instances (including ties).As of heuristicH/TS, it finds the best result for instance 30-4 when the cost is 0.25C2 or 0.5C2, for instances 40-2, 40-3, and 40-4 when the cost is 0.5C2, for instance 40-4 when the cost is 0.25C2, and for instances 50-x when the cost is in the range [0.25C2,0.5C2], with one case excepted. Thus, H/TS seems the best when the number of covers is high and the grid cost is small. All in all, H/TS finds the best result in 24 of the 75 instances (ties included).For its part, GRASP dominates in instances 30-x with cost0.25C2, in instances 40-x with cost in the range [0.25C2,0.5C2], and in instances 50-x with several combinations of instance-cost; it obtains the best result four times. GRASP seems to be the best option when the grid cost is small and the number of covers is below 40. Altogether, GRASP finds the best results in 20 of the 75 instances (ties included).In regard to computational effort it is difficult to assess our proposal, and not only because GRASP was run on a computer different from ours. In the GRASP implementation, the number of grids is fixed, so the reported average execution times correspond to a given number of grids. Conversely, in SA/LP andH/TS the number of grids is a variable to be determined. In our experiments H/TS was run only once for each instance, because its behavior is nearly deterministic, the sole random component being the amount of time each element stays in the tabu list.Table4 shows the computer time needed by our two heuristics for instances 30-x, 40-x, and 50-x. The figures for SA/LP correspond to average times (in seconds) of one run. Clearly, none of the procedures has linear complexity; this largely explains the observed increase in time as m grows.Table 4
Average running time of our heuristics (in sec.). For SA/LP 100 runs were made.
Heuristic Instance set 30-x 40-x 50-x SA/LP (LP time) 45 155 436 SA/LP (Total time) 46 159 446  H/TS 85 218 758We also tested SA/LP andH/TS on 60 instances E001,…,E060 found in www.matcuer.unam.mx/~davidr/cpp.html, whose optimum is known. Table 5 shows the obtained results, where it can be seen that SA/LP gets indeed the optimum for the first 30 instances, and it outperforms H/TS for instances E031,…,E050. However, H/TS obtains the best solutions for E051,…,E060.Table 5
Performance of SA/LP andH/TS, for instances E0XX, with different mand t.
Instance m t Optimum SA/LP H/TS E001 13 6 51 750 51 750 ∗ 51 750 ∗ E002 13 6 51 606 51 606 ∗ 54 606 E003 13 6 56 686 56 686 ∗ 56 686 ∗ E004 13 6 51 257 51 257 ∗ 53 384 E005 13 6 56 322 56 322 ∗ 56 322 ∗ E006 13 6 51 803 51 803 ∗ 51 803 ∗ E007 13 6 56 272 56 272 ∗ 56 272 ∗ E008 13 6 59 104 59 104 ∗ 59 104 ∗ E009 13 6 52 855 52 855 ∗ 52 855 ∗ E010 13 6 53 778 53 778 ∗ 53 778 ∗  E011 25 8 80 749 80 749 ∗ 80 889 E012 25 8 78 369 78 369 ∗ 78 369 ∗ E013 25 8 83 369 83 369 ∗ 83 369 ∗ E014 25 8 71 417 71 417 ∗ 75 756 E015 25 8 75 762 75 762 ∗ 78 580 E016 25 8 82 608 82 608 ∗ 88 970 E017 25 8 85 839 85 839 ∗ 85 839 ∗ E018 25 8 74 488 74 488 ∗ 74 488 ∗ E019 25 8 77 548 77 548 ∗ 82 128 E020 25 8 77 670 77 670 ∗ 77 848  E021 41 10 110 779 110 779 ∗ 111 319 E022 41 10 115 729 115 729 ∗ 116 516 E023 41 10 112 568 112 568 ∗ 116 691 E024 41 10 118 169 118 169 ∗ 118 927 E025 41 10 103 499 103 499 ∗ 103 777 E026 41 10 100 873 100 873 ∗ 101 669 E027 41 10 105 308 105 308 ∗ 110 826 E028 41 10 106 658 106 658 ∗ 107 383 E029 41 10 98 331 98 331 ∗ 98 475 E030 41 10 109 138 109 138 ∗ 109 148  E031 61 12 145 705 146 549 151 894 E032 61 12 149 415 149 716 158 751 E033 61 12 143 983 144 296 150 224 E034 61 12 143 305 143 814 144 108 E035 61 12 138 134 138 521 139 318 E036 61 12 151 318 151 579 153 755 E037 61 12 142 725 142 776 149 208 E038 61 12 138 358 138 385 138 689 E039 61 12 142 520 142 520 ∗ 143 646 E040 61 12 143 932 144 473 150 242  E041 85 14 184 266 185 009 188 739 E042 85 14 181 953 182 731 183 641 E043 85 14 180 216 180 793 184 897 E044 85 14 187 387 188 392 191 421 E045 85 14 162 654 163 293 164 242 E046 85 14 177 954 178 031 178 662 E047 85 14 183 011 184 006 183 841 E048 85 14 188 604 189 230 189 349 E049 85 14 190 843 191 072 191 507 E050 85 14 175 522 176 270 177 200  E051 113 16 230 934 240 057 238 169 E052 113 16 216 732 226 391 223 205 E053 113 16 239 502 254 266 244 122 E054 113 16 217 150 223 559 218 052 E055 113 16 220 353 229 621 221 531 E056 113 16 218 323 226 786 224 245 E057 113 16 209 618 219 285 215 136 E058 113 16 220 605 230 901 223 054 E059 113 16 232 452 242 181 239 358 E060 113 16 232 409 242 633 239 624It is worth mentioning that a similar behavior can be observed for instances in Table3, where H/TS tends to dominate as m grows and C2 decreases.


## 6. Conclusions

In this paper we have presented two competitive procedures for the cover printing problem, SA/LP andH/TS, comparing their results with the best found for a selected set of 88 instances from the specialized literature. Our computer experiments show that our heuristics, taken together, although not dominating in all of these instances, allowed improving the known best solution of 68% of them, their success depending more on the characteristics of the problem treated.A total of 60 better results were obtained in the chosen set: five in the group of 13 instances of typeIxxx and 55 in the large group of 75 instances.It is worth mentioning that one of the advantages of our heuristics is that none of them requires presetting the number of grids.For future work it is desirable to intensify the study of new, original approaches to this difficult combinatorial optimization problem, so as to better understand its intricacies and provide improved solutions.



---

*Source: 6193649-2018-08-27.xml*