The Many Guises of Linear Programming

Joydeep Dutta ()
Additional contact information
Joydeep Dutta: Indian Institute of Technology Kanpur

Chapter Chapter 2 in Optimization Essentials, 2024, pp 11-63 from Springer

Abstract: Abstract This is a survey on linear programming. However, this is not a survey of a single approach to linear programming, but rather of two distinct approaches: the simplex method and interior point methods based on the log-barrier technique. These two topics are in fact extremely vast, and a survey such as this can only provide a glimpse of the huge edifice known as linear programming. Our approach here is unconventional since instead of viewing linear programming as a stand-alone subject, we examine it through the lens of convex programming. This allows us additional insights that are not part of the traditional discourse of linear programming. The approach to the simplex method given in this survey is credited to Manfred Padberg. The freshness of his approach is that it is tableau-free and has a non-linear programming flavor of using a rank-one update of a basic feasible matrix if it is not optimal. We also provide a very simple proof of the strong duality theorem for linear programming due to J. E. Martinez-Legaz. In this chapter we have an extensive discussion on the KKT conditions for linear programming problems with detailed proofs. The convex programming approach will be readily apparent in the discussion of the interior point methods. The chapter also contains the author’s personal experience of learning linear programming, beginning with an aversion to the tableau approach and progressing to a profound appreciation for the Padberg and interior point methods.

Date: 2024
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:isochp:978-981-99-5491-9_2

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

DOI: 10.1007/978-981-99-5491-9_2

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().