Year: 2018

Compact Disjunctive Approximations to Nonconvex Quadratically Constrained Programs

  • Hongbo Dong
  • Yunqi Luo
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Theory, Second-Order Cone Programming

    Decades of advances in mixed-integer linear programming (MILP) and recent development in mixed-integer second-order-cone programming (MISOCP) have translated very mildly to progresses in global solving nonconvex mixed-integer quadratically constrained programs (MIQCP). In this paper we propose a new approach, namely Compact Disjunctive Approximation (CDA), to approximate nonconvex MIQCP to arbitrary precision by convex MIQCPs, which … Read more

    Chvatal rank in binary polynomial optimization

  • Alberto Del Pia
  • Silvia Di Gregorio
    • Categories 0-1 Programming, Cutting Plane Approaches, Global Optimization Theory Tags , , , , ,

    Recently, several classes of cutting planes have been introduced for binary polynomial optimization. In this paper, we present the first results connecting the combinatorial structure of these inequalities with their Chvatal rank. We show that almost all known cutting planes have Chvatal rank 1. All these inequalities have an associated hypergraph that is beta-acyclic, thus, … Read more

    A branch and price algorithm for the resource constrained home health care vehicle routing problem

  • Neda Tanoumand
  • Tonguç Ünlüyurt
    • Categories Integer Programming, Linear Programming Tags , , ,

    We consider the vehicle routing problem with resource constraints motivated by a home health care application. We propose a branch and price algorithm to solve the problem. In our problem, we consider different types of patients that require a nurse or a health aid or both. The patients can be serviced by the appropriate vehicles … Read more

    On the complexity of solving feasibility problems

  • Luís Felipe Bueno
  • José Mario Martínez
    • Categories Nonlinear Systems and Least-Squares Tags , , ,

    We consider feasibility problems defined by a set of constraints that exhibit gradient H\”older continuity plus additional constraints defined by the affordability of obtaining approximate minimizers of quadratic models onto the associated feasible set. Each iteration of the method introduced in this paper involves the approximate minimization of a two-norm regularized quadratic subject to the … Read more

    On the extension of the Hager-Zhang conjugate gradient method for vector optimization

  • Max L. N. Gonçalves
  • Leandro Fonseca Prudente
    • Categories Multi-Criteria Optimization

    The extension of the Hager-Zhang (HZ) nonlinear conjugate gradient method for vector optimization is discussed in the present research. In the scalar minimization case, this method generates descent directions whenever, for example, the line search satisfies the standard Wolfe conditions. We first show that, in general, the direct extension of the HZ method for vector … Read more

    Equivariant Perturbation in Gomory and Johnson’s Infinite Group Problem. VII. Inverse semigroup theory, closures, decomposition of perturbations

  • Robert Hildebrand
  • Matthias Köppe
  • Yuan Zhou
    • Categories Cutting Plane Approaches Tags , ,

    In this self-contained paper, we present a theory of the piecewise linear minimal valid functions for the 1-row Gomory-Johnson infinite group problem. The non-extreme minimal valid functions are those that admit effective perturbations. We give a precise description of the space of these perturbations as a direct sum of certain finite- and infinite-dimensional subspaces. The … Read more

    Submodularity and valid inequalities in nonlinear optimization with indicator variables

  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches Tags , , ,

    We propose a new class of valid inequalities for mixed-integer nonlinear optimization problems with indicator variables. The inequalities are obtained by lifting polymatroid inequalities in the space of the 0–1 variables into conic inequalities in the original space of variables. The proposed inequalities are shown to describe the convex hull of the set under study … Read more

    A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis

  • Etienne de Klerk
  • Monique Laurent
    • Categories Constrained Nonlinear Optimization, Global Optimization, Semi-definite Programming

    The generalized problem of moments is a conic linear optimization problem over the convex cone of positive Borel measures with given support. It has a large variety of applications, including global optimization of polynomials and rational functions, options pricing in finance, constructing quadrature schemes for numerical integration, and distributionally robust optimization. A usual solution approach, … Read more

    A Tutorial on Formulating QUBO Models

  • Fred Glover
  • Gary Kochenberger
    • Categories 0-1 Programming, Combinatorial Optimization, Meta Heuristics Tags ,

    The field of Combinatorial Optimization (CO) is one of the most important areas in the general field of optimization, with important applications found in every industry, including both the private and public sectors. It is also one of the most active research areas pursued by the research communities of Operations Research, Computer Science, and Analytics … Read more