|
|
Detailed schedule
Click on a link for more details
Show all the abstracts
Thursday 30 January:
Thursday 11:15-12:30 TA-1: COMEX - Optimization 1 Room Vesale 023 - Chair: M. Schyns
Thursday 11:15-12:30 TA-2: Software and Implementation Room Vesale 020 - Chair: M. Mezmaz
Thursday 11:15-12:30 TA-3: COMEX - Smart mobility Room Vesale 025 - Chair: A. Caris
Thursday 11:15-12:30 TA-4: Systems Room Pentagone 0A11 - Chair: P. Kunsch
Thursday 14:00-15:40 TB-1: Data Analysis 1 Room Vesale 023 - Chair: X.Siebert
Thursday 14:00-15:40 TB-2: Multiple Objectives Room Vesale 020 - Chair: Y. de Smet
Thursday 14:00-15:40 TB-3: Logistics Room Vesale 025 - Chair: D. De Wolf
Thursday 14:00-15:40 TB-4: COMEX - Applications to Economy Room Pentagone 0A11 - Chair: W. Brauers
Thursday 14:00-15:40 TB-5: Networks Room Pentagone 0A07 - Chair: B. Fortz
Thursday 16:10-17:25 TC-1: Mixed-integer nonlinear programming Room Vesale 023 - Chair: Y. Crama
Thursday 16:10-17:25 TC-2: Decision Analysis 1 Room Vesale 020 - Chair: S. Eppe
Thursday 16:10-17:25 TC-3: Routing Room Vesale 025 - Chair: K. Sörensen
Thursday 16:10-17:25 TC-4: Graphs Room Pentagone 0A11 - Chair: H. Mélot
Thursday 16:10-17:25 TC-5: Scheduling Room Pentagone 0A07 - Chair: S. Hanafi
Friday 9:00-10:15 FA-1: Queuing Room Vesale 023 - Chair: S. Wittevrongel
Friday 9:00-10:15 FA-2: Decision Analysis 2 Room Vesale 020 - Chair: R. Bisdorff
Friday 9:00-10:15 FA-3: COMEX - Optimization 2 Room Vesale 025 - Chair: M. Labbé
Friday 9:00-10:15 FA-4: Production Room Pentagone 0A11 - Chair: D. Tuyttens
Friday 14:00-15:40 FB-1: Data Analysis 2 Room Vesale 023 - Chair: P. Fortemps
- The carry-over effect does exist in tennis
Dries Goossens (Ghent University) Co-authors: Frits Spieksma
- Alternative Pairwise Decomposition Techniques for Label Ranking
Massimo Gurrieri (UMONS) Co-authors: Philippe Fortemps, Xavier Siebert
- Constrained Clustering using Column Generation
Behrouz Babaki (KU Leuven) Co-authors: Tias Guns, Siegfried Nijssen
- Geometrical lower bound for the nonnegative rank of slack matrices
Julien Dewez (Université catholique de Louvain) Co-authors: Nicolas Gillis, François Glineur Abstract: The nonnegative rank of an element-wise nonnegative matrix is the minimum number of nonnegative rank-one factors needed to reconstruct it exactly. Computing this rank and a related factorization is NP-hard. However it can be used to describe an extension of a convex polytope, i.e., a higher-dimensional polytope which projects onto the original polytope, with minimum number of facets. These extensions for polytopes have important applications in combinatorial optimization.
More precisely, many combinatorial optimization problems can be formulated as the optimization of a linear objective function over a polytope which may have a very large number of facets (possibly increasing exponentially with the size of the problem). Because of the high number of facets, computing the optimal solution of this linear optimization problem can be very time consuming. However, if one can find an extension for this polytope with a moderate number of facets (growing for example polynomially with the size of the problem), one can solve the optimization problem over the extension efficiently, and project its optimal solution back to the original polytope of feasible solutions.
Therefore, we would like to know the extension complexity of the polytope of feasible solutions, i.e., the minimum number of facets of any extension of this polytope. In particular, if the extension complexity grows exponentially with the size of the problem, then the polytope of feasible solutions does not admit any extension with a polynomial number of facets and we will not able to solve the problem in polynomial time with this approach.
Crucially, the extension complexity of a polytope is also the nonnegative rank of a particular matrix called the slack matrix. The extension complexity is then also NP-hard to compute in general.
In this talk, we introduce a new geometrical lower bound on the extension complexity of a polytope which relies on the monotone behavior of the f-vector of a convex polytope under projections (where the f-vector is the collection of the numbers of k-faces of the polytope). This new lower bound improves upon existing lower bounds and, in some cases, implies optimality of the best known extension.
Friday 14:00-15:40 FB-2: Heuristics Room Vesale 020 - Chair: T. Stützle
Friday 14:00-15:40 FB-3: COMEX - Transportation Room Vesale 025 - Chair: F. Spieksma
Friday 14:00-15:40 FB-4: Health Room Pentagone 0A11 - Chair: G. Vanden Berghe
|
|