[Help-glpk] glpk development feedback

[Andrew Makhorin]

As it gets understood many users of glpk would like to use this package
not only for solving lp/mip problems, but as a base for developing their
own optimization software. The existing api routines included in the
package doesn't provide or provide inefficiently many features, which
are required in this case. Therefore I started to develop a new, more
efficient implementation of the primal/dual simplex method and a set of
new low-level api routines to fill the gap. These new low-level api
routines are not intended to replace the existing api routines; they
just provide more flexible and more efficient interaction between the
application program, LP problem, and simplex-based lp solvers.

Below I give a brief (currently incomplete) overview of these new api
routines. The reason is that I'd like to have some feedback, which would
help me to develop adequate software.

Please send your remarks, additions, questions and/or suggestions either
to the list <address@hidden> or directly to me.


Andrew Makhorin,
the author and maintainer of GLPK


************************************************************************

A BRIEF OVERVIEW OF LOW-LEVEL GLPK API ROUTINES
===============================================

Note that some of these routines were included in the glpk 3.0.7 (see
the header 'glplpx.h' for details).

PROBLEM CREATING AND MODIFYING ROUTINES
---------------------------------------

LPX *lpx_create_prob(void);
   Creates an "empty" LP problem and returns a pointer to low-level LP
   problem object.

void lpx_add_rows(LPX *lp, int nrs);
   Adds nrs rows (constraints) to the end of the row list.

void lpx_add_cols(LPX *lp, int ncs);
   Adds ncs columns (structural variables) to the end of the column
   list.

void lpx_set_prob_name(LPX *lp, char *name);
   Assigns a symbolic name (up to 255 chars) to the problem.

void lpx_set_row_name(LPX *lp, int i, char *name);
   Assigns a symbolic name (up to 255 chars) to the i-th row.

void lpx_set_col_name(LPX *lp, int j, char *name);
   Assigns a symbolic name (up to 255 chars) to the j-th column.

void lpx_set_row_bnds(LPX *lp, int i, int typx, double lb, double ub);
   Sets (changes) type and bounds of the i-th row (auxiliary variable):
   typx = LPX_FR: -inf <  x <  +inf (free row);
   typx = LPX_LO:   lb <= x <  +inf (constraint of '>=' type);
   typx = LPX_UP: -inf <  x <= ub   (constraint of '<=' type);
   typx = LPX_DB:   lb <= x <= ub   (constraint of ranged type);
   typx = LPX_FX:   lb  = x  = ub   (constraint of '=' type).

void lpx_set_col_bnds(LPX *lp, int j, int typx, double lb, double ub);
   Sets (changes) type and bounds of the i-th column (structural
   variable):
   typx = LPX_FR: -inf <  x <  +inf (free variable);
   typx = LPX_LO:   lb <= x <  +inf (variable with lower bound);
   typx = LPX_UP: -inf <  x <= ub   (variable with upper bound);
   typx = LPX_DB:   lb <= x <= ub   (double-bounded variable);
   typx = LPX_FX:   lb  = x  = ub   (fixed variable).

void lpx_set_obj_dir(LPX *lp, int dir);
   Sets (changes) the optimization direction (objective sense):
   dir = LPX_MIN: minimization;
   dir = LPX_MAX: maximization.

void lpx_set_obj_c0(LPX *lp, double c0);
   Sets (changes) a constant term of the objective function.

void lpx_set_row_coef(LPX *lp, int i, double coef);
   Sets (changes) an objective coefficient at the i-th auxiliary
   variable.

void lpx_set_col_coef(LPX *lp, int j, double coef);
   Sets (changes) an objective coefficient at the j-th structural
   variable.

void lpx_set_mat_row(LPX *lp, int i, int len, int ndx[], double val[]);
   Replaces the i-th row of the constraint matrix by a new sparse
   vector:
   len is number of non-zeros in the sparse vector;
   ndx[1..len] are column indices, and
   val[1..len] are numerical values of non-zero coefficients.

void lpx_set_mat_col(LPX *lp, int j, int len, int ndx[], double val[]);
   Replaces the j-th column of the constraint matrix by a new sparse
   vector:
   len is number of non-zeros in the sparse vector;
   ndx[1..len] are row indices, and
   val[1..len] are numerical values of non-zero coefficients.

void lpx_unmark_all(LPX *lp);
   Unmarks all rows and columns of the problem object.

void lpx_mark_row(LPX *lp, int i, int mark);
   Assigns an integer mark to the i-th row.

void lpx_mark_col(LPX *lp, int j, int mark);
   Assigns an integer mark to the j-th column.

void lpx_change_ordn(LPX *lp);
   Changes ordinal numbers of rows and columns. New ordinal numbers are
   specified by row and columns marks.

void lpx_clear_mat(LPX *lp);
   Replaces marked rows and columns of the constraint matrix by "empty"
   vectors.

void lpx_del_items(LPX *lp);
   Removes marked rows and columns from the LP problem object.

void lpx_delete_prob(LPX *lp);
   Deletes the LP problem object freeing all the memory allocated to it.

PROBLEM QUERYING ROUTINES
-------------------------

int lpx_get_num_rows(LPX *lp);
   Returns the current number of rows in the LP problem object.

int lpx_get_num_cols(LPX *lp);
   Returns the current number of columns in the LP problem object.

int lpx_get_num_nz(LPX *lp);
   Returns the current number of non-zero coefficients in the constraint
   matrix.

char *lpx_get_prob_name(LPX *lp);
   Returns a symbolic name assigned to the problem object (or NULL if
   the problem is unnamed).

char *lpx_get_row_name(LPX *lp, int i);
   Returns a symbolic name assigned to the i-th row (or NULL if the row
   is unnamed).

char *lpx_get_col_name(LPX *lp, int j);
   Returns a symbolic name assigned to the j-th column (or NULL, if the
   column is unnamed).

void lpx_get_row_bnds(LPX *lp, int i, int *typx, double *lb, double *ub)
   Obtains the current type and bounds of the i-th row (for typx, lb,
   and ub see the routine lpx_set_row_bnds).

void lpx_get_col_bnds(LPX *lp, int j, int *typx, double *lb, double *ub)
   Obtains the current type and bounds of the j-th column (for typx, lb,
   and ub see the routine lpx_set_col_bnds).

int lpx_get_obj_dir(LPX *lp);
   Returns the current optmization direction (objective sense):
   dir = LPX_MIN: minimization;
   dir = LPX_MAX: maximization.

double lpx_get_obj_c0(LPX *lp);
   Returns a constant term of the objective function.

double lpx_get_row_coef(LPX *lp, int i);
   Returns an objective coefficient at the i-th auxiliary variable.

double lpx_get_col_coef(LPX *lp, int j);
   Returns an objective coefficient at the j-th structural variable.

int lpx_get_mat_row(LPX *lp, int i, int ndx[], double val[]);
   Obtains the i-th row of the constraint matrix as a sparse vector:
   ndx[1..len] are column indices, and
   val[1..len] are numerical values of non-zero coefficients,
   len is number of non-zeros returned on exit.

int lpx_get_mat_col(LPX *lp, int j, int ndx[], double val[]);
   Obtains the j-th column of the constraint matrix as a sparse vector:
   ndx[1..len] are row indices, and
   val[1..len] are numerical values of non-zero coefficients,
   len is number of non-zeros returned on exit.

int lpx_get_status(LPX *lp);
   Returns the general status of the most recently found basic solution:
   LPX_OPT:       optimal;
   LPX_FEAS:      feasible (optimality has not been proven yet);
   LPX_INFEAS:    infeasible (infeasibility has not been proven yet);
   LPX_NOFEAS:    infeasible (infeasibility has been proven);
   LPX_UNBND:     unbounded (unboundness has been proven);
   LPX_UNDEF:     undefined (either the problem has not been solved yet,
                  or it has been changed since the last solve).

int lpx_get_prim_status(LPX *lp);
   Returns the primal status of the most recently found basic solution:
   LPX_P_UNDEF:   undefined;
   LPX_P_FEAS:    primal feasible;
   LPX_P_INFEAS:  primal infeasible (primal infeasibility has not been
                  proven yet);
   LPX_P_NOFEAS:  primal infeasible (primal infeasibility has been
                  proven).

int lpx_get_dual_status(LPX *lp);
   Returns the dual status of the most recently found basic solution:
   LPX_D_UNDEF:   undefined;
   LPX_D_FEAS:    dual feasible;
   LPX_D_INFEAS:  dual infeasible (dual infeasibility has not been
                  proven yet);
   LPX_D_NOFEAS:  dual infeasible (dual infeasibility has been proven).

void lpx_get_row_info(LPX *lp, int i, int *tagx, double *valx,
      double *dx);
   Obtains a solution information of the most recently found basic
   solution for the i-th row (auxiliary variable):
   tagx = LPX_BS: basic row (inactive constraint);
   tagx = LPX_NL: non-basic row on its lower bound (ineq. constraint);
   tagx = LPX_NU: non-basic row on its upper bound (ineq. constraint);
   tagx = LPX_NF: non-basic free (unbounded) row;
   tagx = LPX_NS: non-basic fixed row (equality constraint).
   valx is a numerical value of the corresponding linear form.
   dx is a reduced cost of the i-th row.

void lpx_get_col_info(LPX *lp, int j, int *tagx, double *valx,
      double *dx);
   Obtains a solution information of the most recently found basic
   solution for the j-th column (structural variable):
   tagx = LPX_BS: basic column;
   tagx = LPX_NL: non-basic column on its lower bound;
   tagx = LPX_NU: non-basic column on its upper bound;
   tagx = LPX_NF: non-basic free (unbounded) column;
   tagx = LPX_NS: non-basic fixed column.
   valx is a numerical value of the corresponding structural variable.
   dx is a reduced cost of the j-th column.

double lpx_get_obj_val(LPX *lp);
   Returns a value of the objective function in the most recently found
   basic solution.

void lpx_print_sol(LPX *lp, char *fname);
   Writes out the most recently found basic solution to a text file
   named fname using a printable format.

PROBLEM SCALING ROUTINES
------------------------

Actually *all* components of the LP problem stored in the structure
LPX are in the scaled form (for example, the constraint matrix stored
in LPX is A" = R*A*S, not A), and if the scaling is not used, it just
means that the matrices R and S are unity. Each time when something
is entered into LPX (for example, bounds of variables or constraint
coefficients), it is automatically scaled and then stored, and vice
versa, if something is obtained from LPX (for example, components of
the current basic solution), it is automatically unscaled. Thus, on
API level the scaling process is invisible (except round-off effects
of the order DBL_EPSILON).

void lpx_scale_prob(LPX *lp);
   Scales the LP problem. A particular scaling method is specified by
   some control parameters.

void lpx_unscale_prob(LPX *lp);
   Unscales the LP problem, i.e. replaces the scaling matrices R and S
   by unity matrices.

INITIAL BASIS ROUTINES
----------------------

In the LPX data structure the initial (or the current) basis can have
the following statuses:

   "cold"   the basis is unknown;
   "warm"   the basis is known (i.e. it is known which rows/columns are
            basic, which are non-basic, and which bounds the non-basics
            sit on);
   "hot"    the basis is known and additionally the factorization of the
            basis matrix is valid.

(There may be an intermediate status between "warm" and "hot" when the
factorization is although invalid, but the pivoting sequence is known
and can be used in the gaussian elimination. However this feature is not
currently implemented.)

void lpx_std_basis(LPX *lp);
   Builds a "standard" initial basis, where all rows are basic and all
   columns are non-basic.

void lpx_adv_basis(LPX *lp);
   Builds an "advanced" initial basis, where the basis matrix is
   implicit triangular, and number of basic fixed rows (i.e. equality
   constraints) is as minimal as possible.

void lpx_set_row_stat(LPX *lp, int i, int stat);
   Changes the status of the i-th row:
   stat = LPX_BS: basic row (inactive constraint);
   stat = LPX_NL: non-basic row (active constraint);
   stat = LPX_NU: non-basic double-bounded row on its upper bound.

void lpx_set_col_stat(LPX *lp, int j, int stat);
   Changes the status of the j-th column:
   stat = LPX_BS: basic column;
   stat = LPX_NL: non-basic column;
   stat = LPX_NU: non-basic double-bounded column on its upper bound.

The latter two routines are intended for building a basis using some
algorithm supplied by the user.

SIMPLEX-BASED SOLVER ROUTINES
-----------------------------

int lpx_warm_up(LPX *lp);
   "Warms up" the initial basis. This operation includes computing
   the factorization of the basis matrix and basic solution components.

int lpx_prim_opt(LPX *lp);
   Finds an optimal solution of the LP problem using the primal simplex
   method. The initial basis on entry to this routine should be primal
   feasible.

int lpx_dual_opt(LPX *lp);
   Finds an optimal solution of the LP problem using the dual simplex
   method. The initial basis on entry to this routine should be dual
   feasible.

int lpx_prim_feas(LPX *lp);
   Finds a primal feasible solution using the method of implicit
   artificial variables (based on the primal simplex method).

int lpx_prim_art(LPX *lp);
   Finds an primal feasible solution using the method of single
   artificial variable (based on the primal simplex method).

int lpx_simplex(LPX *lp);
   An easy-to-use driver to the simplex method routines.

ADDITIONAL ROUTINES (NOT DEVELOPED YET)
---------------------------------------

Computing components of the simplex table (its rows and columns).

Computing/pricing a row/column not presented in the problem.

Basis maintenance routines available on api level.

Preprocessing and presolving routines.

Cross-over routines (to identify basic solution using a given interior
point solution).