Karen I. Aardal

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

  • T. Van der Beek
  • J.T. Van Essen
  • J. Pruyn
  • Karen I. Aardal
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    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

  • Karen I. Aardal
  • Pierre Le Bodic
    • Categories Approximation Algorithms Tags , ,

    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

  • Karen I. Aardal
  • Laurence A. Wolsey
    • Categories (Mixed) Integer Linear Programming

    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

  • Karen I. Aardal
  • Arjen K. Lenstra
    • Categories Integer Programming Tags , ,

    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

  • Karen I. Aardal
  • Arie M.C.A. Koster
  • Carlo Mannino
  • Antonio Sassano
  • Stan P.M. van Hoesel
    • Categories Graphs and Matroids, Telecommunications Tags

    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