Le problème classique de l'industrie du papier consiste à générer un programme de coupe de façon à satisfaire les demandes des clients, tout en minimisant les pertes d epapier. Les méthodes utilisées sont généralement basées sur l'algorithme de génération de colonnes de Gilmore et Gomory. Dans plusieurs secteurs, les solutions qui s'appuient uniquement sur la minimisation des pertes de papier, ne satisfont pas pleinement les producteurs. ainsi, dans l'industrie du papier fin, on rencontre une grande variété de produits qui ne sont demandés qu'en faibles quantités. Les patrons sont utilisés moins longtemps sur les machines, occasionnant de fréquents ajustements qui occupent ainsi une part importante du temps de production. Il devient nécessaire de générer des solutions qui tiennent compte des deux critères: pertes en papier et coûts fixes dus aux ajustements.

Généralement, il existe plusieurs programmes de découpage qui donnent des pertes équivalentes. Nous proposons une post-optimisation qui, à partir des solutions du problème de minimisation des pertes, diminue le nombre de patrons nécessaires pour satisfaire la demande, sans pour autant augmenter les pertes en papier. On obtient une réduction moyenne de 16% dans dix problèmes types.