2026-06-08T08:39:23Zhttps://docta.ucm.es/rest/oai/requestoai:docta.ucm.es:20.500.14352/1166952025-01-29T00:49:17Zcom_20.500.14352_14col_20.500.14352_15
Docta Complutense
author
Lastra Díaz, Juan José
author
Ortuño Sánchez, María Teresa
2025-01-28T17:46:08Z
2025-01-28T17:46:08Z
2024
0377-2217
10.1016/j.ejor.2023.08.009
https://hdl.handle.net/20.500.14352/116695
https://doi.org/10.1016/j.ejor.2023.08.009
The irregular strip-packing problem, also known as nesting or marker making, is defined as the automatic computation of a non-overlapping placement of a set of non-convex polygons onto a rectangular strip of fixed width and unbounded length, such that the strip length is minimized. Nesting methods based on heuristics are a mature technology, and currently, the only practical solution to this problem. However, recent performance gains of the Mixed-Integer Programming (MIP) solvers, together with the known limitations of the heuristics methods, have encouraged the exploration of exact optimization models for nesting during the last decade. Despite the research effort, there is room to improve the efficiency of the current family of exact MIP models for nesting. In order to bridge this gap, this work introduces a new family of continuous MIP models based on a novel formulation of the NoFit-Polygon Covering Model (NFP-CM), called NFP-CM based on Vertical Slices (NFP-CM-VS). Our new family of MIP models is based on a new convex decomposition of the feasible space of relative placements between pieces into vertical slices, together with a new family of valid inequalities, symmetry breakings, and variable eliminations derived from the former convex decomposition. Our experiments show that our new NFP-CM-VS models outperform the current state-of-the art MIP models. Ten instances are solved up to optimality within one hour for the first time, including one with 27 pieces. Finally, we provide a detailed reproducibility protocol and dataset as supplementary material to allow the exact replication of our models, experiments, and results.
eng
Attribution-NonCommercial-NoDerivatives 4.0 International
Mixed-integer programming models for irregular strip packing based on vertical slices and feasibility cuts
journal article
UGFyYSBxdWUgZWwgcmVwb3NpdG9yaW8gaW5zdGl0dWNpb25hbCBkZSBsYSBVbml2ZXJzaWRhZCBkZSBNYWRyaWQgcHVlZGEgYWxtYWNlbmFyIHkgZGlzdHJpYnVpciBlbCBvYmpldG8gZGlnaXRhbCBkZXBvc2l0YWRvLCBlcyBuZWNlc2FyaW8gcXVlIGxhIHBlcnNvbmEgcXVlIGhhZ2EgZWwgZGVww7NzaXRvIGxlYSB5IGFjZXB0ZSBsYXMgY29uZGljaW9uZXMgZXN0YWJsZWNpZGFzIGVuIGVzdGEgbGljZW5jaWE6CuKAoiBBY2VwdGFuZG8gZXN0YSBsaWNlbmNpYSwgdXN0ZWQgY29tbyBhdXRvci9yZXMgeS9vIHByb3BpZXRhcmlvL3MgZGUgbG9zIGRlcmVjaG9zIGRlIHByb3BpZWRhZCBpbnRlbGVjdHVhbCwgbyBsYSBwZXJzb25hIGRlbGVnYWRhIHBhcmEgaGFjZXJsbyAsIG90b3JnYSBhbCByZXBvc2l0b3JpbyBkZSBsYSBVbml2ZXJzaWRhZCBDb21wbHV0ZW5zZSBkZSBNYWRyaWQgZWwgZGVyZWNobyBubyBleGNsdXNpdm8gZGUgcmVwcm9kdWNjacOzbiB5IGRpc3RyaWJ1Y2nDs24gZGUgc3Ugb2JyYSBlbiBjdWFscXVpZXIgZm9ybWF0byB5IG1lZGlvLgrigKIgRWwgZGVwb3NpdGFudGUsIGVuIGNhc28gZGUgdW5hIG9icmEgY29uIG3DoXMgZGUgdW4gYXV0b3IsIGdhcmFudGl6YSBxdWUgbG8gaGFjZSByZXNwb25zYWJsZW1lbnRlIGVuIG5vbWJyZSB5IGNvbiBjb25zZW50aW1pZW50byBkZSBsb3MgZGVtw6FzIGF1dG9yZXMuCuKAoiBBY2VwdGEgcXVlIGVsIHJlcG9zaXRvcmlvIGRlIGxhIFVuaXZlcnNpZGFkIENvbXBsdXRlbnNlIGRlIE1hZHJpZCBwdWVkYSBjb25zZXJ2YXIgbcOhcyBkZSB1bmEgY29waWEgZGUgZXN0ZSBkb2N1bWVudG8geSwgc2luIGFsdGVyYXIgc3UgY29udGVuaWRvLCBjb252ZXJ0aXJsbyBhIGN1YWxxdWllciBmb3JtYXRvIGRlIGZpY2hlcm8sIG1lZGlvIG8gc29wb3J0ZSwgcGFyYSBwcm9ww7NzaXRvcyBkZSBzZWd1cmlkYWQgeSBwcmVzZXJ2YWNpw7NuLgrigKIgRGVjbGFyYSBxdWUgZWwgZG9jdW1lbnRvIGVzIHVuIHRyYWJham8gb3JpZ2luYWwgc3V5bywgbyBxdWUgZXMgbGEgcGVyc29uYSBkZWxlZ2FkYSBwYXJhIHJlYWxpemFyIGVsIGRlcMOzc2l0byB5LCBwb3IgdGFudG8sIGN1ZW50YSBjb24gbGEgcG90ZXN0YWQgcGFyYSBvdG9yZ2FyIGxvcyBkZXJlY2hvcyBjb250ZW5pZG9zIGVuIGVzdGEgbGljZW5jaWEuIFRhbWJpw6luIGRlY2xhcmEgcXVlIHN1IGRvY3VtZW50byBubyBpbmZyaW5nZSBsbyBlc3RhYmxlY2lkbyBlbiBsYSB2aWdlbnRlIGxlZ2lzbGFjacOzbiBkZSBwcm9waWVkYWQgaW50ZWxlY3R1YWwuCuKAoiBTaSBlbCBkb2N1bWVudG8gY29udGllbmUgbWF0ZXJpYWxlcyBkZSBsb3MgY3VhbGVzIG5vIHRpZW5lIGxvcyBkZXJlY2hvcyBkZSBhdXRvciwgZGVjbGFyYSBxdWUgaGEgb2J0ZW5pZG8gZWwgcGVybWlzbyBzaW4gcmVzdHJpY2Npw7NuIGRlbCBwcm9waWV0YXJpbyBwYXJhIG90b3JnYXIgYSBsYSBVbml2ZXJzaWRhZCBDb21wbHV0ZW5zZSBkZSBNYWRyaWQgbG9zIGRlcmVjaG9zIHJlcXVlcmlkb3MgcG9yIGVzdGEgbGljZW5jaWEsIHkgcXVlIGVzZSBtYXRlcmlhbCwgY3V5b3MgZGVyZWNob3Mgc29uIGRlIHRlcmNlcm9zLCBlc3TDoSBjbGFyYW1lbnRlIGlkZW50aWZpY2FkbyB5IHJlY29ub2NpZG8gZGVudHJvIGRlbCBjb250ZW5pZG8gZGVsIGRvY3VtZW50by4K4oCiIFNpIGVsIGRvY3VtZW50byBzZSBiYXNhIGVuIHVuYSBvYnJhIHF1ZSBoYSBzaWRvIHBhdHJvY2luYWRhIG8gYXBveWFkYSBwb3IgdW5hIGFnZW5jaWEgdSBvcmdhbml6YWNpw7NuIGRpZmVyZW50ZSBkZSBsYSBVbml2ZXJzaWRhZCBDb21wbHV0ZW5zZSBkZSBNYWRyaWQsIHVzdGVkIGRlY2xhcmEgcXVlIGhhIGN1bXBsaWRvIGNvbiBsYXMgb2JsaWdhY2lvbmVzIHJlcXVlcmlkYXMgcG9yIGVzdGUgY29udHJhdG8gbyBhY3VlcmRvLgrigKIgTGEgVW5pdmVyc2lkYWQgQ29tcGx1dGVuc2UgZGUgTWFkcmlkIGlkZW50aWZpY2Fyw6EgY2xhcmFtZW50ZSBzdS9zIG5vbWJyZS9zIGNvbW8gZWwvbG9zIGF1dG9yL2VzIG8gcHJvcGlldGFyaW8vcyBkZSBsb3MgZGVyZWNob3MgZGVsIGRvY3VtZW50bywgeSBubyBoYXLDoSBuaW5ndW5hIGFsdGVyYWNpw7NuIGRlIHN1IGRvY3VtZW50byBkaWZlcmVudGUgYSBsYXMgcGVybWl0aWRhcyBlbiBlc3RhIGxpY2VuY2lhLgrigKIgVHJhYmFqb3MgZGVwb3NpdGFkb3MgcG9yIHN1IHByb3BpbyBhdXRvcjogYWwgYXV0by1hcmNoaXZhciBlc3RhIGNvbGVjY2nDs24gZGUgZmljaGVyb3MgeSBtZXRhZGF0b3MgYmlibGlvZ3LDoWZpY29zIGFzb2NpYWRvcywgb3RvcmdvIGFsIHJlcG9zaXRvcmlvIGluc3RpdHVjaW9uYWwgZGUgbGEgVW5pdmVyc2lkYWQgQ29tcGx1dGVuc2UgZGUgTWFkcmlkIGVsIGRlcmVjaG8gcGFyYSBhbG1hY2VuYXJsb3MgeSBkaXN0cmlidWlybG9zLiBEZWNsYXJvIHF1ZSBlc3RlIG1hdGVyaWFsIGVzIGRlIG1pIHByb3BpZWRhZCBpbnRlbGVjdHVhbCB5IHF1ZSBlbCByZXBvc2l0b3JpbyBpbnN0aXR1dGljaW9uYWwgZGUgbGEgVW5pdmVyc2lkYWQgQ29tcGx1dGVuc2UgZGUgTWFkcmlkLCBubyBhc3VtZSByZXNwb25zYWJpbGlkYWQgYWxndW5hIGVuIGNhc28gZGUgcXVlIHNlIHByb2R1emNhIHVuYSB2aW9sYWNpw7NuIGRlIGRlcmVjaG9zIGRlIHByb3BpZWRhZCBhbCBkaXN0cmlidWlyIGVzdG9zIGZpY2hlcm9zIG8gbWV0YWRhdG9zLgrigKIgVHJhYmFqb3MgZGVwb3NpdGFkb3MgcG9yIG90cm9zIHF1ZSBubyBzZWFuIHN1IGF1dG9yOiBkZWNsYXJvIHF1ZSBsb3MgbWV0YWRhdG9zIGJpYmxpb2dyw6FmaWNvcyBxdWUgZXN0b3kgYXJjaGl2YW5kbyBlbiBlbCByZXBvc2l0b3JpbyBpbnN0aXR1Y2lvbmFsIGRlIGxhIFVuaXZlcnNpZGFkIENvbXBsdXRlbnNlIGRlIE1hZHJpZCwgc29uIGRlIGRvbWluaW8gcMO6YmxpY28uIFNpIG5vIGZ1ZXNlIGVsIGNhc28sIGFjZXB0byBwbGVuYSByZXNwb25zYWJpbGlkYWQgcG9yIGN1YWxxdWllciBpbmZyYWNjacOzbiBkZSBkZXJlY2hvcyBkZSBhdXRvciBxdWUgY29ubGxldmUgbGEgZGlzdHJpYnVjacOzbiBkZSBlc3RvcyBmaWNoZXJvcyBvIG1ldGFkYXRvcy4K4oCiIFBvciB0YW50bywgdG9kb3MgbG9zIG1ldGFkYXRvcyBwdWJsaWNhZG9zIGVuIGVsIHJlcG9zaXRvcmlvIGluc3RpdHVjaW9uYWwgZGUgbGEgVW5pdmVyc2lkYWQgQ29tcGx1dGVuc2UgZGUgTWFkcmlkLCBlc3TDoW4gZGlzcG9uaWJsZXMgY29uIGxhIGxpY2VuY2lhIENyZWF0aXZlIENvbW1vbnMgQ0MwIDEuMCBVbml2ZXJzYWwgT2ZyZWNpbWllbnRvIGFsIERvbWluaW8gUMO6YmxpY28gKENDMCAxLjApLiBFc3RhIGxpY2VuY2lhIHBlcm1pdGUgY29waWFyLCBtb2RpZmljYXIsIGRpc3RyaWJ1aXIsIHJldXRpbGl6YXIgeSBjb21wYXJ0aXIgcMO6YmxpY2EgeSBsaWJyZW1lbnRlIGxvcyBtZXRhZGF0b3MgKGluY2x1eWVuZG8gc3UgdXNvIGNvbWVyY2lhbCksIHNpbiB0ZW5lciBxdWUgcGVkaXIgcGVybWlzby4gU2kgdGVyY2VyYXMgcGFydGVzIHVzYW4gZXN0b3MgbWV0YWRhdG9zLCBkZWJlbiBoYWNlciB1biByZWNvbm9jaW1pZW50byB5IHVuYSBhdHJpYnVjacOzbiBhIGxhcyBmdWVudGVzIGRlIGxvcyBtaXNtb3MuIExhIHJldXRpbGl6YWNpw7NuIGRlIGVzdG9zIG1ldGFkYXRvcyB0YW1iacOpbiBlcyBsaWJyZSwgdGFsIHkgY29tbyBlc3RhYmxlY2UgbGEgbGljZW5jaWEgZGUgdXNvIENDMC4K
URL
https://docta.ucm.es/bitstreams/5276ccb9-7d34-4fc6-982e-ba57b61c06c1/download
File
MD5
703b9b212ddb024108bc5f61deb57cad
1851734
application/pdf
Mixed-integer programming.pdf