A Genetic Algorithms Approach for Inverse Shortest Path Length Problems

Inverse Combinatorial Optimization

On a broad analysis, inverse optimization problems can be branched into two classes: inverse solution optimization problems and inverse objective value optimization problems (Hung & Director-Sokol, 2003). Briefly, inverse solution optimization problems require finding an arc costs vector that makes a desired solution optimal. Variations include the minimum cut problem (Zhang & Cai, 1998), inverse maximum flow problem (Yang, Zhang, & Ma, 1997), inverse center location problem (Cai, Yang, & Zhang, 1999), the inverse shortest path problem (ISPP) (Cai & Yang, 1994), among others. Inverse objective value optimization problems require that a solution is found that matches a desired value for the objective function rather than assuming there is a desired optimal solution. This type of problem has been much less explored than inverse solution optimization problems but the reverse center location (Zhang, Yang, & Cai, 1999) and the Inverse Shortest Path Length (ISPL) (Fekete, Hochstättler, Kromberg, & Moll, 1999) are examples, with ISPL probably being the most widely known. Heuberger (2004) presented various methods that had been successfully applied in the past to a set of inverse combinatorial problems on an extended survey. The following subsections further explore the two classes of inverse combinatorial optimization and previous work regarding each one.