
Sixth Joint Operations Research Days
Organizing committee:
 Michel Bierlaire, EPFL
 Komei Fukuda, ETHZ and EPFL
 Jon Lee, IBM Research
 Thomas Liebling, EPFL
 HansJakob Lüthi, ETHZ
 Eleni Pratsini, IBM Research
We invite members of IBM research staff and Swiss OR researchers to submit abstracts about their recent research. We strongly encourage PhD students to present their results.
There is no registration fee. Registration will be confirmed on a first comefirst served basis.
Keynotes speakers
Prof. Friedrich Eisenbrand, Ecole Polytechnique Fédérale de Lausanne 

Integer Programming and the Geometry of Numbers Integer programming is related to convex geometry as well as to
algorithmic number theory, in particular to the algorithmic geometry of numbers.
In this talk, I survey some classical and recent results in the interplay of
integer programming and the geometry of numbers.

Prof. János Pach, Ecole Polytechnique Fédérale de Lausanne 

Conflictfree coloring Motivated by a frequency assignment problem in cellular telephone
networks, Even et al. studied the following question. Given a set
P of n points in general position in the plane, what is the
smallest number of colors in a coloring of the elements of P
with the property that any closed disk D with D∩
P≠∅ has an element whose color is not assigned to any
other element of D∩ P. We refer to such a coloring as a
conflictfree coloring of P with respect to disks.
In the original application, the points correspond to base
stations interconnected by a fixed backbone network. Each client
continuously scans frequencies in search of a base station within
its (circular) range with good reception. Once such a base station
is found, the client establishes a radio link with it, using a
frequency not shared by any other station within its range.
Therefore, a conflictfree coloring of the points corresponds to
an assignment of frequencies to the base stations, which enables
every client to connect to a base station without interfering with
the others.
We survey some basic results related to conflictfree colorings,
and outline some generalizations to graph and hypergraph colorings
based on joint work with Gábor Tardos.

Prof. Karl H. Schmedders, University of Zürich 

Solving Dynamic Games Dynamic stochastic games with a discrete state space have become the dominating tool in the analysis of industries with heterogeneous firms. The applicability of these economic models to explain observed industry dynamics, however, has been greatly limited by the computational burden to calculate equilibria for these models. The reasons for this burden are twofold. First, realistic industry descriptions give rise to models with large numbers of states and variables. Secondly, economists have traditionally applied numerical methods rooted in the motivation of Nash equilibria to solve these models, but these methods are not always well suited to compute equilibria.
In this talk we examine a standard dynamic game model and show that the equilibrium conditions give rise to large nonlinear systems of equations or large complementarity problems. We argue that solvers implementing standard numerical methods, such as the software PATH, can easily solve large dynamic games.

This schedule is tentative and may be modified later on.
Each talk (except the keynote presentations) has a slot of 20 minutes, including questions.
Thursday 




10:00 
10:30 
Coffee 




 Chairperson 
Jon Lee 
10:30 
11:15 
PACH 
EPFL 
Conflictfree coloring 
11:15 
11:20 
Short break 




 Chairperson 
Janos Pach 
11:20 
11:40 
Trautmann 
U Bern 
Resource Allocation Capabilities of Commercial Software Packages for
Project Management: An Experimental Performance Analysis 
11:40 
12:00 
Mastrolilli 
IDSIA 
(Acyclic) Job Shops are Hard to Approximate 
12:00 
12:20 
Stauffer 
IBM 
Decentralized decision making is close to optimal for onewarehouse
multiretailers systems 
12:20 
14:20 
Lunch 




 Chairperson 
Luca Gambardella 
14:20 
14:40 
Faltings 
EPFL 
Distributed Algorithms for Constraint Optimization 
14:40 
15:00 
Shankar 
IBM 
A Novel Algorithm for stochastic Linear Programs with a
ConditionalValueatRisk Objective and Conditionalvalueatrisk Constraints 
15:00 
15:20 
Klatte 
U Zürich 
Generalized semiinfinite programs: reduction approach and a nonsmooth
Newton method 
15:20 
15:50 
Coffee break 




 Chairperson 
Komei Fukuda 
15:50 
16:35 
EISENBRAND 
EPFL 
Integer Programming and the Geometry of Numbers 
16:35 
16:40 
Short break 




 Chairperson 
Friedrich Eisenbrand 
16:40 
17:00 
Foniok 
ETHZ 
Polynomial Pivoting for KLCP: A Proof Using UniqueSink Orientations 
17:00 
17:20 
Sviridenko 
IBM 
Approximation Algorithms for the OneWarehouse MultiRetailer problem 
17:20 
17:40 
Shmonin 
EPFL 
Integer programming gaps 
19:30 
 Dinner at Hotel Continental (click here for a map) 





Friday 






 Chairperson 
Gerald Reiner 
09:00 
9:20 
Horch 
ABB 
The Challenge of Increasing Complexity in Production Optimization 
9:20 
9:40 
Montemanni 
IDSIA 
Heuristic construction of Constant GCcontent DNA codes 
9:40 
10:10 
Coffee break 




 Chairperson 
Eleni Pratsini 
10:10 
10:55 
SCHMEDDERS 
U Zürich 
Solving Dynamic Games 
10:55 
11:00 
Short break 




 Chairperson 
Karl Schmedders 
11:00 
11:20 
Palvolgyi 
EPFL 
Decomposability of polygon coverings 
11:20 
11:40 
Babonneau 
Ordecsys 
A partitioning algorithm for the network loading problem 
11:40 
12:00 
Vacca 
EPFL 
Twostage column generation: a novel framework 
12:00 
14:00 
Lunch 




 Chairperson 
Michel Bierlaire 
14:00 
14:20 
Fulek 
EPFL 
Intersecting convex sets by rays 
14:20 
14:40 
Tiemessen 
IBM 
Heuristics for Inventory Replenishment and Service Request Fulfillment in
Spare Parts Networks 
14:40 
14:50 
Short break 




 Chairperson 
Norbert Trautmann 
14:50 
15:10 
Rothvoss 
EPFL 
A PTAS for Static Priority RealTime Scheduling with Resource
Augmentation 
15:10 
15:30 
Smorodinsky 
EPFL 
ConflictFree coloring made stronger 
18 abstracts  Frédéric Babonneau (Ordecsys)
Title: A partitioning algorithm for the network loading problem Abstract: We present a partitioning algorithm for the network loading problem (NLP). The NLP consists of installing least cost integer capacities on the arcs that are sufficient to handle a network flow that meets the demands.
Our solution method is a Benders partitioning scheme. The master program is a pure integer
programming problem in the space of capacities. The subproblem is a continuous optimization
problem ; it tests whether the integer capacities generated by the master program is sufficient to
support flows that meet the demands. It also computes supporting hyperplanes to the set of feasible fractional capacities. The subproblem makes it possible to construct a polyhedral relaxation of the set of feasible capacities while the master program looks for interesting integer solutions within that polyhedral relaxation.
Since the effort of computing integer solutions is entirely left to a pure integer programming solver (CPLEX in our case), the main advantage of our solution method is its simplicity. It also appear to be efficient on some problems.  Boi Faltings (EPFL)
Title: Distributed Algorithms for Constraint Optimization Abstract: We consider problems where multiple agents have to coordinate their
decisions because of shared resources or other interdependencies, and this
coordination problem can be formulated as a problem of constraint
optimization.
We survey distributed algorithms that allow such problems to be solved
without a central
authority.  Jan Foniok (ETH Zürich)
Title: Polynomial Pivoting for KLCP: A Proof Using UniqueSink Orientations Abstract: Joint work with K. Fukuda, B. GĂ¤rtner, H.J. Lüthi.
Uniquesink orientations of cubes provide a simple combinatorial description of simple principal pivoting methods for the linear complementarity problem (LCP). It had been known that there exists a pivot rule for the simple principal pivoting method that takes only a linear number of pivots to solve the Kmatrix LCP. Using uniquesink orientations, we were able to show that this is actually true for any pivot rule.  Radoslav Fulek (EPFL)
Title: Intersecting convex sets by rays Abstract: What is the smallest number t=t(n) such that for any
collection of n pairwise disjoint convex sets in ddimensional
Euclidean space, there is a point such that any ray (halfline)
emanating from it meets at most sets of the collection?
This question of Urrutia is closely related to the notion of regression depth introduced by Rousseeuw and Hubert (1996).
We show the following:
Given any collection C of n pairwise disjoint compact convex sets in ddimensional Euclidean space, there exists a point p such that any ray emanating from p meets at most
(dn+1)/(d+1) members of C.
There exist collections of n pairwise disjoint (i) equal
length segments or (ii) disks in the Euclidean plane such
that from any point there is a ray that meets at least 2n/32 of them.
We also determine the asymptotic behavior of t(n) when the convex bodies are fat and of roughly equal size.  Alexander Horch (ABB Corporate Research)
Title: The Challenge of Increasing Complexity in Production Optimization Abstract: Today’s industries are more than ever enforced to lower their operational costs, largely due to a harder global competition. One related target is to ensure that the overall result of earlier isolated optimization tasks is “globally optimal”, i.e. the decisions done on different levels or in different process sections do not negate, or counteract, each other. This has created a trend and more importantly a need of
increased information sharing between various decisionsupport systems. Inevitably, information sharing leads to more complex optimization systems as the models need to cover larger problem entities in order to merge previously separate optimization targets. Also, aspects earlier not considered may have to be included.
Another complexity increase arises from the communication need between the tasks. The earlier isolated problems (e.g. machinespecific production planning) become networked, which means that not all goals can be derived from local facts alone, but at least some must be handled globally.
Apart from the cultural change and integration challenges, it is very important to ensure that optimization methodologies can cope with the new demands. As no single strategy suffices to cover all industrial problem solutions – even within one
plant – a system of optimization systems needs to be designed by combination of methods, partitioning of problems and modeling collaboration. Some strategies of combining solution methods will be shown, followed by project examples carried out at ABB Corporate Research. Finally, future challenges and opportunities are discussed.  Diethard Klatte (IOR, UZH)
Title: Generalized semiinfinite programs: reduction approach and a nonsmooth Newton method Abstract: (in collaboration with Stephan Bütikofer IOR, UZH) We study nonlinear programs in finite dimensions with infinitely many inequality constraints, where the set of constraint indices depends on the state variables. Supposing strong regularity assumptions, the problem may be reduced to a standard nonlinear program with finitely many constraints, but now including some kind of nonsmoothness. We present this reduction procedure as well as convergence results and first numerical experiments for a nonsmooth Newton method for solving this type of models.  Monaldo Mastrolilli (IDSIA)
Title: (Acyclic) Job Shops are Hard to Approximate Abstract: Understanding the approximability of the job shop problem is considered one of the most prominent open problems in scheduling theory. Even though the best approximation algorithms have worse than logarithmic performance guarantee, the only known inapproximability result says that it is NPhard to approximate acyclic job shops within a factor less than~$5/4$.
For every $epsilon >0$, we show that the (acyclic) job shop problem cannot be approximated within ratio $O(log^{1epsilon} lb)$, unless $NP$ has quasipolynomial LasVegas algorithms, and where $lb$ denotes a trivial lower bound on the optimal value. This almost matches the
best known results for acyclic job shops, since an $
{O}(log^{1+epsilon} lb)$approximate solution can be obtained in polynomial time for every $epsilon>0$.
Recently, a PTAS was given for the job shop problem, where the
number of machines emph{and} the number of operations per job are
assumed to be constant. Under $P
ot = NP$, and when the number
$mu$ of operations per job is a constant, we provide an
inapproximability result whose value grows with $mu$ to infinity.
Moreover, we show that the problem with two machines has no PTAS,
unless $NP$ has quasipolynomial algorithms. These results show that
the restrictions on the number of machines and operations per job
are necessary to obtain a PTAS. Finally, we solve (negatively) an
open question raised by Bansal et al., by showing that even the
preemptive variant with three machines has no PTAS.
 Roberto Montemanni (IDSIA)
Title: Heuristic construction of Constant GCcontent DNA codes Abstract: DNA codes are sets of words of fixed length n over the alphabet {A, C, G, T} which satisfy a number of combinatorial conditions. They have application in DNA computing, in DNA microarray technologies and as molecular bar codes.
The combinatorial conditions considered are (i) minimum Hamming distance d, (ii) fixed GC content and, in some cases (iii) minimum distance d between any codeword and the reverse WatsonCrick complement of any codeword. The problem is to find DNA codes with the maximum number of codewords.
The construction of DNA codes is studied from an algorithmic perspective. Four local search algorithms are developed and combined in a variable neighbourhood search framework.
The algorithm has been run extensively. Over 254 problems considered, it was able to match or improve the best known lower bounds in 180 cases, with 52 new bests.
(join work with D.H. Smith, University of Glamorgan, UK)  Domotor Palvolgyi (EPFL)
Title: Decomposability of polygon coverings Abstract: A family of sets is a {em $k$fold} covering of a point set
if every point is contained in at least $k$ of the sets. A covering is {em decomposable} if the sets can be partitioned into two ($1$fold) coverings. We say that a geometric set is {em coverdecomposable}, if there exists a $k$ such that every $k$fold covering of {em any point set} in the plane by
its translates is decomposable.\
We show which polygons are coverdecomposable. It turns out that every convex polygon is coverdecomposable and almost every concave polygon is not coverdecomposable.  Thomas Rothvoss (EPFL)
Title: A PTAS for Static Priority RealTime Scheduling with Resource Augmentation Abstract: We present a polynomial time approximation scheme for the realtime scheduling problem
with fixed priorities when resource augmentation is allowed. For a fixed epsilon > 0, our
algorithm computes an assignment using at most (1+epsilon)*OPT +1 processors in polynomial
time, which is feasible if the processors have speed 1+epsilon.
This is joint work with Fritz Eisenbrand.  Gennady Shmonin (EPFL)
Title: Integer programming gaps Abstract: We consider the problem of finding the maximum difference between the optimum value of ab integer program and its linear programming relaxation, as the righthand side vector in the constraint matrix varies over a given polyhedron. It turns out that there is a polynomial algorithm for this problem if the number of variables is fixed.  Shakhar Smorodinsky (EPFL)
Title: ConflictFree coloring made stronger Abstract: In FOCS 2002, Even et al. showed that any set of $n$ discs in the
plane can be ConflictFree colored with a total of at most
$O(\log n)$ colors. Namely, it can be colored with $O(\log n)$
colors such that for any (covered) point $p$ there is some disc
whose color is distinct from all other colors of discs containing
$p$. They also showed that this bound is asymptotically tight.
We prove the following stronger result: Any set of $n$ discs in
the plane can be colored with a total of at most $O(k \log n)$
colors such that for any point $p$ that is covered by at least $k$
discs, there are at least $k$ distinct discs each of which is
colored by a color distinct from all other discs containing $p$
and for any point $p$ covered by at most $k$ discs, all discs
covering $p$ are colored distinctively. We call such a coloring a
{\em $k$Strong ConflictFree} coloring. We extend this result to
pseudodiscs and arbitrary regions with linear unioncomplexity.
Joint work with Elad Horev and Roi Krakovski  Gautier Stauffer (IBM )
Title: Decentralized decision making is close to optimal for onewarehouse multiretailers systems Abstract: Roundy developped in 1985 a centralized algorithm to manage
efficiently (within 2% of optimality) the inventory of a simple
distribution system consisting of one warehouse and many retailers,
where the retailers are facing continuous demands with constant rates.
In order to ensure near optimality of the global system, the retailers
usually have to increase their own optimal inventory costs. In
practice tough, for ease of implementation or for accounting purpose,
decisions are often taken in a decentralized way and all the retailers
and the central warehouse try to minimize their own inventory costs
independently of the others. In this talk we show that in the
continuous rate setting, this practical approach is ususally good
(within 6% of optimal in average) and is provably close to optimal
(within 1.2748 of optimal in the worst case).  Dharmashankar Subramanian (IBM Watson)
Title: A Novel Algorithm for stochastic Linear Programs with a ConditionalValueatRisk Objective and Conditionalvalueatrisk Constraints Abstract: ConditionalValueatRisk (CVaR), as a mathematical programmingfriendly risk measure, was first introduced by Uryasev & Rockafellar (2000). Using a discrete sampleapproximation of the underlying stochastic coefficients, they provided a linear reformulation for stochastic linear programs with CVaR objective/constraints, which can then be solved using generalpurpose linear programming solvers. An important point to note in this reformulation is that the resulting number of additional decision variables & the number of additional constraints, scale linearly with the size of samples. More recently, KunziBay and Mayer (2006) presented a twostage, stochastic programming interpretation of the above linear reformulation for the specific case of a CVaR Objective, and developed a computationally efficient algorithm, CVarMin, to address linear CVaR optimization in the objective function, observing an order of magnitude speedup.
We present a novel, computationally efficient algorithm for stochastic linear programs with both ConditionalValueatRisk (CVaR) Objective and Conditionalvalueatrisk Constraints, retaining the above discrete sampleapproximation of the stochastic coefficients. We start with a reformulation that is different from the above references, and iteratively construct and solve a sequence of compactsized linear optimization problems. We also show that the resulting sequence converges to the true optimal solution of the samplepredicated linear program. The problem size in each iteration of the sequence is unaffected by the size of random samples, which makes it very efficient for largescale problems. A comparison with the generalpurpose linear reformulation of Uryasev & Rockafellar suggests at least an order of magnitude speedup of computational time, and more improvement with increasing number of CVaR constraints and size of samples. Applications include practical problems, such as, portfolio optimization.  Maxim Sviridenko (IBM T.J. Watson Research Center)
Title: Approximation Algorithms for the OneWarehouse MultiRetailer problem Abstract: Deterministic inventory theory provides streamlined optimization
models that attempt to capture tradeoffs in managing the flow of
goods through a supply chain. We will consider two wellstudied
deterministic inventory models, called the {em onewarehouse
multiretailer problem} (OWMR) and its special case the {em joint
replenishment problem} (JRP), and give approximation algorithms
with improved performance guarantees; more specifically, we give a
1.8approximation algorithm for both problems. Our results are
based on an LProunding approach and improve previous results of
Levi, Roundy and Shmoys. Our results also show strong integrality
gaps for the corresponding linear programs.  Harold Tiemessen (IBM Research)
Title: Heuristics for Inventory Replenishment and Service Request Fulfillment in Spare Parts Networks Abstract: Motivated by IBMs spare parts logistics, we present a distributed inventory network for spare parts where service requests can usually be solved from multiple local warehouses. We consider a singleitem, multilocation, singleechelon model with service level constraints and centralized control.
We discuss an inventory controller that consists of a decision rule for selecting the local warehouse that sends out a part to a waiting customer, and a heuristic for calculating replenishment orders. Replenishment orders are calculated by solving a simple but statedependent LP model at carefully selected moments in time.
What differentiates the proposed solution from many existing solutions is that we use stock level information from the entire network to jointly optimize replenishment decisions at all local warehouses. We have carried out simulation experiments to evaluate the proposed solution at different scenarios. We present and discuss the results and draw conclusions.
 Norbert Trautmann (University of Bern)
Title: Resource Allocation Capabilities of Commercial Software Packages for Project Management: An Experimental Performance Analysis Abstract: We report on the results of an experimental analysis where we have compared the resource allocation capabilities of recent versions of 5 commercial project management software packages against stateoftheart solution methods from the literature. For our analysis, we have used 1560 RCPSP instances from the standard test set PSPLIB. The results indicate that using the automatic resource allocating feature of those packages may result in project durations that are considerably longer than necessary, in particular when the resource scarcity is high or when the number of activities is large.  Ilaria Vacca (EPFL)
Title: Twostage column generation: a novel framework Abstract: Column generation has been intensively used in the last decades to compute good quality lower bounds for combinatorial
problems reformulated through DantzigWolfe decomposition. In this
work we propose a novel framework to cope with problems in which the structure of the original formulation, namely the presence of a combinatorial number of decision variables, does not allow for straightforward reformulation. The basic idea is to start from a
meaningful subset of original variables, apply the DW reformulation to the subset, solve the reformulation with column generation and perform the explicit pricing on original variables retracing back the reformulation and using complementaryslackness conditions. The Discrete Split Delivery Vehicle Routing Problem with Time Windows (DSDVRPTW) is used as an illustration for the method, which provides a new exact approach to the problem. Preliminary computational experiments are reported. This is joint work with Matteo Salani.
All participants, including speakers, must register using the following registration forms.
Registration deadline: August 25, 2008. Today is March 24, 2010. Sorry, the deadline is over.
Click here to submit an abstract.
Current number of registered participants: 47
Alipour  Masoud  EPFL  Antonini  Gianluca  IBM ZRL  Babonneau  Frédéric  Ordecsys  Bielser  Mike  IOR, University of Zurich  Bierlaire  Michel  TRANSPOR, EPFL  Boedi  Richard  IBM Research  Cope  Eric  IBM Zurich Research Lab  Eisenbrand  Friedrich  DISOPT, EPFL  Flötteröd  Gunnar  Berlin Institute of Technology  Foniok  Jan  ETH Zurich  Fukuda  Komei  ETH Zurich  Fulek  Radoslav  EPFL  Gambardella  Luca Maria  IDSIA  Horch  Alexander  ABB Corporate Research, Ladenburg, Germany  Klatte  Diethard  IOR, UZH  Labbi  Abdel  IBM Research  Zurich  Laumanns  Marco  IFOR, ETH Zurich  Lee  Jon  IBM TJ Watson Research Center  Liebling  Thomas  EPFL  Mastrolilli  Monaldo  IDSIA  Mayer  Janos  Institute for Operations Research, University of Zurich  Montemanni  Roberto  IDSIA  Nesterov  Yurii  CORE UCL Belgium  Pach  Janos  DCG, EPFL  Palvolgyi  Domotor  EPFL  Pratsini  Eleni  IBM Zurich Research Lab  Prodon  Alain  EPFL  ROSO  Ray  Bonnie  IBM Watson Research Center  Reiner  Gerald  Université de Neuchâtel  Robin  Thomas  TRANSPOR, EPFL  Rosta  Vera  Renyi Institute Budapest  Rothvoss  Thomas  DISOPT, EPFL  sallam  karam  department assistant in faculty of computer and informaticsoperation research dept  Schmedders  Karl  University of Zurich  Shmonin  Gennady  DISOPT, EPFL  Smorodinsky  Shakhar  Ben Gurion University  Stauffer  Gautier  IBM Zurich Research Lab  Subramanian  Dharmashankar  IBM Research  Sviridenko  Maxim  IBM TJ Watson Research Center  Tiemessen  Harold  IBM Research  Trautmann  Norbert  BWL, University of Bern  Uldry  Marc  Université de Fribourg  DIUF  Vacca  Ilaria  TRANSPOR, EPFL  Vial  JeanPhilippe  ORDECSYS  von Bergen  Silvia  IOR, University of Zurich  Widmer  Marino  Université de Fribourg  DIUF  Zenklusen  Rico  ETH Zurich 
EPFLrates apply to the following hotels. Prices are indicative. Please contact the hotel for the exact rates.
In Lausanne
 Swiss Youth Hotels
 BoisdeVaux 36, 1007 Lausanne
tél: +41 21 626.02.22
fax: +41 21 626.02.26
adresse email: lausanne@youthhostel.ch
single: 78.00
 Hôtel Elite
 Avenue SteLuce 1
1003 Lausanne
tél: +41 21 320 23 61
fax: + 41 21 320 39 63
single: 117.00; double: 174.00
 Hôtel Alagare
 Minotel Suisse
Rue du Simplon 14
1006 Lausanne
tél: +41 21 617 92 52
fax: +41 21 617 92 55
single 105.00; double: 150.00
 Hôtel AlphaPalmiers
 Fassbind Hotels
Rue du Petit.Chęne 34
1003 Lausanne
tél: +41 21 555 59 99
fax: +41 21 555 59 98
single: 158.00; double: 220.00
EPFL area

Hotel PréFleuri***
 Rue du Centre 1, 1025 StSulpice.
Email: prefleuri@bluewin.ch
Tél. 021 691 20 21
Fax 021 691 20 20
Price for a single room around CHF 150.
 Motel des Pierrettes** StSulpice
 10 minutes walk to EPFL
Route cantonale 19, 1025 StSulpice
It has no website but you can call at +41 21 691 25 25.
It has no restaurant.
Price for a single room, around CHF 110. (special price for EPFL hosts)
 Hostellerie du Débarcadčre
 Chemin du Cręt 7, 1025 StSulpice,
It belongs to "Relais& Châteaux"
Website: www.debarcadere.ch
Price for a single room around CHF 170. (special price for EPFL hosts)
 Novotel Lausanne Bussigny
 35, Route de Condémines, 1030 Bussigny
(15 minutes by car, no bus possibilities)
Price for a single room, around CHF 200. (special price for EPFL hosts)
The easiest way to get to EPFL is to take the train from Geneva Airport to Renens. In Renens, take the lightrail (called M1) towards Lausanne. There is a stop at EPFL. The travel time is about 1 hour.
A map of the bus and metro network can be found here and time tables are available at the Lausanne Transport web page. Note that tickets must be bought before departure in machines only accepting coins. The price for a oneway ticket from the center of Lausanne to EPFL is 2.80 Fr. (two zones) and most machines do not give back change.
Check the Swiss Federal Railways website.
To navigate within EPFL, use map.epfl.ch.
Consult also this page
