********************************************************************


                                                     Seminar

             Department of Systems Engineering and Engineering Management
                                  The Chinese University of Hong Kong

------------------------------------------------------------------------------------------

　

　

　

Title

:

Knapsack problem with probability constraints

　

　

　

Speaker

:

Prof. Abdel Lisser

　

　

Laboratoire de Recherche en Informatique

　

　

Universite de Paris Sud

　

　

　

Date

:

September 29th, 2008 (Monday)

　

　

　

Time

:

4:30 p.m. - 5:30 p.m.

　

　

　

Venue

:

Room 513

　

　

William M.W. Mong Engineering Building

　

　

(Engineering Building Complex Phase 2)

　

　

CUHK

　

　

　

------------------------------------------------------------------------------------------

Abstract:
　

We present different extensions of the knapsack problem to the case when different elements of the problem formulation are subject to a degree of uncertainty described by random variables. This brings the knapsack problem into the realm of stochastic programming. Two different model formulations are proposed, based on the introduction of probability constraints. The first one is a static quadratic knapsack with a probability constraint on the capacity of the knapsack. The second one is a two-stage quadratic knapsack model, with recourse, where we introduce a probability constraint on the capacity of the knapsack in the second stage. To our knowledge, this is the ¯rst time such a constraint has been used in a two-stage model. The solution techniques are based on the semi-definite relaxations. This allows for solving large instances. Results of numerical experiments are discussed.


-------------------------------------------------------------------------------------------

Biography:
　

Abdel Lisser is Professor in Computer Science laboratory of University of Paris Sud since 2001. He was heading research group at France Telecom from Research Center 1996 to 2001 and research engineer at France Telecom Research Center from 1988 to 1996. He got the master degree at the University of Paris Sorbonne in Mathematical Economics in 1984. He got the Ph.D at the University of Paris Dauphine in Computer Science in 1987 and the Habilitation thesis at the University of Paris Nord in 2000. His main research area is combinatorial and stochastic optimization with application to telecommunication and recently energy problems.


************************* ALL ARE WELCOME ************************

　

　

　

Host

:

Prof. Janny Leung

Tel

:

(852) 2609-8238

Email

:

janny@se.cuhk.edu.hk

　

　

　

Enquiries

:

Prof. Nan Chen or Prof. Sean X. Zhou

　

:

Department of Systems Engineering and Engineering Management

　

　

CUHK

Website

:

http://www.se.cuhk.edu.hk/~seg5810

Email

:

seg5810@se.cuhk.edu.hk

　

　

　

********************************************************************