2015

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Exact Algorithms for Nonconvex Quadratic Integer Optimization
Description:	Christoph Buchheim The talk addresses the problem of minimizing a quadratic objective function over integer variables. Even in the most simple case of binary or box-constrained integer variables, such problems are very hard to solve in theory and in practice. In fact, the problem remains NP-hard both in the case of a convex objective function over binary variables (then being equivalent to max-cut) and in the case of a non-convex objective function over the unit cube (the so-called BoxQP). After shortly reviewing some classical approaches for quadratic discrete optimization, we present two recent methods that are specifically designed for the nonconvex case, aiming at relaxations that jointly address the nonconvexity of the objective function and the nonconvexity of the discrete variable domains. While the first approach results in a semidefinite relaxation of the problem, the second approach uses ellipsoidal relaxations; both approaches can be embedded into branch-and-bound schemes. We present experimental results for the resulting algorithms, showing that the SDP-based approach yields very strong dual bounds that however take more time to be computed, while the second approach based on ellipsoidal relaxations is able to enumerate a large number of nodes in a short time due to a sophisticated preprocessing phase. The resulting total running times are comparable; both approaches however significantly outperform standard software such as Couenne or BARON.

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	EXACT APPROACHES TO THE NETWORK DESIGN PROBLEM WITH RELAYS
Description:	Ivana Ljubic This work considers the Network Design Problem with Relays (NDPR). The NDPR arises in the context of network design when given node-pairs need to communicate with each other, but, due to signal deterioration, communication paths have to respect given distance limits. To cover longer distances, equipment for signal regeneration (i.e., relays) may be required. To enable required communications, one has to upgrade the network: by installing new links, by installing relays on the existing network, or by a combination of both. Besides applications in network design, the NDPR arises in the context of e-mobility where relays model charging stations for electric cars and edge costs correspond to road tolls. In contrast to previous work on the NDPR, which was mainly focused on heuristic approaches, we propose new exact approaches based on different mixed integer linear programming formulations for the problem. We develop Branch-and-Price and Branch-Price-and-Cut algorithms that build upon models with an exponential number of constraints and variables. In a computational study, we analyze the performance of these approaches for instances with different characteristics. This is a joint work with M. Leitner, M. Riedler and M. Ruthmair

Heure:	12:30 - 13:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Approximating the energy storage problem and other continuous dynamic programs
Description:	Giacomo Nannicini We study the problem of optimally managing a source of renewable energy connected to the power grid, a battery, and potentially a household or some other form of energy sink. This problem can be naturally cast as a dynamic program. We propose a model for this problem that subsumes other models in the literature, and we analyze its complexity, showing that in the deterministic setting the problem is solvable in polynomial time, but it becomes #P-hard in the stochastic setting. A variant of the problem that is commonly encountered in practice (i.e. the one where selling energy to the power grid is not allowed) admits a Fully Polynomial Time Approximation Scheme (FPTAS) if the energy levels are discretized; but what about the more natural case where energy is considered a continuous variable? We show that in this case, the problem belongs to a class of convex continuous dynamic programs that admits neither a multiplicative nor an additive approximation. We then show that we can construct a novel type of approximation scheme, where additive and multiplicative approximation are required at the same time but both can be arbitrarily small. We discuss a preliminary computational evaluation of this new type of approximation scheme for continuous convex dynamic programs, showing its potential.