13 papers · ranked by Valyu relevance
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…
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…
Marcin Briański, Martin Koutecký, Daniel Král’, Kristýna Pekárková + 1 more
An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal…
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…
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…
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…
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…
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…
Hendrik Schawe, Roman Bleim, Alexander K. Hartmann, Andrea Gambassi
Here we study linear programming applied to the random K-SAT problem, a fundamental problem in computational complexity. The K-SAT problem is to decide whether a Boolean formula with N variables and structured as a conjunction of M clauses, each being a disjunction of K variables or their negations is satisfiable or…
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…
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…