Inverse of the Gomory Corner Relaxation of Integer Programs

  • George Lyu
  • Fatemeh Nosrat
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Other Topics Tags , , Short URL: https://optimization-online.org/?p=27032

    \(\)
    We analyze the inverse of integer programs (IPs) using the Gomory corner relaxation (GCR). We prove the inverse GCR is equivalent to the inverse of a shortest path problem, yielding a polyhedral representation of the GCR inverse-feasible region. We propose a linear program formulation for the inverse GCR under \(L_1\) and \(L_\infty\) norms.The inverse GCR bounds the inverse IP optimal value as tightly as the inverse linear relaxation under mild conditions. We relate the inverse feasible region of IP and the inverse feasible regions of GCRs.

    Article

    Download

    View Inverse of the Gomory Corner Relaxation of Integer Programs