1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
(Stolen from ftp://softlib.cs.rice.edu/pub/miplib/mps_format)
MPS input format was originally introduced by IBM to express linear
and integer programs in a standard way. The format is a fixed column
format, so care must be taken that all information is placed in the
correct columns as described below.
The following is not intended as a complete description of MPS format,
but only as a brief introduction. For more information, the reader is
directed to:
"Advanced Linear Programming," by Bruce A. Murtagh
"Computer Solutions of Linear Programs," by J.L. Nazareth
It may be useful to look at an example MPS file while reading this
MPS information.
The following template is a guide for the use of MPS format:
---------------------------------------------------------------------
Field: 1 2 3 4 5 6
Columns: 2-3 5-12 15-22 25-36 40-47 50-61
NAME problem name
ROWS
type name
COLUMNS
column row value row value
name name name
RHS
rhs row value row value
name name name
RANGES
range row value row value
name name name
BOUNDS
type bound column value
name name
ENDATA
---------------------------------------------------------------------
NOTES:
A. In the ROWS section, each row of the constraint matrix must have a
row type and a row name specified. The code for indicating row type
is as follows:
type meaning
---------------------------
E equality
L less than or equal
G greater than or equal
N objective
N no restriction
B. In the COLUMNS section, the names of the variables are defined along
with the coefficients of the objective and all the nonzero constraint
matrix elements. It is not necessary to specify columns for slack or
surplus variables as this is taken care of automatically.
C. The RHS section contains information for the right-hand side of the problem.
D. The RANGES section is for constraints of the form: h <= constraint <= u .
The range of the constraint is r = u - h . The value of r is specified
in the RANGES section, and the value of u or h is specified in the RHS
section. If b is the value entered in the RHS section, and r is the
value entered in the RANGES section, then u and h are thus defined:
row type sign of r h u
----------------------------------------------
G + or - b b + |r|
L + or - b - |r| b
E + b b + |r|
E - b - |r| b
E. In the BOUNDS section, bounds on the variables are specified. When
bounds are not indicated, the default bounds ( 0 <= x < infinity )
are assumed. The code for indicating bound type is as follows:
type meaning
-----------------------------------
LO lower bound b <= x
UP upper bound x <= b
FX fixed variable x = b
FR free variable
MI lower bound -inf -inf < x
BV binary variable x = 0 or 1
LI lower bound (int) b <= x *1
UI upper bound (int) x <= b *1
*1 : BOUNDS type of LI / UI is AMPS syntax
F. Sections RANGES and BOUNDS are optional as are the fields 5 and 6.
Everything else is required. In regards to fields 5 and 6, consider
the following 2 constraints:
const1: 2x + 3y < 6
const2: 5x + 8y < 20
Two ways to enter the variable x in the COLUMNS section are:
(Field: 2 3 4 5 6 )
1. x const1 2.0 const2 5.0
2. x const1 2.0
x const2 5.0
G. A mixed integer program requires the specification of which variables
are required to be integer. Markers are used to indicate the start
and end of a group of integer variables. The start marker has its
name in field 2, 'MARKER' in field 3, and 'INTORG' in field 5. The
end marker has its name in field 2, 'MARKER' in field 3, and 'INTEND'
in field 5. These markers are placed in the COLUMNS section.
|
