An optimization model to determine master designs and runs for advertisement printing. (English) Zbl 1178.90354

Summary: In this paper we consider a common optimization problem faced by a printing company while designing masters for advertisement material. A printing company may receive from various customers, advertisements for their products and services and their demand is for a specified number of copies to be printed. In a particular case, the printer receives these orders to be delivered next week from the customers, until the Thursday of a week. By Monday the printed copies have to be delivered to the customers. These advertisement items of the various customers are to be printed on large sheets of papers of specified standard sizes. The size is called a \(k\)-up if \(k\) items can be printed on one sheet. It is a given constraint that only items of the same size can be loaded on a master. This constraint results in a decomposition of the original problem of designing masters into many sub-problems, one for each size. The objective is to minimize the number of masters required while meeting the requirements of the customers. We formulate this optimization problem mathematically, discuss the computational issues and present some heuristic approaches for solving the problem.


90C59 Approximation methods and heuristics in mathematical programming
90C90 Applications of mathematical programming
Full Text: DOI


[1] Balas, E., An additive algorithm for solving linear programs with zero-one variables, Oper. Res., 13, 517-546 (1965) · Zbl 0133.42701
[2] Geoffrion, A. M., Integer programming by implicit enumeration and balas method, SIAM Rev., 9, 178-190 (1967) · Zbl 0213.44702
[3] Feller, W., An Introduction to Probability Theory and Its Applications (1967), New York: Wiley, New York · Zbl 0158.34902
[4] Garfinkel, R.; Nemhauser, G. L., Integer Programming (1972), New York: Wiley, New York · Zbl 0259.90022
[5] Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), New York: Wiley, New York · Zbl 0652.90067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.