Inverse optimization
Inverse optimization
复制标题
DOI：
10.1287/opre.49.5.771.10607
复制
发表时间：
2001-09-01
影响因子：
2.7
通讯作者：
Orlin, JB
中科院分区：
文献类型：
--
作者：
Ahuja, RK;Orlin, JB
在本文中，我们研究如下定义的逆优化问题。设\(S\)表示一个优化问题\(P\)的可行解集，设\(c\)是一个特定的成本向量，\(x^{(0)}\)是一个给定的可行解。对于成本向量\(c\)，解\(x^{(0)}\)可能是也可能不是\(P\)的最优解。逆优化问题是将成本向量\(c\)扰动为\(d\)，使得\(x^{(0)}\)对于\(d\)是\(P\)的最优解，并且\(\left\lVert d - c\right\rVert_{(p)}\)最小，其中\(\left\lVert d - c\right\rVert_{(p)}\)是某个选定的\(L_p\)范数。在本文中，我们考虑\(L_1\)范数下（其中\(\left\lVert d - c\right\rVert_{(p)}=\sum_{j\in J} \omega_{(j)} \left|d_{(j)} - c_{(j)}\right|\)，\(J\)表示变量\(x_{(j)}\)的指标集，\(\omega_{(j)}\)表示变量\(j\)的权重）以及\(L_{\infty}\)范数下（其中\(\left\lVert d - c\right\rVert_{(p)}=\max_{j\in J} (\omega_{(j)}\left|d_{(j)} - c_{(j)}\right|)\)）的逆线性规划问题。我们证明了以下结果：
(i) 如果问题\(P\)是一个线性规划问题，那么它在\(L_1\)以及\(L_{\infty}\)范数下的逆问题也是一个线性规划问题。
(ii) 如果问题\(P\)是一个最短路径、指派或最小割问题，那么在\(L_1\)范数和单位权重下它的逆问题可以通过求解一个同类问题来解决。对于非单位权重的情况，逆问题可归结为求解一个最小费用流问题。
(iii) 如果问题\(P\)是一个最小费用流问题，那么在\(L_1\)范数和单位权重下它的逆问题可归结为求解一个单位容量最小费用流问题。对于非单位权重的情况，逆问题可归结为求解一个最小费用流问题。
(iv) 如果问题\(P\)是一个最小费用流问题，那么在\(L_{\infty}\)范数和单位权重下它的逆问题可归结为求解一个最小平均圈问题。对于非单位权重的情况，逆问题可归结为求解一个最小费用 - 时间比圈问题。
(v) 如果对于线性成本函数问题\(P\)是多项式可解的，那么在\(L_1\)和\(L_{\infty}\)范数下\(P\)的逆问题也是多项式可解的。
In this paper, we study inverse optimization problems defined as follows. Let S denote the set of feasible solutions of an optimization problem P, let c be a specified cost vector, and x(0) be a given feasible solution. The solution x(0) may or may not be an optimal solution of P with respect to the cost vector c. The inverse optimization problem is to perturb the cost vector c to d so that x(0) is an optimal solution of P with respect to d and parallel tod - c parallel to (p) is minimum, where parallel tod - c parallel to (p) is some selected L-p norm. In this paper, we consider the inverse linear programming problem under L-1 norm (where parallel tod - c parallel to (p) = Sigma (t epsilon integral) omega (integral) \d(integral) - c(integral)\ with J denoting the index set of variables x(j) and w(j) denoting the weight of the variable j) and under L-infinity norm (where parallel tod - c parallel to (p) = max(j epsilonJ) (w(j)\d(j) - c(j)\}). We prove. the following results (i) If the problem P is a linear programming problem, then its inverse problem under the L, as well as L. norm is also a linear programming problem. (ii) If the problem P is a shortest path, assignment or minimum cut problem, then its inverse problem under the L, norm and unit weights can be solved by solving a problem of the same kind. For the nonunit weight case, the inverse problem reduces to solving a minimum cost flow problem. (iii) If the problem P is a minimum cost flow problem, then its inverse problem under the L, norm and unit weights reduces to solving a unit-capacity minimum cost flow problem. For the nonunit weight case, the inverse problem reduces to solving a minimum cost flow problem. (iv) If the problem P is a minimum cost flow problem, then its inverse problem under the L. norm and unit weights reduces to solving a minimum mean cycle problem. For the nonunit weight case, the inverse problem reduces to solving a minimum cost-to-time. ratio cycle problem. (v) If the problem P is polynomially solvable for linear cost functions, then inverse versions of P under the. L-1 and L-infinity norms are also polynomially solvable.