Linear programming is the problem of deciding whether there exists a
solution to a system of linear ineqalities. Alot of work was gone into
this problem, resulting in the classical SIMPLEX algorithm (which is
exponential in the worst case), and the Ellipsoid method. The SIMPlEX
algorithm is exponential in the worstcase, and the Ellipsoid algorithm
is weakly polynomial. Coming up with a strongly-polynomial time
algorithm for the linear programming problem is one of the major open
problems in computer science.
However, if the number of variables in the system of inequalities is
small (2, 3, or even a small constant) better methods are known. In
this applet we demonstrate Megiddo algorithm
(independently discovered by Dyer) for the planar case. Here, each
inequlity:
ai x + bi y <= ci
corresponds to half of the plane (because, ai x +
bi y = ci is a line, and all the points that lie to one side of this line fulfill this inequality).
We know that there is a solution if the intersection of the all those
regions is not empty (i.e. the feasible region). In fact, usually we
also wish to find a solution that minimizes (or maximizes) a linear
function (i.e. objective function).
First, we apply a linear transformation to the points of the
plane, so that the objective function becomes equal to the negative y-axis.
This reduces the problem
to finding the lowest point in the region defined by the
constraints.
Description of the algorithm
The intuition behind the algorithm is the following: there are only
half-planes that define the solution (i.e. their intersection
point). If we can throw away, repeatedly, a large chunk of the
inequlities because we know that they do not participate in the
soltion, than by the end of this shrinking process we will be left by
a small number of constraints (that we know that they define the
optimal solution). Now, we will compute the solution from this subset
of the inequalities.
Pseudocode the algorithm
Rotate the coordinate system, so that the objective function
becomes the negative y-axis
Partition the half planes (i.e. constraints) into three groups,
depending upon whether the "allowed" half-plane defined by the
constraint lies:
Above the line defining the constraint (the contraint is a
"floor" of the feasible region)
Below the line defining the constraint (a "ceiling" of the
feasible region)
Left or right of the line - the line is vertical.
If there are at most one "floor" constraint left, then decide,
where is the optimum - the lowest point (if it exists) in
constant time and go to stage 7
Partition the "floors" and "ceilings" into the pairs (in an
arbitrary manner). If the lines in a pair are parallel or their
intersection point is not between the left and right bounds,
determined by the vertical constraints, then remove one of them
(because one of them does not participate in definining the
solution).
Find the median of those
intersection points (median in the x coordinate of the
points), and decide where is the
optimum point relative to the median. If it has the same x
coordinate, then go to stage 7
For each pair, with intersection point on opposite side of the
optimum (relative to the median), remove one of the half planes
(one of them does not participate in the defining the solution)
and go to the stage 3
Rotate the coordinates back and report the solution
Running Time
If at the beginning of stage 4 there are M constraints in the
"floors" and "ceilings", then at the stage 6 at least
M/4 constraints are removed (for example we thrown one
half-plane from all the intersection points to the right of the
median). There are M/2 intersections, we thus removed a
constraint from M/4 pairs. Thus, we removed M/8
constraints. Overall, this required O(M) time. Repeating this process
will require:
O(M + 7/8M + (7/8)2M + ... ) = O(M)
time. This follows because finding the median can be done in linear time. Thus, the
overall running time of the algorithm is O(M).
The algorithm is describedi n detain in:
Franco P. Preparata, Michael Ian Shamos , "Computational geometry"
(Second printing), Springer-Verlag, 1985.Back to the Workshop home page