11 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…
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…
Daniel Dadush, Friedrich Eisenbrand, Thomas Rothvoss
Approximate integer programming is the following: For a given convex body $K \subseteq{\mathbb{R}}^n$, either determine whether $K \cap{\mathbb{Z}}^n$ is empty, or find an integer point in the convex body $2\cdot K - c +c$ which is K, scaled by 2 from its center of gravity c. Approximate integer programming can be…
Zhi-Cheng Wang, Xiao-Bei Wu
Biogeography-based optimization (BBO) is a relatively new bioinspired heuristic for global optimization based on the mathematical models of biogeography. By investigating the applicability and performance of BBO for integer programming, we find that the original BBO algorithm does not perform well on a set of benchmark…
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…
Ahmed F. Ali, Mohamed A. Tawhid
Cuckoo search algorithm is a promising metaheuristic population based method. It has been applied to solve many real life problems. In this paper, we propose a new cuckoo search algorithm by combining the cuckoo search algorithm with the Nelder-Mead method in order to solve the integer and minimax optimization…
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…
Ritchie Lee, Susmit Jha, Anastasia Mavridou, Dimitra Giannakopoulou + 4 more
'Ralph Bottesch' 'Max W. Haslbeck' 'Alban Reynaud' 'René Thiemann'] We implement a decision procedure for linear mixed integer arithmetic and formally verify its soundness in Isabelle/HOL. We further integrate this procedure into one application, namely into CeTA, a formally verified certifier to check untrusted…
Daniel Molina-Pérez, Edgar Alfredo Portilla-Flores, Efrén Mezura-Montes, Eduardo Vega-Alvarado + 2 more
'Efrén Mezura-Montes' 'Eduardo Vega-Alvarado' 'María Bárbara Calva-Yañez' 'Thomas Stützle'] Mixed integer nonlinear programming (MINLP) addresses optimization problems that involve continuous and discrete/integer decision variables, as well as nonlinear functions. These problems often exhibit multiple discontinuous…