Journals

Application of semi definite relaxation and variable neighborhood search for multiuser detection in synchronous CDMA
Networks, Volume 55 Issue 3, Pages 187 – 193, online version available on the publisher's site

Abstract
In this article, a detection strategy based on variable neighborhood search (VNS) and semidefinite relaxation of the multiuser model maximum likelihood (ML) is investigated. The VNS method provides a good method for solving the ML problem while keeping the integer constraints. A SDP relaxation is used as an efficient way to generate an initial solution in a limited amount of time, in particular using early termination. The SDP resolution tool used is the spectral bundle method developed by Helmberg. We show that using VNS can result in a better error rate, but at a cost of calculation time.

Keywords
semidefinite programming * variable neighborhood search * multiuser detection problem

Stochastic Quadratic Knapsack with Recourse
Electronic Notes in Discrete Mathematics, Volume 36, Pages 97-104, online version available on ScienceDirect.

This paper is dedicated to a study of different extensions of the classical 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. In this paper, we propose a model of two-stage quadratic knapsack with recourse in which we introduce a probability constraint on the capacity of the knapsack on the first stage. As far as we know, this is the first time such a constraint has been used in a two-stage model. The solution techniques are based on the semidefinite relaxations. This allows for solving large instances, for which exact methods cannot be used.

Keywords
Quadratic knapsack * Semidefinite programming * Stochastic programming * Chance constrained programming

Knapsack Problem With Probability Constraints
Journal of Global Optimization, to be published. Available on SpringerLink.

Abstract
This paper is dedicated to a study of different extensions of the classical 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. As far as we know, this is the first time such a constraint has been used in a two-stage model. The solution techniques are based on the semidefinite relaxations. This allows for solving large instances, for which exact methods cannot be used. Numerical experiments on a set of randomly generated instances are discussed below.

Keywords
Semidefinite programming * Knapsack problem * Stochastic optimization * Recourse

Research Reports

Knapsack Problem With Probability Constraints
Research Report #1498 - LRI
Download -> Report [PDF]