Department of Mathematics

Search

Optimization seminar

×

Modal title

Modal content

Spring Semester 2013

Date / Time Speaker Title Location
18 February 2013
16:30-18:00 		Prof. Dr. Helmut Gfrerer
Johannes Kepler Universität, Linz, Austria
Event Details

Optimization Seminar

Title Optimality Conditions for Mathematical Programs with Equilibrium Constraints
Speaker, Affiliation Prof. Dr. Helmut Gfrerer, Johannes Kepler Universität, Linz, Austria
Date, Time 18 February 2013, 16:30-18:00
Location HG G 19.1
Abstract Mathematical programs with equilibrium constraints, MPEC for short, form a difficult class of optimization problems. When formulated as a smooth problem, most of the standard constraint qualification conditions are violated. Hence a non-smooth approach is more appropriate to formulate optimality conditions. Using Clarkes generalized gradient yields the so-called C-stationarity conditions, wheras the use of coderivatives introduced by Mordukhovich yields the concept of M-stationarity, which is stronger than C-stationarity. Recently considerable progress has been made in the charcterization of metric subregularity by coderivative-like objects from generalized differentiation. Applying these results to MPECs, we obtain a new set of optimality conditions which we call extended M-stationarity conditions. We also obtain second-order optimaliy conditions, both necessary and sufficient, which generalize the well-known second-order conditions for mathematical programs with equality and inequality constraints and finally we state necessary conditions for MPECs with degenerated constraints.
Optimality Conditions for Mathematical Programs with Equilibrium Constraintsread_more
HG G 19.1
25 February 2013
16:30-18:00 		PD Dr. Alexander Souza
Apixxo AG, Olten, CH
Event Details

Optimization Seminar

Title Approximation Algorithms for Generalized and Variable Sized Bin Covering
Speaker, Affiliation PD Dr. Alexander Souza, Apixxo AG, Olten, CH
Date, Time 25 February 2013, 16:30-18:00
Location HG G 19.1
Abstract We consider the Generalized Bin Covering problem: We are given $m$ bin types, where each bin of type $i$ has profit $p_i$ and demand $d_i$. Furthermore, there are $n$ items, where item $j$ has size $s_j$. A bin of type $i$ is covered if the set of items assigned to it has total size at least the demand $d_i$. Then, the profit of $p_i$ is earned and the objective is to maximize the total profit. To the best of our knowledge, only the cases $p_i = d_i = 1$ (Bin Covering) and $p_i = d_i$ (Variable-Sized Bin Covering) have been treated before. We study two models of bin supply: In the unit supply model, we have exactly one bin of each type, i.e., we have individual bins. By contrast, in the infinite supply model, we have arbitrarily many bins of each type. Both versions of the problem are $\NP$-hard and can not be approximated better than $2$, unless $\P = \NP$. Our results in the unit supply model hold not only symptotically, but for all instances. This contrasts most of the previous work on Bin Covering, which has been asymptotic. We prove that there is a combinatorial $5$-approximation algorithm for Generalized Bin Covering with unit supply, which has running time $O(nm\sqrt{m+n})$. This also transfers to the infinite supply model. Furthermore, for Variable-Sized Bin Covering, in which we have $p_i = d_i$, we show that the natural and fast Next Fit Decreasing (NFD) algorithm is a $9/4$-approximation in the unit supply model. The bound is tight for the algorithm and close to being best-possible. Our analysis gives detailed insight into the limited extent to which the optimum can significantly outperform NFD. Then we discuss the difficulty of defining asymptotics in the unit supply model. For two natural definitions, the negative result holds that Variable-Sized Bin Covering in the \emph{unit} supply model does not allow an APTAS. Clearly, this also excludes an APTAS for Generalized Bin Covering in that model. Nonetheless, we show that there is an AFPTAS for Variable-Sized Bin Covering in the \emph{infinite} supply model. Alexander Souza, Apixxo AG (joint work with Matthias Hellwig, HU Berlin)
Approximation Algorithms for Generalized and Variable Sized Bin Coveringread_more
HG G 19.1
18 March 2013
16:30-18:00 		Prof. Dr. Dan A. Iancu
Stanford University, Stanford, USA
Event Details

Optimization Seminar

Title Pareto Efficiency in Robust Optimization
Speaker, Affiliation Prof. Dr. Dan A. Iancu, Stanford University, Stanford, USA
Date, Time 18 March 2013, 16:30-18:00
Location HG G 19.2
Abstract In this talk, we formalize and adapt the well-known concept of Pareto efficiency in the context of the popular robust optimization (RO) methodology. We argue that the classical RO paradigm need not produce solutions that possess the associated property of Pareto optimality, and illustrate via examples how this could lead to inefficiencies and sub-optimal performance in practice. We provide a basic theoretical characterization of Pareto robustly optimal (PRO) solutions, and extend the RO framework by proposing practical methods that verify Pareto optimality, and generate solutions that are PRO. Critically important, our methodology involves solving optimization problems that are of the same complexity as the underlying robust problems, hence the potential improvements from our framework come at essentially no computational cost. We perform numerical experiments drawn from three different application areas (portfolio optimization, inventory management, and project management), which demonstrate that PRO solutions have a significant upside compared with solutions obtained via classical RO methods, at no extra cost or downside. ( Joint work with Nikolaos Trichakis from HBS )
Pareto Efficiency in Robust Optimizationread_more
HG G 19.2
8 April 2013
16:30-18:00 		Prof. Dr. Gianpaolo Oriolo
Università di Roma "Tor Vergata", Roma, Italy
Event Details

Optimization Seminar

Title When Fourier-Motzkin meets shortest paths (on the way to clique covers in claw-free perfect graphs).
Speaker, Affiliation Prof. Dr. Gianpaolo Oriolo, Università di Roma "Tor Vergata", Roma, Italy
Date, Time 8 April 2013, 16:30-18:00
Location HG G 19.1
Abstract We consider polyhedra (systems) of the form Ax\leq b with A a {0,1,-1} matrix, with at most two non-zero element per row, and b integer. We are interested in testing the existence of integer solutions to such a system. This question was elegantly answered using neat polyhedral arguments by Schrijver in 1994. We give an alternative approach to this question combining pure combinatorial arguments (using techniques from 2-SAT and shortest paths) with polyhedral ones. Our approach is inspired by an algorithm from the Constraint Logic Programming community and we give as a side benefit a formal proof that the corresponding algorithm is correct (apparently answering an open question in this community). Interestingly, the systems we study have properties closely connected with the so-called Edmonds-Johnson property, and we study some interesting related questions. Building upon these results, we give new algorithms for the minimum weighted clique cover in a claw-free perfect graph G, improving the complexity from O(|V(G)|^5) to O(|V(G)|^3). Additionally, we present a simple and neat augmenting path algorithm for the unweighted case. (Joint work with Flavia Bonomo, Claudia Snels and Gautier Stauffer)
When Fourier-Motzkin meets shortest paths (on the way to clique covers in claw-free perfect graphs).read_more
HG G 19.1
29 April 2013
16:30-18:00 		Prof. Dr. Oliver Stein
Karlsruher Institut für Technologie, Karlsruhe
Event Details

Optimization Seminar

Title On Differentiability Properties of Nash Equilibrium Problems
Speaker, Affiliation Prof. Dr. Oliver Stein, Karlsruher Institut für Technologie, Karlsruhe
Date, Time 29 April 2013, 16:30-18:00
Location HG G 19.1
Abstract Any smooth generalized Nash equilibrium problem allows a reformulation as a single constrained minimization problem with possibly nonsmooth objective function. Under the assumption of player convexity, we study smoothness properties of this objective function and, by using several results from parametric optimization, we show that, except for special cases, all locally minimal points of the reformulation are differentiability points. This justifies a numerical approach which basically ignores the possible nondifferentiabilities. This is joint work with Nadja Harms and Christian Kanzow, University of Würzburg.
On Differentiability Properties of Nash Equilibrium Problemsread_more
HG G 19.1
6 May 2013
16:30-18:00 		Prof. Dr. Franz Rendl
Alpen-Adria-Universität Klagenfurt
Event Details

Optimization Seminar

Title A hierarchy of relaxations for Max-Cut and related problems based on small exact subproblems
Speaker, Affiliation Prof. Dr. Franz Rendl, Alpen-Adria-Universität Klagenfurt
Date, Time 6 May 2013, 16:30-18:00
Location HG G 19.1
Abstract The basic semidefinite relaxation for Max-Cut, underlying the Goemans-Williamson hyperplane rounding procedure, allows various tightenings. The simplest one includes constraints from the metric polytope. More refined approaches are iterative, and provide a sequence of relaxations, which come arbitrarily close to the convex hull of cut matrices, but at an increasingly high computational effort. A natural systematic hierarchy was introduced by Lasserre. The first step in this hierarchy corresponds to the basic semidefinite relaxation, where the optimization is done over the set of correlation matrices. The second one is a relaxation in the space of matrices of order $O(n^{2})$. We propose an iterative refinement of the basic semidefinite relaxation intersected with the metric polytope. The refinement is obtained by asking that submatrices to certain carefully selected small node-induced subgraphs of the problem are actually contained in the the cut-polytope of the subgraph. The matrix order in the refinement process is always $n$, and only the number of constraints may grow exponentially. A similar approach has been used in the context of linear relaxations under the heading of 'target cuts'. We will discuss the connections and differences of the present approach to previous methods, and also consider applications to stable-set relaxations. We provide some theoretical insights as well as first computational experience. (joint work with Elsbeth Adams and Miguel Anjos (Montreal) and Angelika Wiegele (Klagenfurt))
A hierarchy of relaxations for Max-Cut and related problems based on small exact subproblemsread_more
HG G 19.1
13 May 2013
16:30-18:00 		Prof. Dr. Vladimir Veliov
Technische Universität Wien, Wien, Oesterreich
Event Details

Optimization Seminar

Title Metric regularity, stability and approximations in optimal control
Speaker, Affiliation Prof. Dr. Vladimir Veliov, Technische Universität Wien, Wien, Oesterreich
Date, Time 13 May 2013, 16:30-18:00
Location HG G 19.1
Abstract The talk will consist of the following parts. 1. An informal introduction. General problems that have led to the concept of metric regularity will be briefly discussed. 2. Some basic definitions and theory. Elements of the theory of metric regularity that are relevant to the rest of the talk will be briefly introduced. A version of the main operational tool--a Lyusternik-Graves-type theorem--will be formulated. Then two extensions will be presented: bi-metric regularity and Hölder metric regularity. 3. Metric regularity of optimal control problems. In this part the metric regularity will be translated in the terms of optimal control problems. Error estimates for discretization schemes will be presented as an illustration. 4. Stability and bi-metric Hölder regularity of bang-bang optimal control problems. Although the theory of linear optimal control problems was developed some half a century ago, the ``stability" and the error analyses of discretization schemes for such problems are subjects of recent research. Some new results in this area that involve the material from part 3 will be presented. 5. Metric regularity and approximations of infinite-horizon optimal control problems. The approximation of infinite-horizon optimal control problems that arise in economics is an open and rather challenging issue. Thanks to some recently obtained optimality conditions for such problems it become possible to apply the metric regularity theory and obtain conditions for approximation and stability analysis of infinite-horizon problems. Such will be presented in the final part of the talk.
Metric regularity, stability and approximations in optimal controlread_more
HG G 19.1
27 May 2013
16:30-18:00 		Prof. Dr. Laurence Wolsey
Catholic University of Louvain, Belgien
Event Details

Optimization Seminar

Title On the Facets of Continuous Knapsack Constraints
Speaker, Affiliation Prof. Dr. Laurence Wolsey, Catholic University of Louvain, Belgien
Date, Time 27 May 2013, 16:30-18:00
Location HG G 19.1
Abstract Given a single constraint mixed integer program with n integer variables and m continuous variables with bounds, our aim is to understand when all the nontrivial facets of the convex hull of solutions have 0-1 coefficients on the continuous variables. The special case with n=1 is the single arc set studied by Magnanti et al., and the case with n=2 and one unbounded continuous variable is treated by Agra and Constantino. We show that the number of distinct non-zero coefficients for the continuous variables is bounded above by 2n − n and that for n = 2 the bound is exactly one. Our main result is to show that when n = 2 the property holds and we provide a complete description of the convex hull. We also show that similar results hold for all m and n when the coefficients of the integer variables are divisible. This is joint work with Oktay Gunluk and Sanjeeb Dash, and Hande Yaman.
On the Facets of Continuous Knapsack Constraintsread_more
HG G 19.1

Note: if you want you can subscribe to the iCal/ics Calender.

Organizers: Komei Fukuda, Bernd Gärtner, Diethard Klatte, John Lygeros, Manfred Morari, Karl Schmedders, Robert Weismantel

Archive: SS 22 SS 20 AS 19 SS 19 AS 18 SS 18 AS 17 SS 17 AS 16 SS 16 AS 15 SS 15 AS 14 SS 14 AS 13 SS 13 AS 12 SS 12 AS 11 SS 11 AS 10 SS 10 AS 09

JavaScript has been disabled in your browser