Linear Programming Approaches to Optimization Problems of Energy Efficiency in Wireless Ad Hoc Networks

Linear programming/integer linear programming (LP/ILP) is a powerful and remarkably versatile tool that is widely applied in business activities, industry manufacturing, military activities, information techniques, etc. The techniques of linear programming, for the most part, have been developed over the past four to five decades. There are three basic steps in the linear programming model of formulations: (1) determination of the decision variables, (2) formulation of objective, and (3) formulation of the constraints. Network optimization problems are a class of important applications of linear programming. Typically, the min-cut max-flow problem, the shortest path problem, and the minimum cost-flow problem can be formulated as linear programming problems. Furthermore, in addition to the traditional Simplex and Branch and Bound methods, there are some powerful software packages that can be used to compute LP/ILP, such as Mathematic, Matlab, LPSolver, etc.