We analyze the inverse of the Gomory corner relaxation (GCR) of a pure integer program (IP). 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 present a linear programming (LP) formulation for solving the inverse GCR under the \(L_{1}\) … Read more
Finding the shortest path in a directed graph is one of the most important combinatorial optimization problems, having applications in a wide range of fields. In its basic version, however, the problem fails to represent situations in which the value of the objective function is determined not only by the choice of each single arc, … Read more
In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (agents/players) move together along the edges of a graph from a given starting vertex to a given destination. The two players take turns in deciding in each vertex which edge to traverse next. The decider in … Read more
Motivated by telecommunication applications, we investigate the shortest path problem on directed acyclic graphs under arc length uncertainties represented as interval numbers. Using a minimax-regret criterion we define and identify robust paths via mixed-integer programming and exploiting interesting structural properties of the problem. CitationBilkent University, Department of Industrial Engineering, Technical Report August 2001ArticleDownload View PDF