Exact solution methods for the Resource Constrained Project Scheduling Problem with a flexible Project Structure

The Resource Constrained Project Scheduling Problem with a flexible Project Structure (RCPSP-PS) is a generalization of the Resource Constrained Project Scheduling Problem (RCPSP). The objective of the RCPSP-PS is to find a minimal makespan schedule subject to precedence and resource constraints, while only having to execute a subset of all activities. We present a general … Read more

Approximation algorithms for the Transportation Problem with Market Choice and related models

Given facilities with capacities and clients with penalties and demands, the transportation problem with market choice consists in finding the minimum-cost way to partition the clients into unserved clients, paying the penalties, and into served clients, paying the transportation cost to serve them. We give polynomial-time reductions from this problem and variants to the (un)capacitated … Read more

Lattice based extended formulations for integer linear equality systems

We study different extended formulations for the set $X =\{x\in\mathbb{Z}^n \mid Ax = Ax^0\}$ in order to tackle the feasibility problem for the set $X_+=X \cap \mathbb{Z}^n_+$. Here the goal is not to find an improved polyhedral relaxation of conv$(X_+)$, but rather to reformulate in such a way that the new variables introduced provide good … Read more

Hard equality constrained integer knapsacks

We consider the following integer feasibility problem: “Given positive integer numbers $a_0,a_1,\dots,a_n,$ with $\gcd(a_1,\dots,a_n)=1$ and $\va=(a_1,\dots,a_n)$, does there exist a vector $\vx\in\bbbz^n_{\ge \zero}$ satisfying $\va\vx = a_0$?” Some instances of this type have been found to be extremely hard to solve by standard methods such as branch-and-bound, even if the number of variables is as … Read more

Models and Solution Techniques for Frequency Assignment Problems

Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modeling ideas for each of the features of the problem, such as the handling of interference … Read more