Inverse Combinatorial Optimization Problems
Panos M. Pardalos, University of Florida
Given an optimization problem and a feasible solution to it, the corresponding inverse optimization problem is to find a minimal adjustment of the cost vector under some norm such that the given solution becomes optimum. Inverse
optimization problems have been applied in diverse areas, ranging from geophysical sciences, traffic networks, communication networks, facility location problems, finance, electricity markets, and medical decision-making. It has been studied in various optimization frameworks including linear programming, combinatorial optimization, conic, integer and mixed-integer programming, variational inequalities, and countably infinite linear problems and robust optimization.
In this talk, we mainly concentrate on inverse combinatorial optimization problems (ICOP). We will introduce some classes of ICOP as well as general methods to solve them. Some open problems are proposed. We also discuss some generalized inverse optimization problems.
We introduce inverse optimization problems on spanning trees and mainly concentrate on the inverse max+sum spanning tree problems (IMMST) in which the original problem aims to minimize the sum of a maximum weight and a sum cost of a spanning tree.
Keywords: inverse combinatorial optimization, spanning tree problems