15 papers · ranked by Valyu relevance
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…
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…
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…
Rémy Defossez, Christoph Haase, Alessio Mansutti, Guillermo A. Pérez
We study the non-linear extension of integer programming with greatest common divisor constraints of the form gcd(f, g) ∼ d, where f and g are linear polynomials, d is a positive integer, and ∼ is a relation among ≤, =, 6= and ≥. We show that the feasibility problem for these systems is in NP, and that an optimal…
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…
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…
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…
Xiang He, Peng Lin, Shaowei Cai
Integer Quadratic Programming (IQP) is an important problem in operations research. Local search is a powerful method for solving hard problems, but the research on local search algorithms for IQP solving is still on its early stage. This paper develops an efficient local search solver for solving general IQP, called…
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…
Akif Çördük, Piotr Sielski, Boucher, Alice + 1 more
We introduce a fusion of GPU accelerated primal heuristics for Mixed Integer Programming. Leveraging GPU acceleration enables exploration of larger search regions and faster iterations. A GPU-accelerated PDLP serves as an approximate LP solver, while a new probing cache facilitates rapid roundings and early…
Behrooz Bodaghi, Nadezda Sukhorukova
In this paper we propose a new efficient linear programming based approach for multi-resource allocation and location problems in disaster management. Such problems require an integer solution and therefore, in most cases, the computations rely on integer and mixed-integer linear programming solvers. In general, these…
Vicky Mak‐Hau, John Yearwood, William Moran
In this paper, we investigate the constraint typology of mixed-integer linear programming (MILP) formulations. MILP is a commonly used mathematical programming technique for modelling and solving real-life scheduling, routing, planning, resource allocation, timetabling optimization problems, providing optimized…
César Massri, Manuel Dubinsky
An important aspect within the study of algebraic varieties over characteristic p is to know the number of points that a variety has. This led to the statement of Weil's conjectures proved by Deligne thanks to the analysis made by Grothendieck and others. In this article we are interested in computing, not only the…