The quadratic linear ordering problem naturally generalizes various optimization problems, such as bipartite crossing minimization or the betweenness problem, which includes linear arrangement. These problems have important applications in, e.g., automatic graph drawing and computational biology. We present a new polyhedral approach to the quadratic linear ordering problem that is based on a linearization of … Read more
In this work we present an exact separation algorithm for the so called co-circuit inequalities, otherwise known as parity or 2-matching inequalities. The algorithm is quite simple since it operates on the tree of min-cuts of the support graph of the solution to separate, relative to an ad hoc capacity vector. The order of our … Read more
Intensity–modulated radiation therapy (IMRT) gives rise to systems of linear inequalities, representing the effects of radiation on the irradiated body. These systems are often infeasible, in which case one settles for an approximate solution, such as an {a,ß}–relaxation, meaning that no more than a percent of the inequalities are violated by no more than ß … Read more
We study a system of linear inequalities associated with the uncapacitated facility location problem. We show that this system defines a polytope with integer extreme points if and only if the graph does not contain a certain type of odd cycles. We also derive odd cycle inequalities and give a separation algorithm. ArticleDownload View PDF
This paper describes a new primal relaxation for nonlinear integer programming problems with linear constraints. This relaxation, contrary to the standard Lagrangean relaxation, can be solved efficiently. It requires the solution of a nonlinear penalized problem whose linear constraint set is known only implicitly, but whose solution is made possible by the use of a … Read more
The curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. We prove the analogue of the result of Klee and Walkup. Namely, we show that if the order of the curvature is less than the dimension $d$ for … Read more
We study cooperative games with supermodular costs. We show that supermodular costs arise in a variety of situations: in particular, we show that the problem of minimizing a linear function over a supermodular polyhedron–a problem that often arises in combinatorial optimization–has supermodular optimal costs. In addition, we examine the computational complexity of the least core … Read more
We present a general metaheuristic for joint chance-constrained stochastic programs with discretely distributed parameters. We give a reformulation of the problem that allows us to define a finite solution space. We then formulate a novel neighborhood for the problem and give methods for efficiently searching this neighborhood for solutions that are likely to be improving. … Read more
We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints … Read more
We consider the single item lot-sizing problem with capacities that are non-decreasing over time. When the cost function is i) non-speculative or Wagner-Whitin (for instance, constant unit production costs and non-negative unit holding costs), and ii) the production set-up costs are non-increasing over time, it is known that the minimum cost lot-sizing problem is polynomially … Read more