The algorithm ends with a (s,t)-cut, which indicates the optimality of the solution. Revision: allow a path to cancel an existing flow. This solution does not always work - see example. The simplex algorithm applied to the maximum-flow problem: start with zero flow, then repeatedly look for an appropriate path from s to t, and increase the flow along the path as much as possible. Maximum flow problem is reduced to LP problem. A flow in the network, from a source s to a sink t, satisfies two constraints: on each edge and each vertex. The Simplex algorithm solves a LP problem by repeatedly moving to a better vertex.Ī directed and weighted graph can be seen as a network with edge capability specified. Reduction and LP Reduction: to transform a problem into another problem.

The feasible region is unbounded, i.e., the objective function can go to infinite.Ģ.The linear program is infeasible, i.e., the constraints are contradictory.In the following situations there is no optimal solution: The optimal solution is the one that maximizes or minimizes a given linear objective function, which is achieved at a vertex of the feasible region.Įxample: profit maximization, Figure 7.1. The points in the common sub-region of all the constraints are feasible solutions of the LP problem. Intuitively, each of them correspond to a region in the space, consisting of the points satisfying the constraint. Intuitively, it corresponds to a multi-dimensional space, and each assignment to the variables corresponds to a point in the space.Ī constraint is expressed as a (linear) equation or inequality. The problem domain is described by a set of variables. Linear programming: Optimization with linear constraints and criterion. Optimization: find a solution with the largest or smallest value by some criterion under certain constraints.

Unbounded solution space