17 papers · ranked by Valyu relevance
Federico Rodes, Isabel Méndez‐Díaz, Paula Zabala
We propose a new exact approach for solving integer linear programming (ILP) problems which we will call projective splitting algorithms (PSAs). Unlike classical methods for solving ILP problems, PSAs conduct the search for the optimal solution by generating candidate solutions tailored to specific values of the…
Qi He, Jon Lee
We present pure-integer Gomory cuts in a way so that they are derived with respect to a "dual form" pure-integer optimization problem and applied on the standard-form primal side as columns, using the primal simplex algorithm. The input integer problem is not in standard form, and so the cuts are derived a bit…
Babak Moazzez, Kevin K. H. Cheung
In 1977, Burdet and Johnson [2] proposed an algorithms to solve integer programs. The algorithm uses idea of lifting a subadditive dual feasible function. This function is lifted until at least one duality or subadditivity constraint gets violated. At this time, the function gets fixed for those points and lifting…
Briański, Marcin, Lassota, Alexandra + 6 more
Solving integer programs of the form min x A x = b , l ⩽ x ⩽ u , x ∈ Z n is, in general, NP-hard. Hence, great effort has been put into identifying subclasses of integer programs that are solvable in polynomial or FPT time. A common scheme for many of these integer programs is a star-like structure of the constraint…
Timo Berthold, Peter J. Stuckey, Jakob Witzig
Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is applied at the root to…
Robert Nieuwenhuis, Albert Oliveras, Enric Rodríguez-Carbonell
State-of-the-art SAT solvers are nowadays able to handle huge real-world instances. The key to this success is the so-called Conflict-Driven Clause-Learning (CDCL) scheme, which encompasses a number of techniques that exploit the conflicts that are encountered during the search for a solution. In this article we extend…
Weili Zhang, Charles Nicholson
The objective scaling ensemble approach is a novel two-phase heuristic for integer linear programming problems shown to be effective on a wide variety of integer linear programming problems. The technique identifies and aggregates multiple partial solutions to modify the problem formulation and significantly reduce the…
Fabio L. Traversa, Massimiliano Di Ventra
Integer linear programming (ILP) encompasses a very important class of optimization problems that are of great interest to both academia and industry. Several algorithms are available that attempt to explore the solution space of this class efficiently, while requiring a reasonable compute time. However, although these…
David E. Bernal, Sridhar Tayur, Davide Venturelli
This lecture series on Quantum Integer Programming (QuIP) – created by Professor Sridhar Tayur, David E. Bernal and Dr. Davide Venturelli, a collaboration between CMU and USRA, with the support from Amazon Braket during Fall 2020 – is intended for students and researchers interested in Integer Programming and the…
Tomáš Gavenčiak, Dušan Knop, Martin Koutecký
Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity…
Pravesh Koirala, Mel Krusniak, Forrest Laine
Integer programming games (IPGs) are -person games with integer strategy spaces. These games are used to model non-cooperative combinatorial decision-making and are used in domains such as cybersecurity and transportation. The prevalent solution concept for IPGs, Nash equilibrium, is difficult to compute and even…
Cheng Guo, Merve Bodur, Joshua A. Taylor
Optimization problems with discrete decisions are nonconvex and thus lack strong duality, which limits the usefulness of tools such as shadow prices and the KKT conditions. It was shown in Burer (2009) that mixedbinary quadratic programs can be written as completely positive programs, which are convex. Completely…
Gabriele Dragotto, Rosario Scatamacchia
Designing efficient algorithms to compute Nash equilibria poses considerable challenges in Algorithmic Game Theory and Optimization. In this work, we employ integer programming techniques to compute Nash equilibria in Integer Programming Games, a class of simultaneous and non-cooperative games where each player solves…
Daniel Lokshtanov
In the Integer Quadratic Programming problem input is an n × n integer matrix Q, an m × n integer matrix A and an m-dimensional integer vector b. The task is to find a vector x ∈ Z n minimizing x TQx, subject to Ax ≤ b. We give a fixed parameter tractable algorithm for Integer Quadratic Programming parameterized by n +…
Ning Ruan, David Yang Gao
This paper presents a canonical dual method for solving a quadratic discrete value selection problem subjected to inequality constraints. The problem is first transformed into a problem with quadratic objective and 0-1 integer variables. The dual problem of the 0-1 programming problem is thus constructed by using the…
Jamie Fravel, Robert Hildebrand
An integer program is called ideal if its continuous relaxation coincides with its convex hull allowing the problem to be solved as a continuous program and offering substantial computational advantages. Proving idealness analytically can be extraordinarily tedious—even for small formulations—such proofs often span…
Saravanan Venkatachalam, Lewis Ntaimo
Two-stage stochastic mixed-integer programming (SMIP) problems with general integer variables in the second-stage are generally difficult to solve. This paper develops the theory of integer set reduction for characterizing the subset of the convex hull of feasible integer points of the second-stage subproblem which can…