15 papers · ranked by Valyu relevance
Sen Bai, Chunqi Yang, Xin Bai, Xin Zhang + 1 more
Binary (0-1) integer programming (BIP) is pivotal in scientific domains requiring discrete decisionmaking. As the advance of AI computing, recent works explore neural network-based solvers for integer linear programming (ILP) problems. Yet, they lack scalability for tackling nonlinear challenges. To handle…
Christian Blum, Haroldo Gambini Santos
Construct, Merge, Solve & Adapt (CMSA) is a general hybrid metaheuristic for solving combinatorial optimization problems. At each iteration, CMSA (1) constructs feasible solutions to the tackled problem instance in a probabilistic way and (2) solves a reduced problem instance (if possible) to optimality. The…
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…
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…
Elisabeth Gaar, Jon Lee, Ivana Ljubić, Markus Sinnl + 1 more
We study a class of integer bilevel programs with second-order cone constraints at the upper-level and a convex-quadratic objective function and linear constraints at the lower-level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a second-order-cone-based cut-generating procedure. We…
Tadashi Kadowaki, Mitsuru Ambai
In edge computing, suppressing data size is a challenge for machine learning models that perform complex tasks such as autonomous driving, in which computational resources (speed, memory size and power) are limited. Efficient lossy compression of matrix data has been introduced by decomposing it into the product of an…
Albert No
The size of the largest binary single deletion code has been unknown for more than 50 years. It is known that Varshamov-Tenengolts (VT) code is an optimum single deletion code for block length $n\leq10$; however, only a few upper bounds of the size of single deletion code are proposed for larger n. We provide improved…
Broderick Crawford, Álex Paz, Ricardo Soto, Álvaro Peña Fritz + 7 more
Metaheuristics are a fundament pillar of Industry 4.0, as they allow for complex optimization problems to be solved by finding good solutions in a reasonable amount of computational time. One category of important problems in modern industry is that of binary problems, where decision variables can take values of zero…
William Pettersson, Melih Özlen
To obtain a better understanding of the trade-offs between various objectives, Bi-Objective Integer Programming (BOIP) algorithms calculate the set of all non-dominated vectors and present these as the solution to a BOIP problem. Historically, these algorithms have been compared in terms of the number of…
Gioni Mexi, Dominik Kamp, Yuji Shinano, Shanwen Pu + 7 more
'Ksenia Bestuzheva' 'Christopher Hojny' 'Matthias Walter' 'Marc E. Pfetsch' 'Sebastian Pokutta' 'Thorsten Koch'] The Pseudo-Boolean problem deals with linear or polynomial constraints with integer coefficients over Boolean variables. The objective lies in optimizing a linear objective function, or finding a feasible…
Dante Leiva, Benjamín Ramos-Tapia, Broderick Crawford, Ricardo Soto + 2 more
'Felipe Cisternas-Caneo' 'Ameer Hamza Khan'] The set-covering problem aims to find the smallest possible set of subsets that cover all the elements of a larger set. The difficulty of solving the set-covering problem increases as the number of elements and sets grows, making it a complex problem for which traditional…
Ayşe Beşkirli, Changsheng Zhang, Haitong Zhao
In this study, the pied kingfisher optimizer (PKO) algorithm is adapted to the uncapacitated facility location problem (UFLP), and its performance is evaluated. The PKO algorithm is binarized with fourteen different transfer functions (TF), and each variant is tested on a total of fifteen different Cap problems. In…
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 +…
Broderick Crawford, Benjamín López Cortés, Felipe Cisternas-Caneo, José Manuel Gómez-Pulido + 7 more
Binarizing continuous metaheuristics to solve challenging NP-hard binary optimization problems is a fundamental step in adapting continuous algorithms for discrete domains. Binary optimization problems, such as the Set Covering Problem and the 0-1 Knapsack Problem, demand tailored approaches to efficiently explore and…
Michael Hartisch, Ulf Lorenz
The necessity to deal with uncertain data is a major challenge in decision making. Robust optimization emerged as one of the predominant paradigms to produce solutions that hedge against uncertainty. In order to obtain an even more realistic description of the underlying problem where the decision maker can react to…