Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Branch and cut is today's state-of-the-art method to solve 0/1-integer linear programs. Important for the success of this method is the generation of strong valid inequalities, which tighten the linear programming relaxation of 0/1-IPs and thus allow for early pruning of parts of the search tree. In this paper we present a novel approach to generate valid inequalities for 0/1-IPs which is based on binary decision diagrams (BDDs). BDDs are a data-structure which represents 0/1-vectors as paths of a certain acyclic graph. They have been successfully applied in computational logic, hardware verification and synthesis. We implemented our BDD cutting plane generator in a branch-and-cut framework and tested it on several instances of the MAX-ONES problem and randomly generated 0/1-IPs. Our computational results show that we have developed competitive code for these problems, on which state-of-the-art MIP-solvers fall short
Volkan Cevher, Grigorios Chrysos, Efstratios Panteleimon Skoulakis
Michel Bierlaire, Claudia Bongiovanni
Michel Bierlaire, Claudia Bongiovanni