Combining logic and optimization in cutting plane theory

Alexander Bockmayr 1 Friedrich Eisenbrand
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Cutting planes were introduced in 1958 by Gomory in order to solve integer linear optimization problems. Since then, they have received a lot of interest, not only in mathematical optimization, but also in logic and complexity theory. In this paper, we present some recent results on cutting planes at the interface of logic and optimization. Main emphasis is on the length and the rank of cutting plane proofs based on the Gomory-Chvátal rounding principle.
Type de document :
Communication dans un congrès
H. Kirchner, Chr. Ringeissen. International Workshop on Frontiers of Combining Systems - FroCoS'2000, 2000, Nancy, France, Springer, 1794, pp.1-17, 2000, Lecture notes in Artificial Intelligence
Liste complète des métadonnées

https://hal.inria.fr/inria-00099172
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:51:30
Dernière modification le : jeudi 11 janvier 2018 - 06:19:58

Identifiants

  • HAL Id : inria-00099172, version 1

Collections

Citation

Alexander Bockmayr, Friedrich Eisenbrand. Combining logic and optimization in cutting plane theory. H. Kirchner, Chr. Ringeissen. International Workshop on Frontiers of Combining Systems - FroCoS'2000, 2000, Nancy, France, Springer, 1794, pp.1-17, 2000, Lecture notes in Artificial Intelligence. 〈inria-00099172〉

Partager

Métriques

Consultations de la notice

157