Innovating Works

QIP

Financiado
Towards a Quantitative Theory of Integer Programming
Integer programming (IP), i.e. linear optimization with integrality constraints on variables, is one of the most successful methods for solving large scale optimization problems in practice. While many of the base IP problems suc... Integer programming (IP), i.e. linear optimization with integrality constraints on variables, is one of the most successful methods for solving large scale optimization problems in practice. While many of the base IP problems such as the traveling salesman problem (TSP) or satisfiability (SAT) are NP-Complete, IPs with tens of thousands of variables are routinely solved in just a few hours by current state of the art IP solvers. The main goal of this proposal is to develop a quantitative theory capable of explaining when and how well different IP solver techniques will work on a wide range of instances. Here we will study many of the principal tools used to solve IPs including branch & bound, the simplex method, cutting planes and rounding heuristics. Our first direction of study will be to develop parametrized classes of instances, inspired by the structure of realistic models, on which branch & bound and the simplex method are provably efficient. The second research direction will be to develop alternatives to ad hoc rounding heuristics and cutting plane selection strategies with provable guarantees and provide their applications to important classes of IPs. Lastly, we will explore the power and limitations of IP techniques in the context of algorithm design by comparing them to powerful techniques in theoretical computer science and analyzing their worst-case performance for solving general integer programs. While the main thrust of this proposal is theoretical, it will be complimented by an experimental component performed in collaboration with well-known experts in computational IP, both to gain valuable insights on the structure of real-world instances and to validate the effectiveness newly suggested approaches. The proposed research is designed to make breakthroughs in our quantitative understanding of IP techniques, many of which have long resisted theoretical analysis. ver más
31/12/2024
2M€
Duración del proyecto: 75 meses Fecha Inicio: 2018-09-10
Fecha Fin: 2024-12-31

Línea de financiación: concedida

El organismo H2020 notifico la concesión del proyecto el día 2018-09-10
Línea de financiación objetivo El proyecto se financió a través de la siguiente ayuda:
ERC-2018-STG: ERC Starting Grant
Cerrada hace 7 años
Presupuesto El presupuesto total del proyecto asciende a 2M€
Líder del proyecto
STICHTING NEDERLANDSE WETENSCHAPPELIJK ONDERZ... No se ha especificado una descripción o un objeto social para esta compañía.
Perfil tecnológico TRL 4-5