Other Topics

Optimization problems with equilibrium constraints and their numerical solution

  • Michal Kočvara
  • Jiri V. Outrata
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization, Other Topics Tags

    We consider a class of optimization problems with a generalized equation among the constraints. This class covers several problem types like MPEC (Mathematical Programs with Equilibrium Constraints) and MPCC (Mathematical Programs with Complementarity Constraints). We briefly review techniques used for numerical solution of these problems: penalty methods, nonlinear programming (NLP) techniques and Implicit Programming approach … Read more

    A Class of Hybrid Methods for Revenue Management

  • William Cooper
  • Tito Homem-de-Mello
    • Categories Dynamic Programming, Stochastic Programming, Yield Management

    We consider a Markov decision process model of a network revenue management problem. Working within this formal framework, we study policies that combine aspects of mathematical programming approaches and pure Markov decision process methods. The policies employ heuristics early in the booking horizon, and switch to a more-detailed decision rule closer to the time of … Read more

    Computing All Nonsingular Solutions of Cyclic-n Polynomial Using Polyhedral Homotopy Continuation Methods

  • Yang Dai
  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Other Topics Tags , , , ,

    All isolated solutions of the cyclic-n polynomial equations are not known for larger dimensions than 11. We exploit two types of symmetric structures in the cyclic-n polynomial to compute all isolated nonsingular solutions of the equations efficiently by the polyhedral homotopy continuation method and to verify the correctness of the generated approximate solutions. Numerical results … Read more

    Solving Stability Problems on a Superclass of Interval Graphs

  • Carlo Mannino
  • Gianpaolo Oriolo
    • Categories Dynamic Programming, Graphs and Matroids, Telecommunications Tags , , ,

    We introduce a graph invariant, called thinness, and show that a maximum weighted stable set on a graph $G(V, E)$ with thinness $k$ may be found in $O(\frac{|V|}{k})^k$-time, if a certain representation is given. We show that a graph has thinness 1 if and only if it is an interval graph, while a graph with … Read more

    Optimality Conditions for Vector Optimization with Set-Valued Maps

  • Yongwei Huang
    • Categories Generalized Convexity/Monoticity, Multi-Criteria Optimization, Nonlinear Optimization Tags , , , , ,

    Based on near convexity, we introduce the concepts of nearly convexlike set-valued maps and nearly semiconvexlike set-valued maps, give some charaterizations of them, and investigate the relationships between them. Then a Farkas-Minkowski type alternative theorem is shown under the assumption of near semiconvexlikeness. By using the alternative theorem and some other lemmas, we establish necessary … Read more

    Constructing Approximations to the Efficient Set of Convex Quadratic Multiobjective Problems

  • Jörg Fliege
  • Andree Heseler
    • Categories Multi-Criteria Optimization, Quadratic Programming Tags , ,

    In multicriteria optimization, several objective functions have to be minimized simultaneously. For this kind of problem, no single solution can adequately represent the whole set of optimal points. We propose a new efficient method for approximating the solution set of a convex quadratic multiobjective programming problem. The method is based on a warm-start interior point … Read more

    An explicit equivalent positive semidefinite program for nonlinear 0-1 programs

  • Jean-Bernard Lasserre
    • Categories 0-1 Programming, Other Topics, Semi-definite Programming

    We consider the general nonlinear optimization problem in 0-1 variables and provide an explicit equivalent positive semidefinite program in $2^n-1$ variables. The optimal values of both problems are identical. From every optimal solution of the former one easily find an optimal solution of the latter and conversely, from every solution of the latter one may … Read more

    Dynamic Weighted Aggregation for Evolutionary Multiobjective Optimization

  • Yaochu Jin
    • Categories Multi-Criteria Optimization, Multidisciplinary Design Optimization Tags , , ,

    Weighted sum based approaches to multiobjective optimization is computationally very efficient. However,they have two main weakness: 1) Only one Pareto solution can be obtained in one run 2) The solutions in the concave part of the Pareto front cannot be obtained. This paper proposes a new theory on multiobjective optimization using weighted aggregation approach. Based … Read more

    Near-optimal solutions to large scale facility location problems

  • Francisco Barahona
  • Fabian Chudak
    • Categories Applications - Science and Engineering, Approximation Algorithms, Other Topics Tags , ,

    We investigate the solution of large scale instances of the capacitated and uncapacitated facility location problems. Let n be the number of customers and m the number of potential facility sites. For the uncapacitated case we solved instances of size m x n=3000 x 3000; for the capacitated case the largest instances were 1000 x … Read more

    Generalized Goal Programming: Polynomial Methods and Applications

  • Emilio Carrizosa
  • Jörg Fliege
    • Categories Applications - OR and Management Sciences, Convex Optimization, Multi-Criteria Optimization Tags , , , ,

    In this paper we address a general Goal Programming problem with linear objectives, convex constraints, and an arbitrary componentwise nondecreasing norm to aggregate deviations with respect to targets. In particular, classical Linear Goal Programming problems, as well as several models in Location and Regression Analysis are modeled within this framework. In spite of its generality, … Read more