25 papers · ranked by Valyu relevance
João Pedro Pedroso
In this paper we introduce an evolutionary algorithm for the solution of linear integer programs. The strategy is based on the separation of the variables into the integer subset and the continuous subset; the integer variables are fixed by the evolutionary system, and the continuous ones are determined in function of…
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…
Friedrich Eisenbrand, Robert Weismantel
We consider integer programming problems in standard form max{c T x : Ax = b, x > 0, x ∈ Z n } where A ∈ Z m×n , b ∈ Z m and c ∈ Z n . We show that such an integer program can be solved in time (m ·∆) O(m) · kbk 2 ∞, where ∆ is an upper bound on each absolute value of an entry in A. This improves upon the longstanding…
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…
D. V. Gribanov
In this paper, we present FPT-algorithms for special cases of the shortest vector problem (SVP) and the integer linear programming problem (ILP), when matrices included to the problems' formulations are near square. The main parameter is the maximal absolute value of rank minors of matrices included to the problem…
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…
Richard Schuster, Jeffrey O. Hanson, Matt Strimas-Mackey, Joseph R. Bennett
The resources available for conserving biodiversity are limited, and so protected areas need to be established in places that will achieve objectives for minimal cost. Two of the main algorithms for solving systematic conservation planning problems are Simulated Annealing (SA) and Integer linear programming (ILP).…
Mengzhen Guo, Stefan Grünewald
We present Lpnet, a variant of the widely used Neighbor-net method that approximates pairwise distances between taxa by a circular phylogenetic network. We first apply standard methods to construct a binary phylogenetic tree and then use integer linear programming to compute an optimal circular orderings that agrees…
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…
Fernando H. C. Dias, Alexandru I. Tomescu
Minimum flow decomposition (MFD) is a common problem across various fields of Computer Science, where a flow is decomposed into a minimum set of weighted paths. However, in Bioinformatics applications, such as RNA transcript or quasi-species assembly, the flow is erroneous, since is obtained from noisy read coverages.…
Conor F. Hayes, Steven A. Magana-Zook, Andre Gonçalves, Ahmet Can Solak + 2 more
We propose a novel approach for antibody library design that combines deep learning and multi-objective linear programming with diversity constraints. Our method leverages recent advances in sequence and structure-based deep learning for protein engineering to predict the effects of mutations on antibody properties.…
Ahmad Abdi, Gérard Cornuéjols, Bertrand Guenin, Levent Tunçel
A rational number is dyadic if it has a finite binary representation $p/2^k$, where p is an integer and k is a nonnegative integer. Dyadic rationals are important for numerical computations because they have an exact representation in floating-point arithmetic on a computer. A vector is dyadic if all its entries are…
Mikhail A. Bragin, Emily L. Tucker
Mixed-Integer Linear Programming (MILP) plays an important role across a range of scientific disciplines and within areas of strategic importance to society. The MILP problems, however, suffer from combinatorial complexity. Because of integer decision variables, as the problem size increases, the number of possible…
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…
Authors not listed
We present a vector-based method to balance chemical reactions. The algorithm builds candidates in a deterministic way, removes duplicates, and always prints coefficients in the lowest whole-number form. For redox cases, electrons and protons/hydroxide are treated explicitly, so both mass and charge are balanced. We…
Henri Schmidt, Benjamin J. Raphael
Reconstructing unobserved ancestral states of a phylogenetic tree provides insight into the history of evolving systems and is one of the fundamental problems in phylogenetics. For a fixed phylogenetic tree, the most parsimonious ancestral reconstruction – a solution to the small parsimony problem – can be efficiently…
Authors not listed
Automated chemistry platforms hold the potential to enable large-scale organic synthesis campaigns, such as producing a library of compounds for biological evaluation. The efficiency of such platforms will depend on the schedule according to which the synthesis operations are executed. In this work, we study the…
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…
Authors not listed
Experimental design plays an important role in efficiently acquiring informative data for system characterization and deriving robust conclusions under resource limitations. Recent advancements in high-throughput experimentation coupled with machine learning have notably improved experimental procedures. While Bayesian…
Zixiang Xu
Gene knockout has been used to improve the conversion ratio of strains for some chemical products. Based on mixed integer bi-level linear programming (MIBLP) and cell network models, there have been several algorithms to predict the target for deletion to improve the productivity of chemicals. At present, the cell…
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…
Aihong Ren, Yuping Wang, Xingsi Xue
This paper proposes a new methodology for solving the interval bilevel linear programming problem in which all coefficients of both objective functions and constraints are considered as interval numbers. In order to keep as much uncertainty of the original constraint region as possible, the original problem is first…
Charalampos P. Triantafyllidis, Nikolaos Samaras, Sándor Szénási
This paper presents a new simplex-type algorithm for Linear Programming with the following two main characteristics: (i) the algorithm computes basic solutions which are neither primal or dual feasible, nor monotonically improving and (ii) the sequence of these basic solutions is connected with a sequence of…
Syed Inayatullah, Nasir Touheed, Muhammad Imtiaz, Cheng-Yi Xia
This paper proposes a streamlined form of simplex method which provides some great benefits over traditional simplex method. For instance, it does not need any kind of artificial variables or artificial constraints; it could start with any feasible or infeasible basis of an LP. This method follows the same pivoting…
Liwei Cao, Danilo Russo, Vassilios S. Vassiliadis, Alexei Lapkin
A mixed-integer nonlinear programming (MINLP) formulation for symbolic regression was proposed to identify physical models from noisy experimental data. The formulation was tested using numerical models and was found to be more efficient than the previous literature example with respect to the number of predictor…