In this study, a lifting procedure is applied to some existing formulations of the Diameter Constrained Minimum Spanning Tree Problem. This problem typically models network design applications where all vertices must communicate with each other at minimum cost, while meeting or surpassing a given quality requirement. An alternative formulation is also proposed for instances of … Read more
This paper deals with a capacitated hub location problem arising in the design of telecommunications networks. The problem is different from the classical hub location problem in two ways: the cost of using an edge is not linear but stepwise and the capacity of an hub restricts the amount of traffic transiting through the hub … Read more
We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are … Read more
Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen the linear programming relaxation. Recently, a number of … Read more
In a previous work, we proposed a new integer programming formulation for the graph coloring problem which, to a certain extent, avoids symmetry. We studied the facet structure of the 0/1-polytope associated with it. Based on these theoretical results, we present now a Branch-and-Cut algorithm for the graph coloring problem. Our computational experiences compare favorably … Read more
A well-known extension of the Travelling Salesman Problem (TSP) is the Selective TSP (STSP): Each node has an associated profit and instead of visiting all nodes, the most profitable set of nodes, taking into account the tour cost, is visited. The Quadratic STSP (QSTSP) adds the additional complication that each pair of nodes have an … Read more
Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in Koster and Zymolka … Read more
The concentrator location problem is to choose a subset of a given terminal set to install concentrators and to assign each remaining terminal node to a concentrator to minimize the cost of installation and assignment. The concentrators may have capacity constraints. We study the polyhedral properties of concentrator location problems with different capacity structures. We … Read more
In this paper we describe a successful case-study where a Branch-and-Cut algorithm yields the \lq\lq optimal” solution of a real-world timetabling problem of University courses \emph{(University Course Timetabling problem)}. The problem is formulated as a \emph{Set Packing problem} with side constraints. To tighten the initial formulation, we utilize well-known valid inequalities of the Set Packing … Read more
The hub location problem with single assignment is the problem of locating hubs and assigning the terminal nodes to hubs in order to minimize the cost of hub installation and the cost of routing the traffic in the network. There may also be capacity restrictions on the amount of traffic that can transit by hubs. … Read more