IOR Preprint 5/2010
O. Stein, P. Steuermann:
The adaptive convexification algorithm for semi-infinite programming with arbitrary index sets
Abstract: A numerical solution method for semi-infinite optimization problems with arbitrary, not necessarily box-shaped, index sets is presented. Following the ideas of C. A. Floudas, O. Stein, The adaptive convexification algorithm: a feasible point method for semi-infinite programming (SIAM Journal on Optimization, Vol. 18, 2007, 1187-1208), convex relaxations of the lower level problem are adaptively constructed and then reformulated as MPCCs and solved. Although the index set is arbitrary, this approximation produces feasible iterates for the original problem. The convex relaxations and needed parameters are constructed with ideas of the alphaBB method of global optimization and interval methods. It is shown that after finitely many steps an epsilon-stationary point of the original semi-infinite problem is reached. A numerical example illustrates the performance of the proposed method.
Keywords:Semi-infinite programming, alphaBB, global optimization, convex optimization, mathematical programming with complementarity constraints, bilevel optimization.
IOR Preprint 4/2010
J. Kalcsics:
The Multi-Facility Median Problem With Pos/Neg Weights on General Graphs
Abstract: In this paper we discuss the multi-facility location problem on networks with positive and negative weights. As the finite dominating set for the single facility problem does not carry over to the multi-facility problem, we derive a new finite dominating set. To solve the problem, we present a straight forward algorithm. Moreover, for the problem with just two new facilities, we show how to obtain a more efficient solution procedure by using planar arrangements. We present computational results to underline the efficiency of the improved algorithm and to test some approximations which are based on a reduced candidate set. In addition, we discuss the problem on trees.
Keywords: Multi-facility Location Problems, Networks, Finite Dominating Sets, Planar Arrangements.
IOR Preprint 3/2010
S. Nickel, F. Saldanha-da-Gama, H.-P. Ziegler:
Stochastic Programming approaches for Risk aware Supply Chain Network Design Problems
Abstract: In this paper, a multi-period supply chain network design problem is addressed. Several aspects of practical relevance are considered such as those related with the financial decisions that must be accounted for by a company managing a supply chain. The decisions to be made comprise the location of the facilities, the flow of commodities and the investments to make in alternative activities to those directly related with the supply chain design. Uncertainty is assumed for demand and interest rates, which is described by a set of scenarios. Therefore, for the entire planning horizon, a tree of scenarios is built. A target is set for the return on investment and the risk of falling below it is measured and accounted for. The service level is also measured and included in the objective function. The problem is formulated as a multi-stage stochastic mixed-integer linear programming problem. The goal is to maximize the total financial benefit. An alternative formulation which is based upon the paths in the scenario tree is also proposed. A methodology for measuring the value of the stochastic solution in this problem is discussed. Computational tests using randomly generated data are presented showing that the stochastic approach is worth considering in these type of problems.
Keywords: Supply Chain Management, Multi-stage Stochastic Programming, Financial Decisions, Risk.
IOR Preprint 2/2010
D. Ralph, O. Stein:
The C-index: a new stability concept for quadratic programs with complementarity constraints
Abstract: We introduce nondegeneracy and the C-index for C-stationary points of a QPCC, that is, for a mathematical program with a quadratic objective function and linear complementarity constraints. The C-index characterizes the qualitative local behaviour of a QPCC around a nondegenerate C-stationary point. The article focusses on the structure of the C-stationary set of QPCCs depending on a real parameter. We show that, for generic QPCC data, the C-index changes exactly at turning points of the C-stationary set, and that it changes exactly by one. To illustrate this concept, we introduce and analyze two homotopy methods for finding C-stationary points. Numerical results illustrate that, for randomly generated test problems, the two homotopy methods very often identify B-stationary points.
Keywords: Mathematical Program with Complementarity Constraints, C-stationarity, C-index, MPEC, MPCC, QPCC, homotopy.
AMS Subject Classification: 90C33, 90C31, 90C20, 90C46.
IOR Preprint 1/2010
O. Mayer:
Topological classification of continuous selections of five linear functions
Abstract: Continuous selections of linear functions play an important role in Morse theory for piecewise C2-functions. In this article the topological properties of continuous selections of linear functions are investigated in detail. These are then utilised to provide a complete classification of all continuous selections of five linear functions. This is done by showing that the first four Betti numbers of a simplicial complex induced by such a function fully determine that function up to topological equivalence. The number of different topological types of continuous selections of linear functions has been only known in the case of four or less selection functions so far. The main result of this article now states that there are exactly 26 different topological types of continuous selections of five linear functions.
Keywords: continuous selection of linear functions, critical point, topological classification, Morse theory, non-smooth optimization.
AMS Subject Classification: 26A27, 90C30.