How does it work? For the set of real numbers R and some positive integer n, the problem starts with a set F that is the intersection of finitely many closed h

How does it work? For the set of real numbers R and some positive integer n, the problem starts with a set F that is the intersection of finitely many closed half spaces in R^n. Each such half space is from a constraint that is a linear inequality with relation either >= or <=. Then the set F is a closed, convex subset of R^n. Set F is called the feasible region. In addition, are given a linear function z: R^n --> R, the objective function. Then the problem is to find a point x in F that makes z(x) as large as possible. Such point x in R^n is said to be optimal. Even if optimal point x exists, it may not be unique. Indeed, if there is more than one optimal solution, then there are infinitely many, and the set of all optimal solutions forms a closed, convex subset of feasible region F. If set F is empty, then the problem is infeasible and there is no optimal solution. Else set F is non-empty and the problem is feasible. Any point in set F is said to be a feasible point. If the problem is feasible, then it may be that function z is unbounded above on F. Then the problem is unbounded and there is no optimal solution. If the problem is feasible and not unbounded, then it is feasible and bounded. It is a theorem, not trivial to prove, that if the problem feasible and bounded, then it has an optimal solution. Given points x, y in R^n and real number t in the interval [0,1], the point w = tx + (1-t)y is a convex combination of the points x and y. Easily the set of all convex combinations of points x and y is closed and convex. Suppose C is a convex subset of R^n, x is in C, and x is not a convex combination of two other points in C. Then point x is an extreme point of convex set C. It is a theorem that if the linear program has an optimal solution, then it has at least one optimal solution that is an extreme point of the feasible region F. So, in looking for optimal solutions, it is sufficient to look only at extreme points of the feasible region F. It is a theorem that the feasible region F has only finitely many extreme points. The classic algorithm for finding optimal solutions is the Dantzig simplex algorithm. Intuitively and geometrically the algorithm starts at an extreme point of the feasible region and moves, one iteration at a time, to adjacent extreme points (and adjusts what it regards as the basic variables) until it satisfies a sufficient condition for optimality. With appropriate refinement of the simplex algorithm, it is always able to achieve this sufficient condition. Algebraically, the simplex algorithm is a small but clever modification of Gauss elimination for solution of systems of linear equations. Each iteration of the algorithm corresponds to some elementary row operations on the system of linear equations. There are more technical details, but the above is a good outline and overview of the core math. Some of the consequences of the linear programming and some of the properties of the simplex algorithm yield a nice collection of inequalities, theorems of the alternative, the saddle point theorem and optimal strategies of two person game theory, etc. E.g., in the game paper, scissors, and rock, play each of the tree moves with probability 1/3rd and independent of all the past. Then in the long run will break even. Is the simplex algorithm a polynomial algorithm? Apparently not: There is a classic example problem of Klee and Minty that shows that at least one version of the algorithm is exponential. In practice, however, the simplex algorithm runs in time linear in the number of half spaces. There are more details in some now classic work of K. Borgward. Is there a polynomial algorithm for linear programming? Yes. In practice, the simplex algorithm has many refinements and extensions. If we ask that the components of an optimal solution x be integers, then the problem is integer linear programming and is in NP-complete. One solution approach is via branch and bound where we solve an ordinary linear program at each node of a large tree. But that approach is not a bad as it might sound since usually one more solution is just a little work from what was left over from the last solution -- the simplex algorithm has lots of such modifications. Another problem is least cost flows on a directed graph (network) with on each arc a maximum flow and a cost per unit of flow. There the simplex algorithm takes on a special form that commonly permits astoundingly fast solutions of astoundingly large problems. Moreover, if the arc capacities are all integers, then, starting with an integer feasible solution, the simplex algorithm maintains integer solutions and will find an optimal integer solution -- we get integer programming for no extra effort. We can also use linear programming as a tool in solving convex problems, nonlinear problems, make use of Lagrange multipliers, achieve the Kuhn-Tucker necessary conditions, etc. Some of the promise of linear programming is from how common are linear expressions, especially in business, accounting, budgeting, business planning, etc. Dantzig worked out his simplex algorithm in the late 1940s at Rand Corporation working on the logistic problem of the USAF of how best to deploy a military force rapidly to a distant location. An early commercial success was feed mixing for livestock: Given a list of feeds and the nutritional content and prices of each and given what total nutritional content want for the livestock, find how much of each feed to buy to feed the livestock at least cost. There are rumors that Ralston Purina runs linear programs daily when mixing feeds. Another problem of early high interest was how to ship from some factories to some warehouses to get each warehouse what they needed, take from each factory only what they had, and minimize total shipping cost. Well, now we know that this is a special case of the least cost flow problem that we can do so well solving. An early statement of this problem, the transhipment problem, resulted in a Nobel prize in economics. Another early success was operating an oil refinery: So, given crude oil supplies, which differ in chemistry and price, and refinery products, which differ in price, find what crude oil supplies to use and what products to make to maximize profit. Apparently eventually this problem was refined to make use of nonlinear programming, e.g., by C. Floudas. One use of linear programming is for scheduling. E.g., consider the original FedEx: Given 90 US cities with loads to be picked up and loads in Memphis to be delivered. Given 33 airplanes, say, all Dassault DA-20 Fanjet Falcons. Now, way which airplanes go to which cities in what order to move all the loads, obey all safety and engineering constraints, arrive within specified time windows at each of the airports, and minimize direct operating costs. So, it looks like a huge, non-linear, integer problem. But, can attack the problem in two steps where the first is just some enumeration likely doable with some nonlinear arithmetic and the second is just some 0-1 integer linear programming which likely has an okay chance of good results. So, the first step is just to get a list of what a single airplane might do, that is, what cities it might visit and in what order. So, just write the code: Try all the reasonable sets of cities in reasonable order (e.g., don't waste time on evaluating absurd cases like having one plane serve NYC, Seattle, Miami, Chicago, and LA, in that order). Then for each reasonable candidate for what one plane might do, do the nonlinear arithmetic to find the costs. For a given set of cities served, keep only the one order of the cities that minimizes the costs. The result will be a list of some 100,000 or so cases for what one plane might do, the cost of the case, and the cities served (right, cheat a little -- argue that if an plane stops at a city, then it delivers everything the city gets and picks up everything the city has to ship, etc.). So, with 90 cities and 100,000 cases set up a linear program with 100,000 variables and 90 constraints. That is, for each of the 90 cities, want some one of the 100,000 cases to serve that city. So, each of the 100,000 columns has just 0s and 1s, a 0 if that case does not serve that city and a 1 if it does. This is an old approach and is called 0-1 integer linear programming set covering. Yes, likely it is in NP-complete. But there is a also a good chance that save 5, 10, maybe 15% of direct operating costs over other approaches. Can do a lot of scheduling problems with such approaches. For linear programming software, can consider, say, R. Bixby and his work Gurobi. At times I have had good success with the old IBM Optimization Subroutine Library (OSL). E.g., once with some Lagrangian relaxation, I got a feasible solution within 0.025% of optimality to a 0-1 integer linear programming problem with 40,000 constraints and 600,000 variables in 905 seconds on a 90 MHz PC!