Integer Programming

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

    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

    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 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

    Strong mixed-integer programming formulations for trained neural networks

  • Ross Anderson
  • Joey Huchette
  • Juan Pablo Vielma
  • Will Ma
  • Christian Tjandraatmadja
    • Categories (Mixed) Integer Linear Programming, Statistics Tags , ,

    We present strong mixed-integer programming (MIP) formulations for high-dimensional piecewise linear functions that correspond to trained neural networks. These formulations can be used for a number of important tasks, such as verifying that an image classification network is robust to adversarial inputs, or solving decision problems where the objective function is a machine learning model. … Read more

    Strong Mixed-Integer Formulations for Power System Islanding and Restoration

  • Ignacio Aravena
  • Shmuel Oren
  • Deepak Rajan
  • Georgios Patsakis
    • Categories Branch and Cut Algorithms, Integer Programming, Polyhedra Tags , , , , ,

    The Intentional Controlled Islanding (ICI) and the Black Start Allocation (BSA) are two examples of problems in the power systems literature that have been formulated as Mixed Integer Programs (MIPs). A key consideration in both of these problems is that each island must have at least one energized generator. In this paper, we provide three … Read more

    Pattern-based models and a cooperative parallel metaheuristic for high school timetabling problems

  • Alysson Machado Costa
  • Lana M. R. Santos
  • Maristela O. Santos
  • Landir Saviniec
    • Categories (Mixed) Integer Linear Programming, Parallel Algorithms, Scheduling Tags , , ,

    High school timetabling problems consist in building periodic timetables for class-teacher meetings considering compulsory and non-compulsory requisites. This family of problems has been widely studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the efficient obtention of optimal or near-optimal solutions is still a challenge for many problems of practical size. In … Read more

    A new combinatorial algorithm for separable convex resource allocation with nested bound constraints

  • Qie He
  • Kameng Nip
  • Zeyang Wu
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , , ,

    The separable convex resource allocation problem with nested bound constraints aims to allocate $B$ units of resources to $n$ activities to minimize a separable convex cost function, with lower and upper bounds on the total amount of resources that can be consumed by nested subsets of activities. We develop a new combinatorial algorithm to solve … Read more

    n-step cutset inequalities: facets for multi-module capacitated network design problem

  • Kiavash Kianfar
  • Haochen Luo
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Facility Planning and Design

    Many real-world decision-making problems can be modeled as network design problems, especially on networks with capacity requirements on links. In network design problems, decisions are made on installation of flow transfer capacities on the links and routing of flow from a set of source nodes to a set of sink nodes through the links. Many … Read more