14 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…
Hitarth, S, Mansutti, Alessio + 2 more
This paper presents the first study of the complexity of the optimization problem for integer linear-exponential programs which extend classical integer linear programs with the exponential function x 7→ 2 x and the remainder function (x, y) 7→ (x mod 2 y ). The problem of deciding if such a program has a solution was…
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…
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…
Li, Shuai, Zhou, Shenglong
Unconstrained binary integer programming (UBIP) poses significant computational challenges due to its discrete nature. We introduce a novel reformulation approach using a piecewise cubic function that transforms binary constraints into continuous equality constraints. Instead of solving the resulting constrained…
Kyuil Sim, Sanghyeok Choi, Jinkyoo Park
Integer Linear Programming (ILP) serves as a versatile framework for modeling a wide range of combinatorial optimization problems, typically addressed by sophisticated exact solvers or heuristics. While learning-based approaches have recently shown their effectiveness, they suffer from poor generalization to…
Daniel T. Larsson, Dipankar Maity, Panagiotis Tsiotras
In this paper, we consider establishing a formal connection between two distinct tree-abstraction problems inspired by the information-bottleneck (IB) method. Specifically, we consider the hard- and soft-constrained formulations that have recently appeared in the literature to determine the conditions for which the two…
Christopher Hojny, Mathieu Besançon, Ksenia Bestuzheva, Sander Borst + 30 more
``` Christopher Hojny · Mathieu Besan¸con · Ksenia Bestuzheva Sander Borst · Antonia Chmiela , Jo˜ao Dion´ısio · Johannes Ehls Leon Eifler · Mohammed Ghannam · Ambros Gleixner Adrian G¨oß · Alexander Hoen · Jacob von Holly-Ponientzietz Rolf van der Hulst · Dominik Kamp · Thorsten Koch Kevin Kofler · Jurgen Lentz ·…
Del Pia, Alberto
We introduce the notion of projection-width for systems of separable constraints, defined via branch decompositions of variables and constraints. We show that several fundamental discrete optimization and counting problems can be solved in polynomial time when the projection-width is polynomially bounded. These include…
Wei-Kun Chen, Chang-Long Li, Zhao-Wei Wang, Yu-Hong Dai + 2 more
Presolve for mixed integer programming (MIP) problems aims to eliminate redundant information, strengthen the formulation, and extract useful structural information for the subsequent branch-and-cut process. An important type of such structural information is the variable implications (VIs), which describe how a bound…
Tung Quoc Le, Anh Tuan Nguyen, Viet Anh Nguyen
Lagrangian Relaxation (LR) is a powerful technique for solving large-scale Mixed Integer Linear Programming (MILP), particularly those with decomposable structures, such as vehicle routing or unit commitment problems. By relaxing the coupling constraints, LR enables parallel subproblem solving and often yields tighter…
Yongzheng Dai, Chen Chen
We develop a novel primal heuristic for nonconvex Mixed-Integer Quadratically Constrained Quadratic Programs (MIQCQPs). The method is built around a convex approximation that is dynamically adjusted within a feasibility-pump-style alternating heuristic. Approximations are adjusted based on the structure of the MIQCQP…
Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Pouya Sampourmahani, Jun-Kai You + 1 more
—The emergence of huge-scale, data-intensive linear optimization (LO) problems in applications such as machine learning has driven the need for more computationally efficient interior point methods (IPMs). While conventional IPMs are polynomial-time algorithms with rapid convergence, their periteration cost can be…
Yang, Yaguang
This paper presents a Matlab implementation of an arc-search infeasible interior point algorithm for linear programming (LP), which has a proven polynomial bound of $\mathcal{O}(\sqrt{n}L)$, the best among all interior-point algorithms for LP. Software architecture and major functions are discussed. Its ease of use is…