Integer Programming

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

    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

    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

    Enhancing large neighbourhood search heuristics for Benders’ decomposition

  • Stephen J. Maher
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , ,

    A general enhancement of the Benders’ decomposition (BD) algorithm can be achieved through the improved use of large neighbourhood search heuristics within mixed-integer programming solvers. While mixed-integer programming solvers are endowed with an array of large neighbourhood search heuristics, few, if any, have been designed for BD. Further, typically the use of large neighbourhood search … Read more

    A Column and Constraint Algorithm for the Dynamic Knapsack Problem with Stochastic Item Sizes

  • Daniel Blado
  • Alejandro Toriello
    • Categories Dynamic Programming, Integer 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 choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more