Approximating the balanced minimum evolution problem

We prove a strong inapproximability result for the Balanced Minimum Evolution Problem. Our proof also implies that the problem remains NP-hard even when restricted to metric instances. Furthermore, we give a MST-based 2-approximation algorithm for the problem for such instances.     

The balanced minimum evolution problem under uncertain data

We investigate the Robust Deviation Balanced Minimum Evolution Problem (RDBMEP), a combinatorial optimization problem that arises in computational biology when the evolutionary distances from taxa are uncertain and varying inside intervals. By exploiting some fundamental properties of the objective function, we present a mixed integer programming model to exactly solve instances of the RDBMEP and discuss the biological impact of uncertainty on the solutions to the problem. Our results give perspective on the mathematics of the RDBMEP and suggest new directions to tackle phylogeny estimation problems affected by uncertainty.     

On the vertex packing problem

A forbidden subgraphs characterization of the class of graphs that arise from bipartite graphs, odd holes, and graphs with no complement of a diamond via repeated substitutions is given. This characterization allows us to solve the vertex packing problem for the graphs in this class.     

Solving the problem of packing equal and unequal circles in a circular container

In this paper we propose a Monotonic Basin Hopping approach and its population-based variant Population Basin Hopping to solve the problem of packing equal and unequal circles within a circular container with minimum radius. Extensive computational experiments have been performed both to analyze the problem at hand, and to choose in an appropriate way the parameter values for the proposed methods. Different improvements with respect to the best results reported in the literature have been detected.     

Sufficient conditions for a global minimum in a nonlinear programming problem

Translated from Issledovaniya po Prikladnoi Matematike, No. 1, pp. 103–108, 1973.     

An information theory perspective on the balanced minimum evolution problem

We show that the Balanced Minimum Evolution Problem (BMEP) is a cross-entropy minimization problem. This new perspective both extends the previous interpretations of the BMEP length function described in the literature and enables the identification of an efficiently computable family of lower bounds on the value of the optimal solution to the problem.     

A dynamic adaptive local search algorithm for the circular packing problem

This paper studies the circular packing problem (CPP) which consists of packing n non-identical circles C_i of known radius r_i, i ∈ N = {1, … , n}, into the smallest containing circle C. The objective is to determine the coordinates (x_i, y_i) of the center of C_i, i ∈ N, as well as the radius r and center (x, y) of C. This problem, which is a variant of the two-dimensional open dimension problem, is solved using a two-step, dynamic, adaptive, local search algorithm. At each iteration, the algorithm identifies the set of potential “best local positions” of a circle C_i, i ∈ N, given the positions of the previously packed circles, and determines for each of these positions the coordinates and radius of the smallest containing circle. The “best local position” minimizes the radius of the current containing circle. That is, every time an additional circle is packed, both the center and the radius of the containing circle are dynamically updated, and the smallest containing circle is known. The experimental results reflect the good performance of the algorithm.     

On a dual version of the one-dimensional bin packing problem

The NP-hard problem of packing items from a given set into bins so as to maximize the number of bins used, subject to the constraint that each bin be filled to at least a given threshold, is considered. Approximation algorithms are presented that provide guarantees of , , and the optimal number, at running time costs of O(n), O(nlogn), and O(nlog²n), respectively, and the average case behavior of these algorithms is explored via empirical tests on randomly generated sets of items.     

On the value of a random minimum spanning tree problem

Suppose we are given a complete graph on n vertices in which the lenghts of the edges are independent identically distributed non-negative random variables. Suppose that their common distribution function F is differentiable at zero and D = F′ (0) > 0 and each edge length has a finite mean and variance. Let L_n be the random variable whose value is the length of the minimum spanning tree in such a graph. Then we will prove the following: lim_{n → ∞}E(L_n) = ζ(3)/D where ζ(3) = Σ_{k = 1}^∞ 1/k³ = 1.202… and for any ε > 0 lim_{n → ∞} Pr(|L_n^?ζ(3)/D|) > ε) = 0.     

Increasing the attraction area of the global minimum in the binary optimization problem

The problem of binary minimization of a quadratic functional in the configuration space is discussed. In order to increase the efficiency of the random-search algorithm it is proposed to change the energy functional by raising to a power the matrix it is based on. We demonstrate that this brings about changes of the energy surface: deep minima displace slightly in the space and become still deeper and their attraction areas grow significantly. Experiments show that this approach results in a considerable displacement of the spectrum of the sought-for minima to the area of greater depth, and the probability of finding the global minimum increases abruptly (by a factor of 10³ in the case of the 10 × 10 Edwards–Anderson spin glass).     

On the integer-valued variables in the linear vertex packing problem

Given a graph with weights on vertices, the vertex packing problem consists of finding a vertex packing (i.e. a set of vertices, no two of them being adjacent) of maximum weight. A linear relaxation of one binary programming formulation of this problem has these two well-known properties: (i) every basic solution is (0, 1/2, 1)-valued, (ii) in an optimum linear solution, an integer-valued variable keeps the same value in an optimum binary solution.As an answer to an open problem from Nemhauser and Trotter, it is shown that there is a unique maximal set of variables which are integral in optimal (VLP) solutions.This research was supported by National Research Council of Canada GRANT A8528 and RD 804.     

A branch-and-price algorithm for the variable size bin packing problem with minimum filling constraint

In this paper we consider a variation of the bin packing problem in which bins of different types have different costs and capacities. Furthermore, each bin has to be filled at least to a certain level, which depends on its type. We present a set partitioning formulation and an exact optimization algorithm which exploits column generation and specialized heuristics. We compare our algorithm with the general purpose solver ILOG CPLEX, running on two compact ILP formulations and we report on experimental results on instances we have generated from data-sets for the variable size bin packing problem.     

On a packing problem for infinite graphs and independence spaces

In this paper several infinite extensions of the well-known results for packing bases in finite matroids are considered. A counterexample is given to a conjecture of Nash-Williams on edge-disjoint spanning trees of countable graphs, and a sufficient condition is proved for the packing problem in independence spaces over a countably infinite set.     

On a binary distance model for the minimum linear arrangement problem

The minimum linear arrangement problem consists of finding an embedding of the nodes of a graph on the line such that the sum of the resulting edge lengths is minimized. The problem is among the classical NP-hard optimization problems and there has been extensive research on exact and approximative algorithms. In this paper, we introduce a new model based on binary variables d _ijk that are equal to 1 if nodes i and j have distance k in the ordering. We analyze this model and point to connections and differences to a model using integer distance variables. Based on computational experiments, we argue that our model is worth further theoretical and practical investigation and that is has potentials yet to be examined.     

On the prize-collecting generalized minimum spanning tree problem

The prize-collecting generalized minimum spanning tree problem (PC-GMSTP), is a generalization of the generalized minimum spanning tree problem (GMSTP) and belongs to the hard core of -hard problems. We describe an exact exponential time algorithm for the problem, as well we present several mixed integer and integer programming formulations of the PC-GMSTP. Moreover, we establish relationships between the polytopes corresponding to their linear relaxations and present an efficient solution procedure that finds the optimal solution of the PC-GMSTP for graphs with up 240 nodes.