Show simple item record

Authordc.contributor.authorEspinoza González, Daniel 
Authordc.contributor.authorGoycoolea, Marcos 
Authordc.contributor.authorMoreno, Eduardo 
Admission datedc.date.accessioned2015-12-14T15:24:01Z
Available datedc.date.available2015-12-14T15:24:01Z
Publication datedc.date.issued2015
Cita de ítemdc.identifier.citationDiscrete Applied Mathematics Volumen: 194 Páginas: 65-80 oct 2015en_US
Identifierdc.identifier.otherDOI: 10.1016/j.dam.2015.05.020
Identifierdc.identifier.urihttps://repositorio.uchile.cl/handle/2250/135687
General notedc.descriptionArtículo de publicación ISIen_US
Abstractdc.description.abstractWe consider the problem of separating maximally violated inequalities for the precedence constrained knapsack problem. Though we consider maximally violated constraints in a very general way, special emphasis is placed on induced cover inequalities and induced clique inequalities. Our contributions include a new partial characterization of maximally violated inequalities, a new safe shrinking technique, and new insights on strengthening and lifting. This work follows on the work of Boyd (1993), Park and Park (1997), van de Leensel et al. (1999) and Boland et al. (2011). Computational experiments show that our new techniques and insights can be used to significantly improve the performance of cutting plane algorithms for this problem.en_US
Patrocinadordc.description.sponsorshipFONDECYT grants 1110024 1110674 ANILLO grant ACT-88 Basal project CMM (Universidad de Chile) ICM grant P10-024-Fen_US
Lenguagedc.language.isoenen_US
Publisherdc.publisherElsevieren_US
Type of licensedc.rightsAtribución-NoComercial-SinDerivadas 3.0 Chile*
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/*
Keywordsdc.subjectLiftingen_US
Keywordsdc.subjectShrinkingen_US
Keywordsdc.subjectPrecedence-constrained knapsack problemen_US
Keywordsdc.subjectInduced cover inequalityen_US
Keywordsdc.subjectInduced clique inequalityen_US
Keywordsdc.subjectSeparation problemen_US
Títulodc.titleThe precedence constrained knapsack problem: Separating maximally violated inequalitiesen_US
Document typedc.typeArtículo de revista


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record

Atribución-NoComercial-SinDerivadas 3.0 Chile
Except where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 Chile