Restricted inverse optimal value problem on linear programming under weighted l1 norm

Abstract

We study the restricted inverse optimal value problem on linear programming under weighted l1 norm (RIOVLP1). Given a linear programming problem LPc : min{cx|Ax = b, x ≥ 0} with a feasible solution x0 and a value K, we aim to adjust the vector c to ¯c such that x0 becomes an optimal solution of the problem LPc¯ whose objective value ¯cx0 equals K. The objective is to minimize the distance ∥c¯− c∥1 = Pn j=1 dj |c¯j − cj | under weighted l1 norm. Firstly, we formulate the problem (RIOVLP1) as a linear programming problem by dual theories. Secondly, we construct a sub-problem (Dz), which has the same form as LPc, of the dual (RIOVLP1) problem corresponding to a given value z. Thirdly, when the coefficient matrix A is unimodular, we design a binary search algorithm to calculate the critical value z∗ corresponding to an optimal solution of the problem (RIOVLP1). Finally, we solve the (RIOV ) problems on Hitchcock and shortest path problem, respectively, in O(TMCF log max{dmax, x0max, n}) time, where we solve a sub-problem (Dz) by minimum cost flow in TMCF time in each iteration. The values dmax, x0max are the maximum values of d and x 0, respectively.