A Bicriterion Steiner Tree Problem on Graph
A branch&bound algorithm for solving one-dimensional cutting stock problems exactly
Many numerical computations reported in the literature show only a small difference between the optimal value of the one-dimensional cutting stock problem (1CSP) and that of the corresponding linear programming relaxation. Moreover, theoretical investigations have proven that this difference is smaller than 2 for a wide range of subproblems of the general 1CSP.
A class of combinatorial problems with polynomially solvable large scale set covering/partitioning relaxations
A derivation of Lovász’ theta via augmented Lagrange duality
A recently introduced dualization technique for binary linear programs with equality constraints, essentially due to Poljak et al. [13], and further developed in Lemaréchal and Oustry [9], leads to simple alternative derivations of well-known, important relaxations to two well-known problems of discrete optimization: the maximum stable set problem and the maximum vertex cover problem. The resulting relaxation is easily transformed to the well-known Lovász number.
A Derivation of Lovász' Theta via Augmented Lagrange Duality
A recently introduced dualization technique for binary linear programs with equality constraints, essentially due to Poljak et al. [13], and further developed in Lemaréchal and Oustry [9], leads to simple alternative derivations of well-known, important relaxations to two well-known problems of discrete optimization: the maximum stable set problem and the maximum vertex cover problem. The resulting relaxation is easily transformed to the well-known Lovász θ number.
A Dual Exterior Point Simplex Type Algorithm for the Minimum Cost Network Flow Problem
A dual of the rectangle-segmentation problem for binary matrices.
A formulation of combinatorial auction via reverse convex programming.
A Genetic Algorithm for Composing Music
A genetic algorithm for solving multiple warehouse layout problem
A literature review on circle and sphere packing problems: models and methodologies.
A Metaheuristic Approach to Solving the Generalized Vertex Cover Problem
AMS Subj. Classification: 90C27, 05C85, 90C59The topic is related to solving the generalized vertex cover problem (GVCP) by genetic algorithm. The problem is NP-hard as a generalization of well-known vertex cover problem which was one of the first problems shown to be NP-hard. The definition of the GVCP and basics of genetic algorithms are described. Details of genetic algorithm and numerical results are presented in [8]. Genetic algorithm obtained high quality solutions in a short period of time.
A New Efficient Transformation of the Generalized Vehicle Routing Problem into the Classical Vehicle Routing Problem
A new heuristic for the traveling salesman problem
A new relaxation in conic form for the euclidean Steiner problem in
In this paper, we present a new mathematical programming formulation for the euclidean Steiner Tree Problem (ESTP) in . We relax the integrality constrains on this formulation and transform the resulting relaxation, which is convex, but not everywhere differentiable, into a standard convex programming problem in conic form. We consider then an efficient computation of an -optimal solution for this latter problem using interior-point algorithm.
A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ
In this paper, we present a new mathematical programming formulation for the Euclidean Steiner Tree Problem (ESTP) in ℜ. We relax the integrality constrains on this formulation and transform the resulting relaxation, which is convex, but not everywhere differentiable, into a standard convex programming problem in conic form. We consider then an efficient computation of an ϵ-optimal solution for this latter problem using interior-point algorithm.
A note on a two dimensional knapsack problem with unloading constraints
In this paper we address the two-dimensional knapsack problem with unloading constraints: we have a bin B, and a list L of n rectangular items, each item with a class value in {1,...,C}. The problem is to pack a subset of L into B, maximizing the total profit of packed items, where the packing must satisfy the unloading constraint: while removing one item a, items with higher class values can not block a. We present a (4 + ϵ)-approximation algorithm when the bin is a square. We also present (3 + ϵ)-approximation...
A note on dual approximation algorithms for class constrained bin packing problems
In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity , and items of different classes, each item with class and size . The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size . In...
A note on dual approximation algorithms for class constrained bin packing problems
In this paper we present a dual approximation scheme for the class constrained shelf bin packing problem. In this problem, we are given bins of capacity 1, and n items of Q different classes, each item e with class ce and size se. The problem is to pack the items into bins, such that two items of different classes packed in a same bin must be in different shelves. Items in a same shelf are packed consecutively. Moreover, items in consecutive shelves must be separated by shelf divisors of size...
A note on operators of deletion and contraction for antichains.