Analysis of a generalized Linear Ordering Problem via integer programming | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación | |
| dc.conicet.organizacion | Universidad Torcuato Di Tella | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación | |
| dc.contributor.author | Méndez Díaz, Isabel | |
| dc.contributor.author | Vulcano, Gustavo | |
| dc.contributor.author | Zabala, Paula Lorena | |
| dc.date.issued | 2019-12 | |
| dc.description.abstract | We study a generalized version of the linear ordering problem: Given a collection of partial orders represented by directed trees with unique root and height one, where each tree is associated with a nonnegative reward, the goal is to build a linear order of maximum reward, where the total reward is defined as the sum of the rewards of the trees compatible with the linear order. Each tree has a single root, and includes a distinguished element either as the root or as a leaf. There is a constraint about the position that the distinguished element has to occupy in the final order. The problem is NP-Hard, and has applications in diverse areas such as machine learning, discrete choice theory, and scheduling. Our contribution is two-fold. On the theoretical side, we formulate an integer programming model, establish the dimension of the convex hull of all integer feasible solutions, and infer several families of valid inequalities, including facet defining ones. On the computational side, we develop a branch-and-cut (B&C) algorithm that is competitive with state-of-the-art, generic B&C methods with respect to running time and quality of the solutions obtained. Through an extensive set of numerical studies, we characterize conditions of the model that result in a significant dominance of our B&C proposal. | es |
| dc.description.fil | Fil: Méndez Díaz, Isabel. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina | |
| dc.description.fil | Fil: Vulcano, Gustavo. Universidad Torcuato Di Tella; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Zabala, Paula Lorena. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Méndez Díaz, Isabel; Vulcano, Gustavo; Zabala, Paula Lorena; Analysis of a generalized Linear Ordering Problem via integer programming; Elsevier Science; Discrete Applied Mathematics; 271; 12-2019; 93-107 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/121144 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 93-107 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 271 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2019.08.010 | |
| dc.rights | info:eu-repo/semantics/restrictedAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | BRANCH AND CUT | es |
| dc.subject | INTEGER PROGRAMMING | es |
| dc.subject | LINEAR ORDERING | es |
| dc.subject | VALID INEQUALITIES | es |
| dc.subject.classification | Otras Ciencias de la Computación e Información | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Analysis of a generalized Linear Ordering Problem via integer programming | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.0d5b955f-734f-4a6f-8bf2-0c771655de73_A.pdf
- Tamaño:
- 387.47 KB
- Formato:
- Adobe Portable Document Format