Month: September 2017

A sequential optimality condition related to the quasinormality constraint qualification and its algorithmic consequences

  • Roberto Andreani
  • N. S. Fazzio
  • María Laura Schuverdt
  • Leonardo D. Secchin
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In the present paper, we prove that the augmented Lagrangian method converges to KKT points under the quasinormality constraint qualification, which is associated with the external penalty theory. For this purpose, a new sequential optimality condition for smooth constrained optimization, called PAKKT, is defined. The new condition takes into account the sign of the dual … Read more

    Shaping and Trimming Branch-and-bound Trees

  • Philipp M. Christophel
  • Imre Pólik
    • Categories (Mixed) Integer Linear Programming, Optimization Software Design Principles Tags ,

    We present a new branch-and-bound type search method for mixed integer linear optimization problems based on the concept of offshoots (introduced in this paper). While similar to a classic branch-and-bound method, it allows for changing the order of the variables in a dive (shaping) and removing unnecessary branching variables from a dive (trimming). The regular … Read more

    Dynamic Relaxations for Online Bipartite Matching

  • Alejandro Toriello
  • Alfredo Torrico
    • Categories Dynamic Programming Tags , , ,

    Online bipartite matching (OBM) is a fundamental model underpinning many important applications, including search engine advertisement, website banner and pop-up ads, and ride-hailing. We study the i.i.d. OBM problem, where one side of the bipartition is fixed and known in advance, while nodes from the other side appear sequentially as i.i.d. realizations of an underlying … Read more

    Planar Maximum Coverage Location Problem with Partial Coverage and General Spatial Representation of Demand and Service Zones

  • Manish Bansal
    • Categories Approximation Algorithms, Nonlinear Optimization, Production and Logistics

    We introduce a new generalization of the classical planar maximum coverage location problem (PMCLP) in which demand zones and service zone of each facility are represented by spatial objects such as circles, polygons, etc., and are allowed to be located anywhere in a continuous plane. In addition, we allow partial coverage in its true sense, … Read more

    Exploiting sparsity for the min k-partition problem

  • Hassan L. Hijazi
  • Guanglei Wang
    • Categories 0-1 Programming, Semi-definite Programming Tags , , ,

    The minimum k-partition problem is a challenging combinatorial problem with a diverse set of applications ranging from telecommunications to sports scheduling. It generalizes the max-cut problem and has been extensively studied since the late sixties. Strong integer formulations proposed in the literature suffer from a prohibitive number of valid inequalities and integer variables. In this … Read more