wn_trans_problem, wn_trans_problem_feasible, wn_trans_problem_simplex_improve - transportation problem

#include <wn/wnspmat.h>
#include <wn/wntrn.h>

wn_trans_problem(&code, &objective, &result,
int code;
double objective;
wn_sparse_matrix result, cost_mat;
double i_capacities[], j_capacities[];

wn_trans_problem_feasible(&code, &result, cost_mat,
int code;
wn_sparse_matrix result, cost_mat;
double i_capacities[], j_capacities[];

wn_trans_problem_simplex_improve(&code, &objective,
&delta, &new_result, result, cost_mat, max_time)
int code;
double objective, delta;
wn_sparse_matrix new_result, result, cost_mat;
int max_time;

This package is designed to assist in solving the "transportation problem" easily and efficiently. The "transportation problem" is the following optimization problem:

CHOOSE result[i][j] TO MINIMIZE

sum_over(i,j){ result[i][j]*cost_mat[i][j] }

WHILE SATISFYING THE CONSTRAINTS

for_all(i){ sum_over(j){ result[i][j] } == i_capacities[i] }

for_all(j){ sum_over(i){ result[i][j] } == j_capacities[j] }

for_all(i,j){ result[i][j] >= 0 }

wn_trans_problem solves the transportation problem specified by cost_mat, i_capacities, and j_capacities. The optimal solution appears in result; its objective function appears in objective. code is set to WN_SUCCESS if the problem is solved successfully; if no solution is feasible, code is set to WN_INFEASIBLE. Solving a problem using wn_trans_problem can be too slow for large problems, that is why the routines below are provided.

wn_trans_problem_feasible finds a feasible solution to the transportation problem specified by cost_mat, i_capacities, and j_capacities. The solution is placed in result. code is set to WN_SUBOPTIMAL if a feasible solution is found; code is set to WN_INFEASIBLE otherwise. This routine is generally much faster than wn_trans_problem.

wn_trans_problem_simplex_improve improves a corner-feasible solution to a transportation problem, spending CPU time bounded by max_time. The resulting solution is also corner-feasible. Repeated application of this routine to a solution will eventually yield the optimal solution. Setting max_time=WN_IHUGE also yields the optimal solution. result contains the beginning solution. cost_mat specifies the transportation problem to be solve. Note that capacities are unnecessary because this information is already contained in result. The improved solution is placed in new_result. The objective function of new_result is placed in objective; the improvement achieved is placed in delta. code indicates the status of the solution; if the solution is optimal, code=WN_SUCCESS; if the solution is not optimal, code=WN_SUBOPTIMAL.

wn_trans_problem runs with

WORST and AVERAGE CASE:

time = e*(len_i+len_j)

stack_memory = 1

dynamic_memory = e

wn_trans_problem_feasible" runs with

WORST CASE:

time = e*(len_i+len_j)

stack_memory = 1

dynamic_memory = e

AVERAGE CASE:

time = e*log(e)

stack_memory = 1

dynamic_memory = e

"wn_trans_simplex_improve"

WORST and AVERAGE CASE:

time = max_time*log(e)

stack_memory = 1

dynamic_memory = e

if max_time < WN_IHUGE.

wn_trans_simplex_improve finds the optimum solution if max_time == WN_IHUGE, with

WORST CASE:

time = e*(len_i+len_j)*log(e)

stack_memory = 1

dynamic_memory = e

The actual time taken depends heavily on the start solution. Generally, the closer the start solution to optimum, the less time to get to optimum.

In the above, "len_i" and "len_j" are the i and j lengths of cost_mat; "e" is the number of entries of cost_mat.

wn_trans_problem and wn_trans_problem_feasible crash if i_capacities and j_capacities do not sum to equal quantities.

wn_trans_problem_simplex_improve crashes if result is not corner-feasible.

This code is new and has not been tested in large industrial applications.

wnsplx, wnprm, wnmst

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

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

Will Naylor