The Complexity of Maximum Matroid-Greedoid Intersection and Weighted Greedoid Maximization

  • Taneli Mielikäinen
  • Esko Ukkonen
    • Categories Combinatorial Optimization Tags , ,

    The maximum intersection problem for a matroid and a greedoid, given by polynomial-time oracles, is shown $NP$-hard by expressing the satisfiability of boolean formulas in $3$-conjunctive normal form as such an intersection. The corresponding approximation problems are shown $NP$-hard for certain approximation performance bounds. Moreover, some natural parameterized variants of the problem are shown $W[P]$-hard. … Read more

    Batched Bin Packing

  • Gregory Gutin
  • Anders Yeo
  • Tommy Jensen
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    We introduce and study the batched bin packing problem (BBPP), a bin packing problem in which items become available for packing incrementally, one batch at a time. A batched algorithm must pack a batch before the next batch becomes known. A batch may contain several items; the special case when each batch consists of merely … Read more

    A filter-trust-region method for unconstrained optimization

  • Nicholas I. M. Gould
  • Caroline Sainvitu
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags ,

    A new filter-trust-region algorithm for solving unconstrained nonlinear optimization problems is introduced. Based on the filter technique introduced by Fletcher and Leyffer, it extends an existing technique of Gould, Leyffer and Toint (SIAM J. Optim., to appear 2004) for nonlinear equations and nonlinear least-squares to the fully general unconstrained optimization problem. The new algorithm is … Read more

    Portfolio Optimization with Stochastic Dominance Constraints

  • Darinka Dentcheva
  • Andrzej Ruszczyński
    • Categories Convex Optimization, Finance and Economics, Stochastic Programming Tags , , ,

    We consider the problem of constructing a portfolio of finitely many assets whose returns are described by a discrete joint distribution. We propose a new portfolio optimization model involving stochastic dominance constraints on the portfolio return. We develop optimality and duality theory for these models. We construct equivalent optimization models with utility functions. Numerical illustration … Read more

    Optimization of Convex Risk Functions

  • Andrzej Ruszczyński
  • Alexander Shapiro
    • Categories Finance and Economics, Stochastic Programming Tags , , , ,

    We consider optimization problems involving convex risk functions. By employing techniques of convex analysis and optimization theory in vector spaces of measurable functions we develop new representation theorems for risk models, and optimality and duality theory for problems involving risk functions. Citation Preprint Article Download View Optimization of Convex Risk Functions

    Solving nonconvex SDP problems of structural optimization with stability control

  • Michal Kočvara
  • Michael Stingl
    • Categories Constrained Nonlinear Optimization, Mechanical Engineering, Semi-definite Programming Tags , , ,

    The goal of this paper is to formulate and solve structural optimization problems with constraints on the global stability of the structure. The stability constraint is based on the linear buckling phenomenon. We formulate the problem as a nonconvex semidefinite programming problem and introduce an algorithm based on the Augmented Lagrangian method combined with the … Read more

    Efficient neighborhood search for Just-in-Time scheduling problems

  • Yann Hendel
  • Francis Sourd
    • Categories Scheduling Tags , ,

    This paper addresses the one-machine scheduling problem where the objective is to minimize a sum of costs such as earliness-tardiness costs. Since the sequencing problem is NP-hard, local search is very useful for finding good solutions. Unlike scheduling problems with regular cost functions, the scheduling (or timing) problem is not trivial when the sequence is … Read more

    Dynasearch neighborhood for the earliness-tardiness scheduling problem with release dates and setup constraints

  • Francis Sourd
    • Categories Scheduling Tags , ,

    The one-machine scheduling problem with sequence-dependent setup times and costs and earliness-tardiness penalties is addressed. This problem is NP-complete, so that local search approaches are very useful to efficiently find good feasible schedules. In this paper, we present an extension of the dynasearch neighborhood for this problem. Finding the best schedule in this neighborhood is … Read more

    Introduction to Domination Analysis

  • Gregory Gutin
  • Anders Yeo
    • Categories Approximation Algorithms, Combinatorial Optimization Tags ,

    In the recently published book on the Traveling Salesman Problem, half of Chapter 6 is devoted to domination analysis (DA) of heuristics for the Traveling Salesman Problem. Another chapter (in preparation) is a detailed overview of the whole area of DA. Both chapters are of considerable length. The purpose of this paper is to give … Read more