Optimization Online


A pseudo-polynomial size formulation for 2-stage two-dimensional knapsack problems

Fabio Furini (fabio.furini***at***dauphine.fr)
Enrico Malaguti (enrico.malaguti***at***unibo.it)

Abstract: Two dimensional cutting problems are about obtaining a set of rectangular items from a set of rectangular stock pieces and are of great relevance in industry, whenever a sheet of wood, metal or other material has to be cut. In this paper, we consider the 2-stage two-dimensional knapsack (2TDK) problem which requires finding the maximum profit subset of rectangular items obtain- able through 2-stage guillotine cuts in a rectangular panel. We propose a formulation having a pseudo-polynomial number of variables and constraints which can still be enumerated for the instances present in the literature. We compare the proposed formulation with the previous best known polynomial size one. Extensive computational experiments show that the new model is characterized by a stronger linear programming relaxation and can be effectively solved with a general-purpose MIP solver.

Keywords: 2-stage two-dimensional Knapsack problem, Mixed-Integer Programming models, computational experiments

Category 1: Integer Programming ((Mixed) Integer Linear Programming )


Download: [PDF]

Entry Submitted: 09/20/2013
Entry Accepted: 09/20/2013
Entry Last Modified: 03/28/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society