NAG C Library Function Document

nag_opt_miqp_mps_read (e04mxc) reads data for sparse linear programming, mixed integer linear programming, quadratic programming or mixed integer quadratic programming problems from an external file which is in standard or compatible MPS input format.

2

Specification

#include <nag.h>

#include <nage04.h>

void

nag_opt_miqp_mps_read (Nag_FileID fileid, Integer maxn, Integer maxm, Integer maxnnz, Integer maxncolh, Integer maxnnzh, Integer maxlintvar, Integer mpslst, Integer *n, Integer *m, Integer *nnz, Integer *ncolh, Integer *nnzh, Integer *lintvar, Integer *iobj, double a[], Integer irowa[], Integer iccola[], double bl[], double bu[], char pnames[][9], Integer *nname, char crname[][9], double h[], Integer irowh[], Integer iccolh[], Integer *minmax, Integer intvar[], NagError *fail)

3

Description

nag_opt_miqp_mps_read (e04mxc) reads data for linear programming (LP) or quadratic programming (QP) problems (or their mixed integer variants) from an external file which is prepared in standard or compatible MPS (see IBM (1971)) input format. It then initializes

n

(the number of variables),

m

(the number of general linear constraints), the

m

n

matrix

A

, the vectors

l

u

c

(stored in row iobj of

A

) and the

n

n

Hessian matrix

H

for use with nag_opt_sparse_convex_qp_solve (e04nqc). This function is designed to solve problems of the form

\underset{x}{minimize} c^{T} x + \frac{1}{2} x^{T} H x subject to l \leq \{\begin{matrix} x \\ A x \end{matrix}\} \leq u .

3.1

MPS input format

The input file of data may only contain two types of lines:

1.	Indicator lines (specifying the type of data which is to follow).
2.	Data lines (specifying the actual data).

A section is a combination of an indicator line and its corresponding data line(s). Any characters beyond column 80 are ignored. Indicator lines must not contain leading blank characters (in other words they must begin in column 1). The following displays the order in which the indicator lines must appear in the file:

NAME	user-supplied name	(optional)
OBJSENSE		(optional)
	data line
OBJNAME		(optional)
	data line
ROWS
	data line(s)
COLUMNS
	data line(s)
RHS
	data line(s)
RANGES		(optional)
	data line(s)
BOUNDS		(optional)
	data line(s)
QUADOBJ		(optional)
	data line(s)
ENDATA

A data line follows a fixed format, being made up of fields as defined below. The contents of the fields may have different significance depending upon the section of data in which they appear.

	Field 1	Field 2	Field 3	Field 4	Field 5	Field 6
Columns	$2 - 3$	$5 - 12$	$15 - 22$	$25 - 36$	$40 - 47$	$50 - 61$
Contents	Code	Name	Name	Value	Name	Value

Each name and code must consist of ‘printable’ characters only; names and codes supplied must match the case used in the following descriptions. Values are read using a field width of

12

. This allows values to be entered in several equivalent forms. For example,

1.2345678

1.2345678e+0

123.45678e−2

and

12345678e−07

all represent the same number. It is safest to include an explicit decimal point.

Lines with an asterisk (

*

) in column

1

will be considered comment lines and will be ignored by the function.

Columns outside the six fields must be blank, except for columns 72–80, whose contents are ignored by the function. A non-blank character outside the predefined six fields and columns 72–80 is considered to be a major error (

fail . code =

NE_MPS_ILLEGAL_DATA_LINE; see Section 6), unless it is part of a comment.

3.1.1

NAME Section (optional)

The NAME section is the only section where the data must be on the same line as the indicator. The ‘user-supplied name’ must be in field

3

but may be blank.

Field	Required	Description
$3$	No	Name of the problem

3.1.2

OBJSENSE Section (optional)

The data line in this section can be used to specify the sense of the objective function. If this section is present it must contain only one data line. If the section is missing or empty, minimization is assumed.

Field	Required	Description
$2$	No	Sense of the objective function

Field 2 may contain either MIN, MAX, MINIMIZE or MAXIMIZE.

3.1.3

OBJNAME Section (optional)

The data line in this section can be used to specify the name of a free row (see Section 3.1.4) that should be used as the objective function. If this section is present it must contain only one data line. If the section is missing or is empty, the first free row will be chosen instead. Alternatively, OBJNAME can be overridden by setting nonempty

pnames [1]

(see Section 5).

Field	Required	Description
$2$	No	Row name to be used as the objective function

Field 2 must contain a valid row name.

3.1.4

ROWS Section

The data lines in this section specify unique row (constraint) names and their inequality types (i.e., unconstrained,

=

\geq

\leq

Field	Required	Description
$1$	Yes	Inequality key
$2$	Yes	Row name

The inequality key specifies each row's type. It must be E, G, L or N and can be in either column

2

3

Inequality Key	Description	$l$	$u$
N	Free row	$- \infty$	$\infty$
G	Greater than or equal to	finite	$\infty$
L	Less than or equal to	$- \infty$	finite
E	Equal to	finite	$l$

Row type N stands for ‘Not binding’. It can be used to define the objective row. The objective row is a free row that specifies the vector

c

in the linear objective term

c^{T} x

. If there is more than one free row, the first free row is chosen, unless another free row name is specified by OBJNAME (see Section 3.1.3) or

pnames [1]

(see Section 5). Note that

c

is assumed to be zero if either the chosen row does not appear in the COLUMNS section (i.e., has no nonzero elements) or there are no free rows defined in the ROWS section.

3.1.5

COLUMNS Section

Data lines in this section specify the names to be assigned to the variables (columns) in the general linear constraint matrix

A

, and define, in terms of column vectors, the actual values of the corresponding matrix elements.

Field	Required	Description
$2$	Yes	Column name
$3$	Yes	Row name
$4$	Yes	Value
$5$	No	Row name
$6$	No	Value

Each data line in the COLUMNS section defines the nonzero elements of

A

c

. Any elements of

A

c

that are undefined are assumed to be zero. Nonzero elements of

A

must be grouped by column, that is to say that all of the nonzero elements in the jth column of

A

must be specified before those in the

j + 1

th column, for

j = 1, 2, \dots, n - 1

. Rows may appear in any order within the column.

3.1.5.1

Integer Markers

For backward compatibility nag_opt_miqp_mps_read (e04mxc) allows you to define the integer variables within the COLUMNS section using integer markers, although this is not recommended as markers can be treated differently by different MPS readers; you should instead define any integer variables in the BOUNDS section (see below). Each marker line must have the following format:

Field	Required	Description
$2$	No	Marker ID
$3$	Yes	Marker tag
$5$	Yes	Marker type

The marker tag must be

^{'}

MARKER

^{'}

. The marker type must be

^{'}

INTORG

^{'}

to start reading integer variables and

^{'}

INTEND

^{'}

to finish reading integer variables. This implies that a row cannot be named

^{'}

MARKER

^{'}

^{'}

INTORG

^{'}

^{'}

INTEND

^{'}

. Please note that both marker tag and marker type comprise of

8

characters as a

^{'}

is the mandatory first and last character in the string. You may wish to have several integer marker sections within the COLUMNS section, in which case each marker section must begin with an

^{'}

INTORG

^{'}

marker and end with an

^{'}

INTEND

^{'}

marker and there should not be another marker between them.

Field 2 is ignored by nag_opt_miqp_mps_read (e04mxc). When an integer variable is declared it will keep its default bounds unless they are changed in the BOUNDS section. This may vary between different MPS readers.

3.1.6

RHS Section

This section specifies the right-hand side values (if any) of the general linear constraint matrix

A

Field	Required	Description
$2$	Yes	RHS name
$3$	Yes	Row name
$4$	Yes	Value
$5$	No	Row name
$6$	No	Value

The MPS file may contain several RHS sets distinguished by RHS name. If an RHS name is defined in

pnames [2]

(see Section 5) then nag_opt_miqp_mps_read (e04mxc) will read in only that RHS vector, otherwise the first RHS set will be used.

Only the nonzero RHS elements need to be specified. Note that if an RHS is given to the objective function it will be ignored by nag_opt_miqp_mps_read (e04mxc). An RHS given to the objective function is dealt with differently by different MPS readers, therefore it is safer to not define an RHS of the objective function in your MPS file. Note that this section may be empty, in which case the RHS vector is assumed to be zero.

3.1.7

RANGES Section (optional)

Ranges are used to modify the interpretation of constraints defined in the ROWS section (see Section 3.1.4) to the form

l \leq A x \leq u

, where both

l

and

u

are finite. The range of the constraint is

r = u - l

Field	Required	Description
$2$	Yes	Range name
$3$	Yes	Row name
$4$	Yes	Value
$5$	No	Row name
$6$	No	Value

The range of each constraint implies an upper and lower bound dependent on the inequality key of each constraint, on the RHS

b

of the constraint (as defined in the RHS section), and on the range

r

Inequality Key	Sign of $r$	$l$	$u$
E	$+$	$b$	$b + r$
E	$-$	$b + r$	$b$
G	$+ / -$	$b$	$b + \|r\|$
L	$+ / -$	$b - \|r\|$	$b$
N	$+ / -$	$- \infty$	$+ \infty$

If a range name is defined in

pnames [3]

(see Section 5) then the function will read in only the range set of that name, otherwise the first set will be used.

3.1.8

BOUNDS Section (optional)

These lines specify limits on the values of the variables (the quantities

l

and

u

l \leq x \leq u

). If a variable is not specified in the bound set then it is automatically assumed to lie between

0

and

+ \infty

Field	Required	Description
$1$	Yes	Bound type identifier
$2$	Yes	Bound name
$3$	Yes	Column name
$4$	Yes/No	Value

Note: field 4 is required only if the bound type identifier is one of UP, LO, FX, UI or LI in which case it gives the value

k

below. If the bound type identifier is FR, MI, PL or BV, field 4 is ignored and it is recommended to leave it blank.

The table below describes the acceptable bound type identifiers and how each determines the variables' bounds.

Bound Type Identifier	$l$	$u$	Integer Variable?
UP	unchanged	$k$	No
LO	$k$	unchanged	No
FX	$k$	$k$	No
FR	$- \infty$	$\infty$	No
MI	$- \infty$	unchanged	No
PL	unchanged	$\infty$	No
BV	$0$	$1$	Yes
UI	unchanged	$k$	Yes
LI	$k$	unchanged	Yes

If a bound name is defined in

pnames [4]

(see Section 5) then the function will read in only the bound set of that name, otherwise the first set will be used.

3.1.9

QUADOBJ Section (optional)

The QUADOBJ section defines nonzero elements of the upper or lower triangle of the Hessian matrix

H

Field	Required	Description
$2$	Yes	Column name (HColumn Index)
$3$	Yes	Column name (HRow Index)
$4$	Yes	Value
$5$	No	Column name (HRow Index)
$6$	No	Value

Each data line in the QUADOBJ section defines one (or optionally two) nonzero elements

H_{i j}

of the matrix

H

. Each element

H_{i j}

is given as a triplet of row index

i

, column index

j

and a value. The column names (as defined in the COLUMNS section) are used to link the names of the variables and the indices

i

and

j

. More precisely, the matrix

H

on output will have a nonzero element

H_{i j} = Value

where index

j

belongs to HColumn Index and index

i

to one of the HRow Indices such that

$crname [j - 1] = Column name (HColumn Index)$ and
$crname [i - 1] = Column name (HRow Index)$ .

It is only necessary to define either the upper or lower triangle of the

H

matrix; either will suffice. Any elements that have been defined in the upper triangle of the matrix will be moved to the lower triangle of the matrix, then any repeated nonzeros will be summed.

Note: it is much more efficient for nag_opt_sparse_convex_qp_solve (e04nqc) to have the

H

matrix defined by the first ncolh column names. If the nonzeros of

H

are defined by any columns that are not in the first ncolh of n then nag_opt_miqp_mps_read (e04mxc) will rearrange the matrices

A

and

H

so that they are.

3.2

Query Mode

nag_opt_miqp_mps_read (e04mxc) offers a ‘query mode’ to quickly give upper estimates on the sizes of user arrays. In this mode any expensive checks of the data and of the file format are skipped, providing a prompt count of the number of variables, constraints and matrix nonzeros. This might be useful in the common case where the size of the problem is not known in advance.

You may activate query mode by setting any of the following:

maxn < 1

maxm < 1

maxnnz < 1

maxncolh < 0

maxnnzh < 0

. If no major formatting error is detected in the data file,

fail . code =

NE_NOERROR is returned and the upper estimates are given as stated in Table 1. Alternatively, the function switches to query mode while the file is being read if it is discovered that the provided space is insufficient (that is, if

n > maxn

m > maxm

nnz > maxnnz

ncolh > maxncolh

nnzh > maxnnzh

lintvar > maxlintvar

). In this case

fail . code =

NE_INT_MAX is returned.

Argument Name	Upper Estimate for
n	maxn
m	maxm
nnz	maxnnz
ncolh	maxncolh
nnzh	maxnnzh
lintvar	maxlintvar

Table 1

The recommended practice is shown in Section 10, where the function is invoked twice. The first call queries the array lengths required, after which the data arrays are allocated to be of these sizes. The second call reads the data using the sufficiently-sized arrays.

4

References

IBM (1971) MPSX – Mathematical programming system Program Number 5734 XM4 IBM Trade Corporation, New York

5

Arguments

1: $fileid$ – Nag_FileIDInput

On entry: the ID of the MPSX data file to be read as returned by a call to nag_open_file (x04acc).

Constraint:

fileid \geq 0

2: $maxn$ – IntegerInput

On entry: an upper limit for the number of variables in the problem.

maxn < 1