4. Some General Methods to Solve Inverse Linear Programming Problem Under Weighted \(l_1\) Norm

In this chapter, we study the inverse (bounded) linear programming problem under weighted \(l_1\) norm (I(B)LP). Given a feasible solution \(x^0\) of the standard (LP) problem \(\min \{c^T x|Ax=b, x\geq 0\}\), the objective is to modify the cost vector c to \(\tilde {c}\) such that \(x^0\) becomes an optimal solution of the modified (LP) problem, while minimizing \(\|\tilde {c}-c\|\) under weighted \(l_1\) norm. This chapter presents a comprehensive study on tackling inverse optimization problems through the design of general algorithms. For the inverse problem (ILP), a mathematical model of (ILP) in view of extreme vertices is examined, followed by two distinct solution approaches: the column generation method and the revised simplex method. Notably, the column generation method incorporates dual operator updates through complementary slackness conditions and a row generation technique. Subsequently, we delve into the resolution of the inverse bounded problem (IBLP), proposing two primal-dual algorithms grounded in duality theory. These algorithms consider the model (IBLP) from both primal and dual perspectives, with a focus on enhancing the dual-based algorithms’ properties to yield an improved primal-dual algorithm. The generality of these algorithms allows for their application to various concrete combinatorial optimization issues, offering potential for the development of more efficient algorithms to inverse combinatorial optimization challenges.