Some General Methods to Solve Inverse Linear Programming Problem Under Weighted l 1 $$l_1$$ Norm

Xiucui Guan, Panos M. Pardalos and Binwu Zhang
Additional contact information
Xiucui Guan: Southeast University
Binwu Zhang: Hohai University

Chapter Chapter 4 in Inverse Combinatorial Optimization Problems, 2025, pp 101-136 from Springer

Abstract: Abstract In this chapter, we study the inverse (bounded) linear programming problem under weighted l 1 $$l_1$$ norm (I(B)LP). Given a feasible solution x 0 $$x^0$$ of the standard (LP) problem min { c T x | Ax = b , x ≥ 0 } $$\min \{c^T x|Ax=b, x\geq 0\}$$ , the objective is to modify the cost vector c to c ~ $$\tilde {c}$$ such that x 0 $$x^0$$ becomes an optimal solution of the modified (LP) problem, while minimizing ∥ c ~ − c ∥ $$\|\tilde {c}-c\|$$ under weighted l 1 $$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.

Keywords: Inverse linear programming problem; Inverse bounded linear programming problem; Column generation method; Row generation method; Primal-dual method (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-031-91175-0_4

Ordering information: This item can be ordered from
http://www.springer.com/9783031911750

DOI: 10.1007/978-3-031-91175-0_4

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().