Linear Programming: Foundations and Extensions (International Series in Operations Research & Management Science)

Category: Mathematics
Author: Robert J Vanderbei
This Month Stack Overflow 1


by anonymous   2019-01-13

The line


will select the dual simplex method. It does not give you the dual solution per se. (To be precise: afterwards you can retrieve both the primal and dual solution).

The way to retrieve the solution after solving is:

GLPK.glp_get_col_prim(lp,j)   // retrieve primal solution
GLPK.glp_get_row_dual(lp,i)   // retrieve duals 

Remember in linear programming

  • Dual Simplex Method
  • The Dual of an LP problem
  • Duals in a solution

are all different things. For more information please consult a book on Linear Programming (e.g. Vanderbei).

by anonymous   2019-01-13

If all variables (structural and logical) are non-negative (i.e. x>=0 and slacks s>=0) then all non-basic variables are equal to zero. As they are fixed to zero we only have to solve for the m basic variables.

Essentially we have to solve

A x = b

Unfortunately this is a non-square system of equations (after adding slacks we always have more columns than rows). In LPs we can form a basic solution and partition this into

B x_B + N x_N = b

After setting x_N = 0 we have just a square system of linear equations with solution:

x_B = inv(B) b

There is a fundamental theorem that says we can restrict the search to only basic solutions i.e. solutions that can be partitioned in basic and non-basic variables

x = [ x_B ]
    [ x_N ]

with x_B >= 0 and x_N = 0.

For more info open a book about Linear Programming; a very good one is Vanderbei.