We introduce orbitopes as the convex hulls of 0/1-matrices that are lexicographically maximal sub ject to a group acting on the columns. Special cases are packing and partitioning orbitopes, which arise from restrictions to matrices with at most or exactly one 1-entry in each row, respectively. The goal of investigating these polytopes is to gain … Read more
Given a set of clients and a set of potential sites for facilities, several location problems consist of opening a set of sites and assigning each client to the closest open facility to it. It can be viewed as a variation of the uncapacitated facility location problem. We propose a new formulation of this problem … Read more
We consider the problem of interconnecting a set of customer sites using SONET rings of equal capacity, which can be defined as follows: Given an undirected graph G=(V,E) with nonnegative edge weight d(u,v), (u,v) in E, and two integers K and B, find a partition of the nodes of G into K subsets so that … Read more
We describe an effective method for doing binary-encoded modeling, in the context of 0/1 linear programming, when the number of feasible configurations is not a power of two. Our motivation comes from modeling all-different restrictions. Article Download View Parsimonious Binary-Encoding in Integer Programming
Video on Demand (VoD) is a technology used to provide a number of programs to a number of users on request. In developing a VoD system, a fundamental problem is load balancing, which is further characterized by optimally placing videos to a number of predefined servers and routing the user program requests to available resources. … Read more
In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results … Read more
We propose a simple and sufficiently fast separation procedure to identify cover inequalities for the multidimensional knapsack problem. It is based on the solution of a conventional integer programming model. Solving this kind of integer programs are usually considered expensive and the proposed method may have been overlooked because of this assumption. The results of … Read more
This paper first presents an improve cutting plane method for solving the linear programming problems, based on the primal simplex method with the current equivalent facet technique, in which the increment of objection function is allowed as a pivot variable to decide the search step size. We obtain a strong valid inequality from the objective … Read more
For a real world problem — transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand — we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost … Read more
In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of … Read more