Combinatorial Optimization – Page 90

Easy distributions for combinatorial optimization problems with probabilistic constraints

Published: 2009/10/22, Updated: 2010/02/22

Combinatorial Optimization, Stochastic Programming combinatorial optimization, continuous distributions, probabilistic constraint

We show how we can linearize probabilistic linear constraints with binary variables when all coefficients are distributed according to either $\mathcal{N}(\mu_i,\lambda \mu_i)$, for some $\lambda >0$ and $\mu_i>0$, or $\Gamma(k_i,\theta)$ for some $\theta >0$ and $k_i>0$. The constraint can also be linearized when the coefficients are independent and identically distributed if they are, besides, either … Read more

Reformulation of the Hadamard conjecture via Hurwitz-Radon word systems

Published: 2009/10/13

Miklós Ujvári

Combinatorial Optimization

The Hadamard conjecture (unsolved since 1867) states that there exists an orthogonal matrix with entries of the same absolute value if and only if the order of the matrix is one, two, or is divisible by four. In the paper we reformulate this conjecture using Hurwitz-Radon word systems. (A Hurwitz-Radon word system is a system … Read more

Exact Solution of Emerging Quadratic Assignment Problems

Published: 2009/10/12, Updated: 2010/02/13

Applications - OR and Management Sciences, Combinatorial Optimization, Facility Planning and Design combinatorial optimization, quadratic assignment, reformulation linearization, survey

We report on a growing class of assignment problems that are increasingly of interest and very challenging in terms of the difficulty they pose to attempts at exact solution. These problems address economic issues in the location and design of factories, hospitals, depots, transportation hubs and military bases. Others involve improvements in communication network design. … Read more

Integer Network Synthesis Problem for Hop Constrained Flows

Published: 2009/10/12

Santosh N. Kabadi

K. P. K. Nair

Combinatorial Optimization, Network Optimization hop constraints, network synthesis, telecommunications

Hop constraint is associated with modern communication network flows. We consider the problem of designing an optimal undirected network with integer-valued edge-capacities that meets a given set of single-commodity, hop-constrained network flow value requirements. We present a strongly polynomial, combinatorial algorithm for the problem with value of hop-parameter equal to three when values of flow … Read more

Biased random-key genetic algorithms for combinatorial optimization

Published: 2009/10/09

José Fernando Gonçalves

Mauricio G.C. Resende

Meta Heuristics, Stochastic Approaches biased random-key genetic algorithms, combinatorial optimization, genetic algorithm, metaheuristics, random-key genetic algorithms

Random-key genetic algorithms were introduced by Bean (1994) for solving sequencing problems in combinatorial optimization. Since then, they have been extended to handle a wide class of combinatorial optimization problems. This paper presents a tutorial on the implementation and use of biased random-key genetic algorithms for solving combinatorial optimization problems. Biased random-key genetic algorithms are … Read more

Paths, Trees and Matchings under Disjunctive Constraints

Published: 2009/10/04, Updated: 2012/12/01

Graphs and Matroids, Network Optimization

We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict … Read more

Molecular distance geometry methods: from continuous to discrete

Published: 2009/09/27, Updated: 2009/10/03

Biomedical Applications, Combinatorial Optimization branch-and-prune, distance geometry, network localization, rigidity

Distance geometry problems arise from the need to position entities in the Euclidean $K$-space given some of their respective distances. Entities may be atoms (molecular distance geometry), wireless sensors (sensor network localization), or abstract vertices of a graph(graph drawing). In the context of molecular distance geometry, the distances are usually known because of chemical properties … Read more

Solving Large Steiner Triple Covering Problems

Published: 2009/09/22

0-1 Programming, Branch and Cut Algorithms branch-and-bound algorithms, integer programming, steiner triple systems, symmetry

Computing the 1-width of the incidence matrix of a Steiner Triple System gives rise to small set covering instances that provide a computational challenge for integer programming techniques. One major source of difficulty for instances of this family is their highly symmetric structure, which impairs the performance of most branch-and-bound algorithms. The largest instance in … Read more

Resource Allocation with Time Intervals

Published: 2009/09/21, Updated: 2012/12/01

Andreas Darmann

Ulrich Pferschy

Joachim Schauer

Combinatorial Optimization, Scheduling proper intervals, resource allocation, unsplittable flow

We study a resource allocation problem where jobs have the following characteristics: Each job consumes some quantity of a bounded resource during a certain time interval and induces a given profit. We aim to select a subset of jobs with maximal total profit such that the total resource consumed at any point in time remains … Read more