A general model of some inverse combinatorial optimization problems and its solution method under \(\ell_\infty\) norm (Q1598883)

Given a combinatorial optimization problem \(\min \{ w(F): F \in {\mathcal F} \}\) and a feasible solution \(\overline F\) to it, the associated inverse combinatorial optimization problem asks for a new weighting vector \(\overline w\) such that \(\overline F\) is optimal under \(\overline w\) and the distance between \(w\) and \(\overline w\) is minimized under a suitable norm. A related reverse problem asks to adjust in the most economic way suitable parameters (e.g. capacities) in order to achieve a given target value for the optimal solution or not exceed a given budget. This paper proposes an optimization model which generalizes several inverse and reverse problems, focalizing on the \(L_1\) and \(L_{\infty}\) norms. For the \(L_{\infty}\) norm a Newton-type algorithm is described which solves the model in a strongly polynomial number of iterations, each one of them requiring the solution of a related subproblem for a fixed value of a scalar parameter. The paper discusses several inverse optimization problems that can be solved in strongly polynomial time by the proposed procedure.