A Globally Convergent Primal-Dual Active-Set Framework for Large-Scale Convex Quadratic Optimization

  • Frank E. Curtis
  • Daniel P. Robinson
  • Zheng Han
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

    We present a primal-dual active-set framework for solving large-scale convex quadratic optimization problems (QPs). In contrast to classical active-set methods, our framework allows for multiple simultaneous changes in the active- set estimate, which often leads to rapid identification of the optimal active-set regardless of the initial estimate. The iterates of our framework are the active-set … Read more

    Deriving robust and globalized robust solutions of uncertain linear programs with general convex uncertainty sets

  • Aharon Ben-Tal
  • Dick den Hertog
  • Bram L. Gorissen
  • Hans Blanc
    • Categories Robust Optimization

    We propose a new way to derive tractable robust counterparts of a linear program by using the theory of Beck and Ben-Tal (2009) on the duality between the robust (“pessimistic”) primal problem and its “optimistic” dual. First, we obtain a new {\it convex} reformulation of the dual problem of a robust linear program, and then … Read more

    Robust combinatorial optimization with variable budgeted uncertainty

  • Michael Poss
    • Categories Robust Optimization

    We introduce a new model for robust combinatorial optimization where the uncertain parameters belong to the image of multifunctions of the problem variables. In particular, we study the variable budgeted uncertainty, an extension of the budgeted uncertainty introduced by Bertsimas and Sim. Variable budgeted uncertainty can provide the same probabilistic guarantee as the budgeted uncertainty … Read more

    Metric regularity of composition set-valued mappings: metric setting and coderivative conditions

  • Marius Durea
  • Van Ngai Huynh
  • Huu Tron Nguyen
  • Radu Strugariu
    • Categories Convex and Nonsmooth Optimization

    The paper concerns a new method to obtain a direct proof of the openness at linear rate/metric regularity of composite set-valued maps on metric spaces by the unification and refinement of several methods developed somehow separately in several works of the authors. In fact, this work is a synthesis and a precise specialization to a … Read more

    Chance-constrained binary packing problems

  • Simge Küçükyavuz
  • James R. Luedtke
  • Yongjia Song
    • Categories Integer Programming, Stochastic Programming Tags ,

    We consider a class of packing problems with uncertain data, which we refer to as the chance-constrained binary packing problem. In this problem, a subset of items is selected that maximizes the total profit so that a generic packing constraint is satisfied with high probability. Interesting special cases of our problem include chance-constrained knapsack and … Read more

    Minimum Concave Cost Flow Over a Grid Network

  • Shabbir Ahmed
  • Qie He
  • George L. Nemhauser
    • Categories Combinatorial Optimization, Network Optimization, Production and Logistics Tags , ,

    The minimum concave cost network flow problem (MCCNFP) is NP-hard, but efficient polynomial-time algorithms exist for some special cases such as the uncapacitated lot-sizing problem and many of its variants. We study the MCCNFP over a grid network with a general nonnegative separable concave cost function. We show that this problem is polynomially solvable when … Read more

    Reducing the Number of Function Evaluations in Mesh Adaptive Direct Search Algorithms

  • Charles Audet
  • Sébastien Le Digabel
  • Christophe Tribes
  • Andrea Ianni
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    The mesh adaptive direct search (MADS) class of algorithms is designed for nonsmooth optimization, where the objective function and constraints are typically computed by launching a time-consuming computer simulation. Each iteration of a MADS algorithm attempts to improve the current best-known solution by launching the simulation at a finite number of trial points. Common implementations … Read more

    On Defining Design Patterns to Generalize and Leverage Automated Constraint Solving

  • Thiago Serra
    • Categories Combinatorial Optimization, Integer Programming, Optimization Software Design Principles Tags , ,

    This position paper reflects on the generalization of adaptive methods for Constraint Programming (CP) solving mechanisms, and suggests the use of application-oriented descriptions as a means to broaden CP adoption in the industry. We regard as an adaptive method any procedure that modifies the behavior of the solving process according to previous experience gathered from … Read more

    Distributionally Robust Multi-Item Newsvendor Problems with Multimodal Demand Distributions

  • Grani A. Hanasusanto
  • Daniel Kuhn
  • Stein W. Wallace
  • Steve Zymler
    • Categories Robust Optimization

    We present a risk-averse multi-dimensional newsvendor model for a class of products whose demands are strongly correlated and subject to fashion trends that are not fully understood at the time when orders are placed. The demand distribution is known to be multimodal in the sense that there are spatially separated clusters of probability mass but … Read more

    On parallelizing dual decomposition in stochastic integer programming

  • Miles Lubin
  • Kipp Martin
  • Burhaneddin Sandikçi
  • Cosmin G. Petra
    • Categories Nonsmooth Optimization, Parallel Algorithms, Stochastic Programming Tags , , , , ,

    For stochastic mixed-integer programs, we revisit the dual decomposition algorithm of Car\o{}e and Schultz from a computational perspective with the aim of its parallelization. We address an important bottleneck of parallel execution by identifying a formulation that permits the parallel solution of the \textit{master} program by using structure-exploiting interior-point solvers. Our results demonstrate the potential … Read more