Tu Anh-Nguyen

Infeasibility Certificates from Superadditive Functions for Mixed-Integer Programs

  • Natasha Patnaik
  • Tu Anh-Nguyen
  • Akshay Gupte
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We present a constructive procedure for certifying the infeasibility of a mixed-integer program (MIP) using recursion on a sequence of sets that describe the sets of barely feasible right-hand sides. Each of these sets corresponds to a monotonic superadditive function, and the pointwise limit of this sequence is a functional certificate for MIP infeasibility. Our … Read more

    Representing Integer Program Value Function with Neural Networks

  • Tu Anh-Nguyen
  • Joey Huchette
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Linear Programming, Integer Programming Tags , ,

    We study the value function of an integer program (IP) by characterizing how its optimal value changes as the right-hand side varies. We show that the IP value function can be approximated to any desired degree of accuracy using machine learning (ML) techniques. Since an IP value function is a Chvátal-Gomory (CG) function, we first … Read more