Igor Vasil’ev – Optimization Online

Computational study of a cutting plane algorithm for University Course Timetabling

Published: 2003/07/11, Updated: 2007/04/24

Branch and Cut Algorithms, Scheduling branch-and-cut, university course timetabling problem

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

Computational study of large-scale p-Median problems

Published: 2003/03/27, Updated: 2007/04/24

Pasquale Avella

Antonio Sassano

Igor Vasil'ev

Branch and Cut Algorithms branch-and-cut, column-and-row generation, p-median

Given a directed graph G(V,A), the p-Median problem consists of determining p nodes (the median nodes) minimizing the total distance from the other nodes of the graph. We present a Branch-and-Cut algorithm yielding provably good solutions for instances up to 3795 nodes (14,402,025 variables). Key ingredients of our approach are: lagrangian relaxation, a simple procedure … Read more