Las Vegas Algorithms for Linear Programming Applet

To start the Applet click on "New Problem" below. A new window will pop-up, it may appear behind the current window so you may have to find it.

A screen will appear asking you to input constraints for your linear program. The linear programming problem you create will have 9 constraints and 2 dimensions. The objective is to maximize in the Y direction. After inputing your constraints, select "preprocess" to begin, a new window will pop-up, it may appear behind your current window so you may have to find it.

The applet implements two algorithms, the recursive algorithm and the iterative algorithm. To run one step in the recursive algorithm select the button "recursive". To run one step of the iterative algorithm select the "iterative" button. If the set of constraints that's inputed is infeasible or unbounded, it will say so in a message window, and you'll have to change your constraints. You can do this by selecting the "reset" button below where you inputed your contraints.

The Recursive Algorithm

Due to the fact that you'ld need to input over 36 constraints to run the actual algorithm for 2 dimensions, I've cut some of the constant values of the algorithm down a bit. Here I only ask for n = 9 constraints, and d = 2 dimensions. I don't run the simplex algorithm if n is less than C_d = 9d² = 36. The random set, R, of constraints that's chosen has size 3 and is shown in blue (not size d(n)^1/2 = 6). The simplex algorithm is then executed on the set R union V^*. The set of violators V (shown in red) is then added to V^* (shown in orange) if |V| <= 3 (not 2n^1/2 = 6). The optimal value of R union V^* that was computed by the simplex algorithm is shown as a black dot. If no constraints violate the optimum then you are done and the optimal value has been found. If not select the "recursive" button again to do another iteration of the algorithm.

The Iterative Algorithm

For the same reasons as above the constants in this applet have been cut down as well. Here the random set, R, has size 4, and the weights of the violating constraints are doubled each iteration. Once again the random set chosen is shown in blue, the violators are shown in red. If no violators are found, the simplex algorithm applied to R found the optimal value and you are done. If there are violators there weights are doubled, the output of the weights on the contraints can be viewed in Java Console, and you can select the "iterate" button again and again, until the set R that's chosen defines the optimal value.