MPSFormat

MPS is a commonly used file format for storing linear and quadratic programs according to the concepts QuadraticProgram, LinearProgram, NonnegativeQuadraticProgram, and NonnegativeLinearProgram, see also http://en.wikipedia.org/wiki/MPS_(format).

CGAL supports a large subset of this format, but there are MPS files around that we cannot read (for example, files that encode integrality constraints on the variables). Also, there might be some other MPS-based solvers that will not be able to read the MPS files written by CGAL, since we do not strictly adhere to the very rigid layout requirements of the original MPS format.

Let's look at an example first. The quadratic program

minimize$$	x2 + 4(y-4)2	(=	x2 + 4y2 - 32y + 64)
subject to$$	x + y		7
	-x + 2y		4
	x		0
	y		0
	y		4

has the following description in MPS format.

NAME first_qp
ROWS
  N obj
  L c0
  L c1
COLUMNS
  x0  c0  1
  x0  c1  -1
  x1  obj  -32
  x1  c0  1
  x1  c1  2
RHS
  rhs obj -64
  rhs c0  7
  rhs c1  4
BOUNDS
  UP  BND  x1  4
QMATRIX
  x0  x0  2
  x1  x1  8
ENDATA

Here comes a semiformal description of the format in general.

NAME section

ROWS section

COLUMNS section

RHS section

The right-hand side identifier is succeeded by one or two sequences of tokens $$i val, where $$i names a constraint or the linear objective function, and $$val specifies the value $$b_i (if $$i names a constraint), or $$-c₀ (if $$i names the linear objective function). Values that are not specified in this section default to $$0. Otherwise, for every $$i, the last specified value determines $$b_i or $$-c₀.

BOUNDS section

0 x_j

The first token in every line is succeeded by an (optional) identifier (here: BND). An MPS file may encode several bound vectors $$l and $$u by using several such identifiers, but we ignore all lines having an identifier different from that of the first line. The first token $$t itself determines the type of the bound, and the token $$j after the bound identifier names the variable to which the bound applies In case of bound types FX, LO, and UP, there is another token $$val that specifices the bound value. Here is how bound type and value determine a bound for variable $$x_j. There may be several bound specifications for a single variable, and they are processed in order of appearance.

bound type	resulting bound
FX	$$xj = val ($$xj becomes a fixed variable)
LO	$$xj val (upper bound remains unchanged)
UP	$$xj val (lower bound remains unchanged, except if $$val<0; then, a zero lower bound is reset to $$- )
FR	$$- xj (previous bounds are discarded)
MI	$$xj - (upper bound remains unchanged)
PL	$$xj (lower bound remains unchanged)

QMATRIX / QUADOBJ / DMATRIX section

In case of QMATRIX and DMATRIX, all nonzero entries must be specified: if there is a line $$i j val, then there must also be a line $$j i val, since $$D is required to be symmetric. In case of QUADOBJ, only the entries of $$2D on or below the diagonal must be specified, entries above the diagonal are deduced from symmetry. It is not allowed to specify two or more different nonzero values for an unordered pair $${i,j}.

If this section is missing or does not contain nonzero values, the program is a model of the concept LinearProgram.

Miscellaneous

See Also

Quadratic_program_from_mps<NT>