QSopt Callable Library Overview QSopt > Callable Library > Overview
  QSopt
  Downloads
  LP Info
  Software
  Problem Formats
  Callable Library
Overview
  Function List
  Rational Solver
  Beta
  Contact Info

Nearly all QSopt library functions work with a single problem data structure that stores all available information about the problem as well as the associated choice of solution algorithm. A handle to the data structure is provided to the user by the QSprob data type.

The first step to working with an LP problem is to obtain an initialized QSprob from the QSopt library. There are three available functions that return initialized QSprob objects, allowing the user to start with an empty problem ( QScreate_prob), a problem described in a MPS format or LP format file ( QSread_prob), or a problem described by a set of user data ( QSload_prob). The QSfree function is used to free the memory associated with a QSprob when work on a given problem is completed.

The QSopt library provides access to two procedures for solving linear programming problems (and the LP relaxations associated with mixed-integer programming problems). The solution procedures are the primal and dual simplex algorithms. For each of these procedures, the user can specify a number of parameters to determine the particular variant of the algorithm that is applied (for example, the dual steepest-edge simplex algorithm). The parameters for the algorithms are specified by using the QSset_param function.

After a problem has been solved by QSopt_dual or QSopt_primal, information about the components of the solution such as the objective function value, the solution vector, the reduced costs, the values of the dual variables, and the values of the slack variables associated with the constraints, can be obtained through a variety of QSopt library functions described in the Accessing an LP Solution section in the QSopt Function List. The optimal basis can be obtained via the functions listed in the Working with an LP Basis section.

Except for the objective function value, all information is returned in arrays. The arrays need to be allocated by the calling routine. For the solution vector and for the values of the reduced costs, the arrays must be length at least ncols (the number of columns [variables] in the problem). For the values of the dual variables and for the values of the slack variables, the arrays must be of length at least nrows (the number of rows [constraints] in the problem). The appropriate values of ncols and nrows can be obtained by calls to the functions QSget_colcount and QSget_rowcount, respectively.

In many applications, a linear-programming problem needs to be modified during the course of the solution procedure, for example when new constraints are discovered or new variables need to be added. The QSopt library provides a variety of functions to address this need, see Modifying an LP Problem.Note that this collection of functions can also be used to build a problem from scratch, after a call to QScreate_prob to initialize an empty problem. The QSopt library provides a number of functions for obtaining information about the content of the problem associated with a specified QSprob object.

An LP solution found by the simplex algorithm has an associated basis. The basis can be used to restart the solution procedure after a problem is modified (usually allowing the algorithm to save a great amount of time over solving the problem from scratch). In the normal course of solving a problem, modifying the data, and resolving, the QSopt solvers will automatically use the basis information to aid in the resolves (the user does not need to provide any additional information to the solvers). However, if a problem is saved (for example to a file) and later reloaded, the basis information is lost. In such a case, it may be useful to save the basis and provide the solver with this information to help in the later solution of the problem. The QSopt library provides number of routines for saving and loading the basis information, as well as saving and loading information used by the dual steepest-edge variant of the simplex algorithm.

The QSopt functions provide two interfaces to the basis routines. The first interface makes use of the QSbas data type to store the associated information, in a manner similar to the use of the QSprob data type. The second interface makes use of a set of arrays to store the basis information (allowing the user to easily build and manipulate the data), see the Working with an LP Basis section of the Callable Function Library.

The Utility Routines section contains functions that allow users to set and obtain parameters associated with the solver routines.

The Advanced Computational Routines section contains functions that may be of interest to researchers and expert developers. These functions can be used in the design of branch-and-cut algorithms for integer programming and discrete optimization (they support routines in the Concorde traveling salesman problem code of Applegate, Bixby, Chvátal, and Cook).

 
QSopt | Problem Formats | Downloads Back
Last Updated: November 2003