ABSTRACT
This chapter presents the basic theory, the main algorithmic approaches and a few typical signal processing problems that can be modeled through Linear programming (LP) or Mixed integer programming (MIP). LP is the class of optimization problems whose criterion and constraints are linear. Such problems appeared first in economy, for example in activity planning or resource allocation, but are now ubiquitous also in engineering. Although being apparently the simplest type of optimization problem that has no analytic solution, LP has interesting properties and its study has led to significant developments and generalizations for the whole optimization field, both in terms of theory and algorithms. MIP problems also have linear criterion and constraints, but some of their variables are constrained to integer values. Despite their resemblance to LP, they have distinct properties and are solved by dedicated algorithms, using LP as a fundamental tool, but much more complex.
