Cover Printing Problem

The instance files have the following format. All numbers, with the exception of the cost per impression and cost per grid are always integers, all intra-line separators are spaces.

First line:
Number of covers;

Second line:
Grid size;

One line for each cover:
Demand of cover;

Last line:
Cost per impression; Cost per grid;

For example, for an instance having three covers with demand 4500, 9000 and 16000, respectively, with a grid size of 4, with an impression cost 13.44 and a grid cost 18676, the file would have the following format:

3
4
4500
9000
16000
13.44 18676

2. Solutions Format

The solution file has the following format. All numbers, excepting the total cost are always integers (all intra-line separators are spaces). The files have the extension .out and a plain text format.

First line:
Number of grids (N_g);

One line for each grid:
Grid composition, namely, and m-vector whose elements are non-negative integers summing up to t (gridsize), all integers separated by spaces.

Next line:
Number of imprints of each grid; N_g integers separated by spaces.

This line has a vector of size N_g, the first integer is the number of imprints of the first grid, the second integer is the number of imprints of the second grid, and so on.

Last line:
Total cost, computed as the total number of imprints times the impression cost, plus the number of grids multiplied by the grid cost.

As an example takes the above input file with 3 covers, then a possible solution in the output file could be:

0 1 3

2 2 0

5334 2250

139280.96

The first line indicates that in this solution two grids are to be composed. The second and third lines describe the composition of the first and second grids, respectively; namely the first grid is composed by one plate of the second cover and three plates of the third cover. the second grid is composed by two plates of the first cover and two plates of the second cover. The fourth line indicates that the first grid is to be printed 5334 times and the second grid 2250 times. The total cost is:

T_c = 13.44 * (5334 + 2250) + 2 * 18676 = 101928.93 + 37352 = 139280.96

which is the last line in the file.

3. Datasets

The source for instances below is indicated in brackets. All files instances have extension .in and plain text format. You can download all instances here: Download all instances.

This page contains five sets of instances, each in one separate table. The first set comes from several sources. The second set corresponds to cases where no cost is given because the objective function is to minimize the paper wasted. The third set of instances was generated with known optimal solutions. The fourth set contains random instances from [1], and the fifth set contains random instances from [14].

3.1 Instances from several sources

The next table provides thirteen instances where m is the number of covers and t is the gridsize. The first column contains the instance file and the source in brackets. The second and third columns contain the size of m and t, respectively. In the fourth column, we give in brackets the source for the best known solutions, and an asterisk (*) indicates that the value corresponds to the global optimum. The fifth column contains the solution file.

Instance	m	t	Best known solution	Solution file
I001.in [12]	3	4	136,472^* [1,10,12,14]	I001.out
I002.in [12]	4	4	247,916^* [1,3,10,12,14]	I002.out
I003.in [12]	5	4	1,851,948^* [1,14]	I003.out
I004.in [12]	8	4	264,348^* [1,3,12,14]	I004.out
I005.in [8]	12	4	269,584* [1,14]	I005.out
I006.in [12]	15	4	515,256* [1,14]	I006.out
I007.in [15]	9	8	5,283.53* [1]	I007.out
I008.in [15]	17	8	11,475.52 [1]	I008.out
I009.in [15]	18	7	11,191.6 [1]	I009.out
I013.in [14]	30	4	1,759,240 [14]	I013.out
I014.in [14]	40	4	2,575,832 [1]	I014.out
I015.in [14]	50	4	6,534,556 [1]	I015.out
I016.in [1]	100	25	265,918 [1]	I016.out

3.2 Instances without costs

The next table provides eight instances where the cost per impression and the cost per grid are unknown. In these instances one looks for minimizing the paper waste for a prescribed number of grids. The waste is computed as one hundred multiplied by the total surplus divided by the total demand. In these instances the solution file contains the percentage of waste instead of the total cost. The first column contains the instance file and the source in brackets. The second and third columns contain the size of m and t, respectively. The fourth column is the prescribed number of grids. In the fifth column of this table, the brackets indicated the source where the best solutions were obtained, an asterisk (*) indicates that the value corresponds to the global optimum.

Instance	m	t	Number of grids	Waste of the best known solution	Solution file
I010.in [13]	6	4	2	7.533%* [1,13]	I010A.out
I010.in [13]	6	4	3	1.095%* [1]	I010B.out
I011.in [11]	18	14	3	5.119% [1]	I011A.out
I011.in [11]	18	14	4	0.771% [1]	I011B.out
I011.in [11]	18	14	5	0.437% [1]	I011C.out
I012.in [11]	22	15	3	6.392% [1]	I012A.out
I012.in [11]	22	15	4	2.452% [1]	I012B.out
I012.in [11]	22	15	5	0.482% [1]	I012C.out

3.3 Instances with known optima

This table contains 60 instances generated in [1], and whose optimal solutions were previously determined. See [1] for a description of the optimal solutions. These instances were heuristically solved as it is described in [1], yielding the results shown in the last three columns of the table. The fourth column corresponds to the optimal cost.

Instance	m	t	Optimal cost	Obtained cost [1]	CPU Time (seconds)	Solution file
E001.in	13	6	51,750	54,750	1	E001.out
E002.in	13	6	51,606	54,606	1	E002.out
E003.in	13	6	56,686	56,686	1	E003.out
E004.in	13	6	51,257	54,257	1	E004.out
E005.in	13	6	56,322	56,322	1	E005.out
E006.in	13	6	51,803	54,803	2	E006.out
E007.in	13	6	56,272	59,272	2	E007.out
E008.in	13	6	59,104	59,104	1	E008.out
E009.in	13	6	52,855	52,855	1	E009.out
E010.in	13	6	53,778	53,778	1	E010.out
E011.in	25	8	80,749	84,005	5	E011.out
E012.in	25	8	78,369	78,684	0	E012.out
E013.in	25	8	83,369	83,704	1	E013.out
E014.in	25	8	71,417	77,494	3	E014.out
E015.in	25	8	75,762	81,464	4	E015.out
E016.in	25	8	82,608	88,970	0	E016.out
E017.in	25	8	85,839	86,134	0	E017.out
E018.in	25	8	74,488	78,311	4	E018.out
E019.in	25	8	77,548	83,991	3	E019.out
E020.in	25	8	77,670	84,019	0	E020.out
E021.in	41	10	110,779	117,319	33	E021.out
E022.in	41	10	115,729	122,591	29	E022.out
E023.in	41	10	112,568	116,775	28	E023.out
E024.in	41	10	118,169	124,564	29	E024.out
E025.in	41	10	103,499	106,863	23	E025.out
E026.in	41	10	100,873	105,407	18	E026.out
E027.in	41	10	105,308	111,470	22	E027.out
E028.in	41	10	106,658	110,383	26	E028.out
E029.in	41	10	98,331	104,552	21	E029.out
E030.in	41	10	109,138	112,839	25	E030.out
E031.in	61	12	145,705	153,481	98	E031.out
E032.in	61	12	149,415	158,751	67	E032.out
E033.in	61	12	143,983	150,500	69	E033.out
E034.in	61	12	143,305	147,910	102	E034.out
E035.in	61	12	138,134	144,670	66	E035.out
E036.in	61	12	151,318	157,823	75	E036.out
E037.in	61	12	142,725	152,127	59	E037.out
E038.in	61	12	138,358	141,690	65	E038.out
E039.in	61	12	142,520	148,396	70	E039.out
E040.in	61	12	143,932	150,316	91	E040.out
E041.in	85	14	184,266	188,739	174	E041.out
E042.in	85	14	181,953	188,797	162	E042.out
E043.in	85	14	180,216	187,595	9	E043.out
E044.in	85	14	187,387	194,373	263	E044.out
E045.in	85	14	162,654	169,008	150	E045.out
E046.in	85	14	177,954	185,086	10	E046.out
E047.in	85	14	183,011	189,472	204	E047.out
E048.in	85	14	188,604	190,223	50	E048.out
E049.in	85	14	190,843	194,012	102	E049.out
E050.in	85	14	175,522	182,728	212	E050.out
E051.in	113	16	230,934	239,792	22	E051.out
E052.in	113	16	216,732	224,021	178	E052.out
E053.in	113	16	239,502	247,076	19	E053.out
E054.in	113	16	217,150	221,105	20	E054.out
E055.in	113	16	220,353	222,348	18	E055.out
E056.in	113	16	218,323	224,692	22	E056.out
E057.in	113	16	209,618	215,806	213	E057.out
E058.in	113	16	220,605	227,740	29	E058.out
E059.in	113	16	232,452	240,263	24	E059.out
E060.in	113	16	232,409	240,615	31	E060.out

3.4 Random instances from [1]

The next table corresponds to 120 random instances generated in [1]. These instances were heuristically solved as it is described in [1], yielding the results shown in the last three columns of the table.

Instance	m	t	Obtained cost [1]	CPU Time (seconds)	Solution file
R001.in	10	6	112,431	0	R001.out
R002.in	10	6	95,990	2	R002.out
R003.in	10	6	89,566	0	R003.out
R004.in	10	6	91,024	1	R004.out
R005.in	10	6	124,168	0	R005.out
R006.in	10	6	95,290	0	R006.out
R007.in	10	6	89,476	1	R007.out
R008.in	10	6	64,539	1	R008.out
R009.in	10	6	107,766	0	R009.out
R010.in	10	6	106,115	0	R010.out
R011.in	10	8	82,792	1	R011.out
R012.in	10	8	87,978	0	R012.out
R013.in	10	8	78,361	0	R013.out
R014.in	10	8	77,106	0	R014.out
R015.in	10	8	66,712	0	R015.out
R016.in	10	8	76,878	0	R016.out
R017.in	10	8	62,817	0	R017.out
R018.in	10	8	74,172	0	R018.out
R019.in	10	8	88,894	0	R019.out
R020.in	10	8	76,921	0	R020.out
R021.in	25	12	128,601	0	R021.out
R022.in	25	12	124,816	1	R022.out
R023.in	25	12	120,665	1	R023.out
R024.in	25	12	134,819	3	R024.out
R025.in	25	12	132,306	0	R025.out
R026.in	25	12	127,978	2	R026.out
R027.in	25	12	116,859	0	R027.out
R028.in	25	12	122,974	1	R028.out
R029.in	25	12	139,761	3	R029.out
R030.in	25	12	152,855	6	R030.out
R031.in	25	16	101,560	1	R031.out
R032.in	25	16	107,327	2	R032.out
R033.in	25	16	108,926	0	R033.out
R034.in	25	16	117,534	1	R034.out
R035.in	25	16	90,293	1	R035.out
R036.in	25	16	92,473	1	R036.out
R037.in	25	16	92,256	1	R037.out
R038.in	25	16	106,009	0	R038.out
R039.in	25	16	107,913	2	R039.out
R040.in	25	16	96,324	0	R040.out
R041.in	50	16	189,253	21	R041.out
R042.in	50	16	195,627	22	R042.out
R043.in	50	16	196,666	13	R043.out
R044.in	50	16	201,876	12	R044.out
R045.in	50	16	222,999	17	R045.out
R046.in	50	16	186,412	11	R046.out
R047.in	50	16	185,067	13	R047.out
R048.in	50	16	184,252	12	R048.out
R049.in	50	16	210,386	12	R049.out
R050.in	50	16	202,643	10	R050.out
R051.in	50	20	145,113	13	R051.out
R052.in	50	20	151,544	16	R052.out
R053.in	50	20	145,687	20	R053.out
R054.in	50	20	162,260	14	R054.out
R055.in	50	20	172,883	16	R055.out
R056.in	50	20	145,464	15	R056.out
R057.in	50	20	145,331	15	R057.out
R058.in	50	20	169,324	16	R058.out
R059.in	50	20	167,109	14	R059.out
R060.in	50	20	159,751	15	R060.out
R061.in	100	12	501,975	87	R061.out
R062.in	100	12	484,739	92	R062.out
R063.in	100	12	532,763	136	R063.out
R064.in	100	12	483,623	136	R064.out
R065.in	100	12	549,673	93	R065.out
R066.in	100	12	499,255	95	R066.out
R067.in	100	12	527,716	138	R067.out
R068.in	100	12	503,971	138	R068.out
R069.in	100	12	531,249	115	R069.out
R070.in	100	12	492,351	155	R070.out
R071.in	100	16	383,644	193	R071.out
R072.in	100	16	385,382	172	R072.out
R073.in	100	16	350,177	223	R073.out
R074.in	100	16	393,316	142	R074.out
R075.in	100	16	377,347	199	R075.out
R076.in	100	16	384,201	203	R076.out
R077.in	100	16	362,790	136	R077.out
R078.in	100	16	383,286	249	R078.out
R079.in	100	16	380,421	146	R079.out
R080.in	100	16	408,601	398	R080.out
R081.in	100	25	254,163	242	R081.out
R082.in	100	25	255,910	252	R082.out
R083.in	100	25	265,873	285	R083.out
R084.in	100	25	260,092	321	R084.out
R085.in	100	25	251,314	267	R085.out
R086.in	100	25	233,874	269	R086.out
R087.in	100	25	253,448	249	R087.out
R088.in	100	25	246,531	306	R088.out
R089.in	100	25	246,524	210	R089.out
R090.in	100	25	249,321	295	R090.out
R091.in	25	8	195,326	2	R091.out
R092.in	25	8	183,406	0	R092.out
R093.in	25	8	192,144	0	R093.out
R094.in	25	8	213,047	2	R094.out
R095.in	25	8	154,142	2	R095.out
R096.in	25	8	184,489	0	R096.out
R097.in	25	8	212,729	0	R097.out
R098.in	25	8	172,726	2	R098.out
R099.in	25	8	195,025	2	R099.out
R100.in	25	8	207,749	1	R100.out
R101.in	50	12	259,020	22	R101.out
R102.in	50	12	259,208	26	R102.out
R103.in	50	12	246,165	9	R103.out
R104.in	50	12	255,621	11	R104.out
R105.in	50	12	257,999	14	R105.out
R106.in	50	12	245,518	11	R106.out
R107.in	50	12	273,008	27	R107.out
R108.in	50	12	281,626	29	R108.out
R109.in	50	12	255,731	24	R109.out
R110.in	50	12	275,057	25	R110.out
R111.in	100	20	298,734	320	R111.out
R112.in	100	20	306,723	166	R112.out
R113.in	100	20	327,041	256	R113.out
R114.in	100	20	293,234	177	R114.out
R115.in	100	20	299,499	197	R115.out
R116.in	100	20	296,731	203	R116.out
R117.in	100	20	314,614	214	R117.out
R118.in	100	20	327,867	213	R118.out
R119.in	100	20	286,527	205	R119.out
R120.in	100	20	313,083	296	R120.out

3.5 Random instances from [14]

The next table contains 75 random instances, kindly provided and heuristically solved [14] by Daniel Tuyttens of the University of Mons, Faculté Polytechnique, Belgium. The fourth column is the obtained cost in [14], the fifth and sixth columns are the obtained cost in [1] and the needed CPU time, respectively. The seventh column indicates the file containing the best known solution.

Instance	m	t	Obtained cost [14]	Obtained cost [1]	CPU Time (seconds)	File of the best solution
T001.in	30	4	2,268,224	2,252,096	1	T001.out
T002.in	30	4	2,164,736	2,145,920	1	T002.out
T003.in	30	4	2,408,000	2,413,376	1	T003.out
T004.in	30	4	2,977,856	2,937,536	1	T004.out
T005.in	30	4	3,116,288	3,082,688	2	T005.out
T006.in	40	4	4,956,448	4,931,696	1	T006.out
T007.in	40	4	4,287,136	4,235,504	3	T007.out
T008.in	40	4	4,937,632	4,863,824	2	T008.out
T009.in	40	4	6,137,824	6,097,168	1	T009.out
T010.in	40	4	5,789,168	5,717,936	3	T010.out
T011.in	50	4	6,911,632	6,863,248	2	T011.out
T012.in	50	4	8,683,248	8,655,024	1	T012.out
T013.in	50	4	9,748,144	9,607,920	6	T013.out
T014.in	50	4	10,351,712	10,255,168	7	T014.out
T015.in	50	4	10,832,080	10,673,040	13	T015.out
T016.in	30	4	1,969,408	1,950,312	1	T016.out
T017.in	30	4	1,860,264	1,833,384	1	T017.out
T018.in	30	4	2,109,184	2,103,528	1	T018.out
T019.in	30	4	2,676,072	2,626,736	1	T019.out
T020.in	30	4	2,768,920	2,741,648	1	T020.out
T021.in	40	4	4,569,712	4,520,824	2	T021.out
T022.in	40	4	3,857,392	3,824,632	3	T022.out
T023.in	40	4	4,467,848	4,407,368	2	T023.out
T024.in	40	4	5,679,576	5,611,592	1	T024.out
T025.in	40	4	5,322,352	5,268,872	2	T025.out
T026.in	50	4	6,355,328	6,327,104	2	T026.out
T027.in	50	4	8,122,968	8,070,272	2	T027.out
T028.in	50	4	9,750,776	9,047,640	5	T028.out
T029.in	50	4	9,711,520	9,655,632	7	T029.out
T030.in	50	4	10,158,792	10,082,240	13	T030.out
T031.in	30	4	1,804,656	1,778,056	1	T031.out
T032.in	30	4	1,684,648	1,662,929	1	T032.out
T033.in	30	4	1,931,132	1,915,004	1	T033.out
T034.in	30	4	2,452,464	2,436,476	1	T034.out
T035.in	30	4	2,563,484	2,549,372	2	T035.out
T036.in	40	4	4,298,700	4,275,320	2	T036.out
T037.in	40	4	3,594,444	3,569,244	2	T037.out
T038.in	40	4	4,182,976	4,148,172	2	T038.out
T039.in	40	4	5,396,468	5,368,524	2	T039.out
T040.in	40	4	5,021,492	5,001,612	1	T040.out
T041.in	50	4	6,056,512	6,028,288	3	T041.out
T042.in	50	4	7,800,744	7,771,456	2	T042.out
T043.in	50	4	8,770,692	8,720,040	4	T043.out
T044.in	50	4	9,336,516	9,317,840	8	T044.out
T045.in	50	4	9,766,596	9,725,744	13	T045.out
T046.in	30	4	1,692,600	1,678,558	1	T046.out
T047.in	30	4	1,585,080	1,569,549	1	T047.out
T048.in	30	4	1,818,866	1,810,200	1	T048.out
T049.in	30	4	2,338,994	2,326,296	1	T049.out
T050.in	30	4	2,445,170	2,437,778	2	T050.out
T051.in	40	4	4,155,732	4,144,588	1	T051.out
T052.in	40	4	3,451,546	3,429,174	2	T052.out
T053.in	40	4	4,033,428	4,008,102	2	T053.out
T054.in	40	4	5,236,308	5,220,992	2	T054.out
T055.in	40	4	4,862,746	4,858,784	3	T055.out
T056.in	50	4	5,873,224	5,859,784	2	T056.out
T057.in	50	4	7,625,870	7,615,048	1	T057.out
T058.in	50	4	8,571,836	8,551,956	4	T058.out
T059.in	50	4	9,140,418	9,124,962	9	T059.out
T060.in	50	4	9,570,288	9,538,984	13	T060.out
T061.in	30	4	1,634,521	1,626,492	1	T061.out
T062.in	30	4	1,529,052	1,522,668	1	T062.out
T063.in	30	4	1,757,462	1,752,121	1	T063.out
T064.in	30	4	2,274,902	2,267,545	1	T064.out
T065.in	30	4	2,381,008	2,374,358	2	T065.out
T066.in	40	4	4,071,690	4,067,658	2	T066.out
T067.in	40	4	3,370,689	3,359,139	2	T067.out
T068.in	40	4	3,949,386	3,938,067	3	T068.out
T069.in	40	4	5,151,559	5,141,514	1	T069.out
T070.in	40	4	4,779,908	4,771,879	2	T070.out
T071.in	50	4	5,777,086	5,766,404	2	T071.out
T072.in	50	4	7,532,987	7,521,668	3	T072.out
T073.in	50	4	8,465,723	8,455,006	4	T073.out
T074.in	50	4	9,033,458	9,026,843	9	T074.out
T075.in	50	4	9,458,232	9,441,467	12	T075.out

References

[1] D. Romero, F. Alonso-Pecina, Ad hoc Heuristic for the Cover Printing Problem, submitted to Elsevier

[2] Q.-S. Hua, Y. Wang, D. Yu, and F.C.M. Lau, Dynamic programming based algorithms for set multicover and multiset multicover problems, Theoretical Computer Science 411 (2010) 2467--2474.

[3] A. Ekici, O. Ergun, P. Keskinocak, and M.G. Lagoudakis, Optimal Job Splitting on a Multi-Slot Machine with Applications in the Printing Industry, Naval Research Logistics 57 (2010) 237--251.

[4] M. Balinski, A printing shop problem, personal communication, 1974.

[5] M. Naya, Problème du mariage des couvertures posé par la S.A. Casterman, Graduate Thesis, Faculté Polytechnique de Mons, Belgium, 1986.

[6] C. Antoniadis, Problème du mariage des couvertures: Résolution par la méthode du recuit simulé, Graduate Thesis, Université de Mons-Hainaut, Belgium, 1992.

[7] C. Carrein, Problème du mariage des couvertures par la méthode tabou, Graduate Thesis, Faculté Polytechnique de Mons, Belgium, 1994.

[8] G. Fasbender, A branch and price algorithm for the book cover printing problem, Graduate Thesis, Université Libre de Bruxelles, Belgium, 2000.

[9] L.E. Carrera, Algoritmo para encontrar el óptimo a una simplificación de un problema combinatorio presente en la industria editorial, Graduate Thesis, Mathematics Department, Cinvestav, Mexico City, 2006. (in Spanish)

[10] J. Teghem, M. Pirlot, C. Antoniadis, Embedding of linear programming in simulated annealing algorithm for solving a mixed integer production planning problem, Journal of Computational and Applied Mathematics 64 (1995), 91-102.

[11] K.F.C. Yiu, K.L. Mak, H.Y.K. Lau, A heuristic for the label printing problem, Computers and Operations Research 34 (2007), 2576-2588

[12] S. Elaoud, J. Teghem, B. Bouaziz, Genetic algorithm to solve the cover printing problem, Computers & Operations Research 34 (2007), 3346-3361.

[13] S.R. Mohan, S.K. Neogy, A. Seth, N.K. Garg, S. Mittal, An optimization model to determine master designs and runs for advertisement printing, Journal of Mathematical Modelling and Algorithms 6 (2007), 259-271.

[14] D. Tuyttens, A. Vandaele, Using a greedy random adaptative search procedure to solve the cover printing problem, Computers & Operations Research, Volume 37, (2010) Issue 4, 640-648.

[15] L. Trilling, Personal Communication, 2006.