Theorem of Alternative

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

    On strong duality, theorems of the alternative, and projections in conic optimization

  • Temitayo Ajayi
  • Akshay Gupte
  • Amin Khademi
  • Andrew J. Schaefer
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    A conic program is the problem of optimizing a linear function over a closed convex cone intersected with an affine preimage of another cone. We analyse three constraint qualifications, namely a Closedness CQ, Slater CQ, and Boundedness CQ (also called Clark- Duffin theorem), that are sufficient for achieving strong duality and show that the first … Read more