wn_simplex_method, wn_simplex_loop - simplex method package

#include <wn/wnmat.h>

wn_simplex_method(&code, &objective, shadow_prices, solution,
int code;
double objective;
double *shadow_prices, *solution, *objective_vect;
double **mat;
double *right_side;
int len_i, len_j;

wn_simplex_loop(&code, mat, right_side, right_side_control,
int code;
double **mat;
double *right_side, *right_side_control;
int *non_zero_vars, *zero_vars;
int len_i, len_j;

This package solves the "linear programming" problem easily and efficiently. The "linear programming" problem is the following optimization problem:

CHOOSE solution[j] TO MAXIMIZE

sum_over(j){ objective_vect[j]*solution[j] }

WHILE SATISFYING THE CONSTRAINTS

for_all(i){ sum_over(j){mat[i][j]*solution[j]} == right_side[i] }

AND

for_all(j){ solution[j] >= 0 }

Difficult optimization problems from many fields can be put into this form, and thus solved efficiently with this package.

Set objective to NULL if you want any feasible solution; set shadow_prices to NULL if you don't care about shadow prices.

For an introduction to the linear programming problem, consult [1] and [2]. The basis of the algorithm used here is the "revised simplex method" given in [3]. However, the algorithm used has these improvements:

1) It is randomized to avoid various degeneracy problems.

2) The pivot element is selected for numerical stability

3) A perturbed right side is provided as an anti-cycling measure.

Naive users should confine themselves to wn_simplex_method.

wn_simplex_loop makes available to sophisticated users the (improved) simplex loop given in [3] in raw form. The 0'th row is the objective row. right_side[0] contains minus the objective after completion of the algorithm. right_side_control should be an array with len_i entries, initialized to the values in right_side plus a small random perturbation. The perturbation is necessary to prevent cycling. wn_simplex_loop uses right_side_control to control the basis; right_side is carried along with it to give the exact answer.

Solving the simplex problem using wn_simplex_method requires

AVERAGE CASE:

time = len_i^2 * len_j

stack memory = 1

dynamic memory = len_i*len_j

Randomizing is used to avoid exponential worst-case performance.

wn_simplex_loop requires

AVERAGE CASE:

time = len_i * len_j

stack memory = 1

dynamic memory = 0

for each iteration. Usually no more than order len_i iterations are required for an optimal solution.

code == WN_SUCCESS for successful solution.

code == WN_UNBOUNDED for unbounded solution.

code == WN_INFEASIBLE if no solution satisfies the constraints.

WN_INFEASIBLE also given if mat is degenerate, even if solutions are feasible.

wnminv, wnanl, wnnlp

[1] F. Hillier and G. Lieberman: Introduction to Operations Research. Holden-Day Inc.

[2] J. Franklin: Methods of Mathematical Economics. Springer-Verlag.

[3] G. B. Dantzig, A. Orden, and P. Wolfe: Generalized Simplex Method for Minimizing a Linear Form under Linear Inequality Restraints, Pacific J. Math. Vol. 5 (1955) pp. 183-195.

Will Naylor