Other Topics

Fully Polynomial Time (Sigma,Pi)-Approximation Schemes for Continuous Nonlinear Newsvendor and Continuous Stochastic Dynamic Programs

  • Nir Halman
  • Giacomo Nannicini
    • Categories Approximation Algorithms, Dynamic Programming Tags , , , , ,

    We study the continuous newsvendor problem (i.e. a newsvendor problem concerning goods of a non-discrete nature, such as fresh fruit juice) and a class of stochastic dynamic programs with several application areas, such as inventory control of a continuous good, economics, and supply chain management. The class is characterized by continuous state and action spaces, … Read more

    Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes

  • Daniel Blado
  • Alejandro Toriello
    • Categories Combinatorial Optimization, Dynamic Programming Tags ,

    We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can dynamically choose the next item based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more

    Branch-and-bound for biobjective mixed-integer linear programming

  • Nathan Adelgren
  • Akshay Gupte
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Multi-Criteria Optimization Tags , , , ,

    We present a generic branch-and-bound algorithm for finding all the Pareto solutions of a biobjective mixed-integer linear program. The main contributions are new algorithms for obtaining dual bounds at a node, checking node fathoming, presolve, and duality gap measurement. Our branch-and-bound is predominantly a decision space search method because the branching is performed on the … Read more

    A parametric programming approach to redefine the global configuration of resource constraints of 0-1-Integer Linear Programming problems.

  • Alejandro Crema
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Multi-Criteria Optimization Tags , , , ,

    A mathematical programming approach to deal with the global configuration of resource constraints is presented. A specialized parametric programming algorithm to obtain the pareto set for the biobjective problem that appears to deal with the global configuration for 0-1-Integer Linear Programing problems is presented and implemented. Computational results for Multiconstrained Knapsack problems and Bounded Knapsack … Read more

    A Copositive Approach for Two-Stage Adjustable Robust Optimization with Uncertain Right-Hand Sides

  • Samuel Burer
  • Guanglin Xu
    • Categories Dynamic Programming, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , , , ,

    We study two-stage adjustable robust linear programming in which the right-hand sides are uncertain and belong to a convex, compact uncertainty set. This problem is NP-hard, and the affine policy is a popular, tractable approximation. We prove that under standard and simple conditions, the two-stage problem can be reformulated as a copositive optimization problem, which … Read more

    Optimal Deterministic Algorithm Generation

  • Ioannis G. Kevrekidis
  • Alexander Mitsos
  • Jaromił Najman
    • Categories Applications - Science and Engineering, Global Optimization, Other Topics Tags , ,

    A formulation for the automated generation of algorithms via mathematical programming (optimization) is proposed. The formulation is based on the concept of optimizing within a parameterized family of algorithms, or equivalently a family of functions describing the algorithmic steps. The optimization variables are the parameters – within this family of algorithms- that encode algorithm design: … Read more

    An Effective Dynamic Programming Algorithm for the Minimum-Cost Maximal Knapsack Packing

  • Fabio Furini
  • Ivana Ljubić
  • Markus Sinnl
    • Categories Combinatorial Optimization, Dynamic Programming, Integer Programming

    Given a set of n items with profits and weights and a knapsack capacity C, we study the problem of finding a maximal knapsack packing that minimizes the profit of selected items. We propose for the first time an effective dynamic programming (DP) algorithm which has O(nC) time complexity and O(n+C) space complexity. We demonstrate … Read more

    Optimization with stochastic preferences based on a general class of scalarization functions

  • Nilay Noyan
  • Gabor Rudolf
    • Categories Multi-Criteria Optimization, Stochastic Programming

    It is of crucial importance to develop risk-averse models for multicriteria decision making under uncertainty. A major stream of the related literature studies optimization problems that feature multivariate stochastic benchmarking constraints. These problems typically involve a univariate stochastic preference relation, often based on stochastic dominance or a coherent risk measure such as conditional value-at-risk (CVaR), … Read more

    Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes

  • Isabel Beckenbach
  • Leon Eifler
  • Ambros Gleixner
  • Andreas Grever
  • Jakob Witzig
  • Konstantin Fackeldey
  • Marcus Weber
    • Categories (Mixed) Integer Linear Programming, Chemical Engineering, Optimization of Simulated Systems

    In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to … Read more

    Decomposition of loosely coupled integer programs: A multiobjective perspective

  • Shabbir Ahmed
  • Merve Bodur
  • Natashia Boland
  • George L. Nemhauser
    • Categories Integer Programming, Multi-Criteria Optimization Tags , , ,

    We consider integer programming (IP) problems consisting of (possibly a large number of) subsystems and a small number of coupling constraints that link variables from different subsystems. Such problems are called loosely coupled or nearly decomposable. Motivated by recent developments in multiobjective programming (MOP), we develop a MOP-based decomposition algorithm to solve loosely coupled IPs. … Read more