4 documentos corresponden a la consulta.
Palabras contadas: zabala: 4, p: 248
Méndez-Díaz, I. - Zabala, P.
Discrete Appl Math 2008;156(2):159-179
2008
Temas: Cutting plane algorithms - Facets of polyhedra - Graph coloring - Integer programming - Computer programming - Graph theory - Integer programming - Problem solving - Cutting plane algorithms - Facets of polyhedra
Descripción: We present an approach based on integer programming formulations of the graph coloring problem. Our goal is to develop models that remove some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the 0/1-polytope associated with one of these integer programming formulations. The theoretical results described here are used to design an efficient Cutting Plane algorithm. © 2007 Elsevier B.V. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Méndez-Díaz, I. - Zabala, P.
Discrete Appl Math 2006;154(5 SPEC ISS):826-847
2006
Temas: Branch-and-Cut algorithms - Graph coloring - Integer programming - Graph theory - Integer programming - Mathematical models - Branch-and-cut algorithms - Graph coloring - Algorithms
Descripción: Fil:Méndez-Díaz, I. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Méndez-Díaz, I. - Zabala, P.
Discrete Appl Math 2010;158(4):349-354
2010
Temas: Branch-and-Cut - Graph multicoloring - Integer programming - Branch-and-cut - Branch-and-cut algorithms - Graph multicoloring - Integer programming formulations - Multicoloring - Polytopes - Random instance
Descripción: This paper presents a new generalization of the graph multicoloring problem. We propose a Branch-and-Cut algorithm based on a new integer programming formulation. The cuts used are valid inequalities that we could identify to the polytope associated with the model. The Branch-and-Cut system includes separation heuristics for the valid inequalities, specific initial and primal heuristics, branching and pruning rules. We report on computational experience with random instances. © 2009 Elsevier B.V. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Méndez-Díaz, I. - Zabala, P. - Lucena, A.
Discrete Appl Math 2008;156(17):3223-3237
2008
Temas: Branch-and-cut algorithms - Integer programming - Traveling deliveryman problem - Dynamic programming - Hamiltonians - Integer programming - Linearization - Meats - Particle size analysis - Branch-and-Bound
Descripción: The Traveling Deliveryman Problem is a generalization of the Minimum Cost Hamiltonian Path Problem where the starting vertex of the path, i.e. a depot vertex, is fixed in advance and the cost associated with a Hamiltonian path equals the sum of the costs for the layers of paths (along the Hamiltonian path) going from the depot vertex to each of the remaining vertices. In this paper, we propose a new Integer Programming formulation for the problem and computationally evaluate the strength of its Linear Programming relaxation. Computational results are also presented for a cutting plane algorithm that uses a number of valid inequalities associated with the proposed formulation. Some of these inequalities are shown to be facet defining for the convex hull of feasible solutions to that formulation. These inequalities proved very effective when used to reinforce Linear Programming relaxation bounds, at the nodes of a Branch and Bound enumeration tree. © 2008 Elsevier B.V. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo