</a>Polyhedral theory

Polyhedral Empowerment of Networks through Symmetry: psycho-social implications for organization and global governance (Part #7)

[Parts: First | Prev | Next | Last | All] [Links: To-K | From-K | From-Kx | Refs ]

Polyhedra, linear inequalities and linear programming can be seen as three views of the same concept. Polyhedra represent a geometrical point of view, linear inequalities represent the algebraic point of view, and linear programming the optimization point of view. As noted by Geir Dahl (An Introduction to Convexity, Polyhedral Theory and Combinatorial Optimization. 1997)

Today, optimization problems arise in all sorts of areas; this is the age of optimization as a scientist stated it in a recent talk. Modern society, with advanced technology and competive businesses typically needs to make best possible decisions which e.g. involve the best possible use of resources, maximizing some revenue, minimize production or design costs etc.... The large amount of applications, combined with the development of fast computers, has led to massive innovation in optimization. In fact, today optimization may be divided onto several *elds, e.g. linear programming, nonlinear programming, discrete optimization and stochastic optimization. In this course we are concerned with discrete optimization and linear programming.... Typically these are problems of choosing some "optimal subset" among a class of subsets of a given *nite ground set. Many of the problems come from the network area, where *nding a shortest path between a pair of points in a network is the simplest example.

It is the identification of the closure associated with appropriate "convex polyhedra" that is closely associated with identification of an "optimal subset". Most problems studied in combinatorial optimization involve looking for certain structures in graphs. The simplest symmetrical polyhedra (ocathedron, docdecahedron, etc) may therefore be understood as representing or "containing" the solutions to challenges of optimization in many fields. As Dahl further notes:

Well, polyhedral combinatorics is an area where one studies combinatorial optimization problems using theory and methods from linear programming and polyhedral theory.... Polyhedral theory deals with the feasible sets of linear programming problems, which are called polyhedra. Now, polyhedral theory may be viewed as a part of convex analysis which is the branch of mathematics where one studies convex sets, i.e., sets that contain the line segments between each pair of its points.

[Parts: First | Prev | Next | Last | All] [Links: To-K | From-K | From-Kx | Refs ]