GLPK/Interoperability

From Wikibooks, open books for an open world
Jump to: navigation, search

Interoperability, in this case, refers to the ability to translate between and/or use common linear and mixed integer problem specification formats under GLPK. These formats are used to present and archive problem instances. The notion of a problem format should not be confused with that of a high-level modeling language, such as GLPK MathProg. This page also considers the solution recovery formats provided by GLPK and gives information on the machine processing of GLPK output.

Overview[edit]

GLPK can readily input and output problems in various problem specification formats:

  • the CPLEX LP format (includes MIP problems)
  • the MPS format in fixed (ancient) and free (modern) variants
  • a custom DIMACS-like format named GLPK format.

This means GLPK can be used to create problems for other solvers. And can take problems from other sources and either reformat them or solve them. This functionality is available through both GLPSOL and the GLPK callable library. Indeed some users employ GLPK solely for its model generation and problem reformatting features — and never actually invoke the underlying solver.

GLPK is not able to write back results to these formats in cases where the underlying format specification provides for this. Users must rely on the native GLPK solution output instead. Nor does GLPK currently support any of the XML-based optimization formats [1] including that developed as part of the COIN-OR OS (Optimization Services) project.

In addition, GLPK offers several graph reading and writing routines which make use of the DIMACS clique/coloring format and also a custom GLPK plain text format. These API routines are not currently available through GLPSOL and are not discussed further.

Earlier versions of GLPK have supported the OPB pseudo-boolean format.

The following file extension conventions normally apply:

Format File extension Comment
CPLEX LP .lp
MPS .mps fixed and free
GLPK .glp  .glpk

The official GLPK documentation gives full details of each supported format.

Finally, an example of sensitivity analysis is included on this page although it is not really an interoperability issue. Sensitivity analysis interpretation keys are given in the glp_print_ranges entry.

GLPSOL usage[edit]

GLPSOL offers convenient command-line usage for achieving interoperability. A review of the help message from GLPSOL makes a good starting point.

The following table summarizes the relevant interoperability options (the MathProg column is included for completeness):[2]

CPLEX LP MPS fixed MPS free GLPK MathProg
Read --lp --mps --freemps --glp --math
Write --wlp filename --wmps filename --wfreemps filename --wglp filename not possible

As indicated, it is not generally possible to create a high-level model from a lower-level problem format. That said, the CPLEX LP format is the most human legible.

The following example reads in an existing convert.lp CPLEX LP format file and outputs a GLPK format file without solving the model. In this case, the --check option prevents the model from being run.

$ glpsol --check --wglp convert.glp --lp convert.lp 

The GLPSOL options for solution capture comprise:

Printable format Plain text format
Recover --output filename --write filename

The printable format is designed to be understood by humans. The plain text format is for machine processing. Neither format represents an established standard. A copy of the terminal output can also be written to file using the --log option. Hence:

$ glpsol --output example.out --log example.log --math example.mod 

The same functionality provided by GLPSOL is also available through API routines from the GLPK callable library.

Again the official GLPK documentation gives full details of each format.

Machine processing GLPK output[edit]

Users may wish to automatically process the output from GLPK. But GLPK cannot produce common machine-parsable formats like CSV (comma-separated values) or XML or specialized dialects based on these two protocols. Instead, the GLPK maintainer advises:

"To access the solution found by GLPSOL from a computer program, one could write the model with the --wglp option and the solution with the --write option. The ordering of rows and columns is the same in both files. It is enough to obtain all necessary information. (The only improvements I would like to make here is to use a DIMACS-like format for solution files.)" Source: [help-glpk], 19 Jan 2011, grammar corrected, emphasis added.

See elsewhere on this page for representative output from these two GLPSOL options.

The same output can also be generated using the appropriate API calls, namely: glp_write_sol, glp_write_ipt, glp_write_mip, and glp_write_prob.

Short examples[edit]

This section uses the short.mod model, first introduced on the MathProg page. Save the following model in a file named short.mod.

# short example
var x1;
var x2;
maximize obj: 0.6 * x1 + 0.5 * x2;
s.t. c1: x1 + 2 * x2 <= 1;
s.t. c2: 3 * x1 + x2 <= 2;
solve;
display x1, x2;
end;

Astute readers may notice that this model does not contain advanced MathProg language features and thus looks much like a problem format (the solve and display statements excepted).

A selection of calls and results are given next. This exercise also provides a useful visual comparison of these various formats.

CPLEX LP format[edit]

$ glpsol --check --wlp short.lp --math short.mod 
\* Problem: short *\

Maximize
 obj: + 0.6 x1 + 0.5 x2

Subject To
 c1: + x1 + 2 x2 <= 1
 c2: + 3 x1 + x2 <= 2

Bounds
 x1 free
 x2 free

End

MPS fixed format[edit]

$ glpsol --check --wmps short.mps --math short.mod 
* Problem:    short
* Class:      LP
* Rows:       3
* Columns:    2
* Non-zeros:  6
* Format:     Fixed MPS
*
NAME          short
ROWS
 N  obj
 L  c1
 L  c2
COLUMNS
    x1        obj                0.6   c1                   1
    x1        c2                   3
    x2        obj                0.5   c1                   2
    x2        c2                   1
RHS
    RHS1      c1                   1   c2                   2
BOUNDS
 FR BND1      x1      
 FR BND1      x2      
ENDATA

MPS free format[edit]

$ glpsol --check --wfreemps short.mps --math short.mod 
* Problem:    short
* Class:      LP
* Rows:       3
* Columns:    2
* Non-zeros:  6
* Format:     Free MPS
*
NAME short
ROWS
 N obj
 L c1
 L c2
COLUMNS
 x1 obj 0.6 c1 1
 x1 c2 3
 x2 obj 0.5 c1 2
 x2 c2 1
RHS
 RHS1 c1 1 c2 2
BOUNDS
 FR BND1 x1
 FR BND1 x2
ENDATA

GLPK format[edit]

$ glpsol --check --wglp short.glp --math short.mod 
p lp max 3 2 6
n p short
n z obj
i 1 f
n i 1 obj
i 2 u 1
n i 2 c1
i 3 u 2
n i 3 c2
j 1 f
n j 1 x1
j 2 f
n j 2 x2
a 0 1 0.6
a 0 2 0.5
a 1 1 0.6
a 1 2 0.5
a 2 1 1
a 2 2 2
a 3 1 3
a 3 2 1
e o f

GLPSOL output format[edit]

See here for information regarding the KKT optimality conditions.

$ glpsol --output short.out --math short.mod
Problem:    short
Rows:       3
Columns:    2
Non-zeros:  6
Status:     OPTIMAL
Objective:  obj = 0.46 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 obj          B           0.46                             
     2 c1           NU             1                           1          0.18 
     3 c2           NU             2                           2          0.14 

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           B            0.6                             
     2 x2           B            0.2                             

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.DE: max.abs.err = 0.00e+00 on column 0
        max.rel.err = 0.00e+00 on column 0
        High quality

KKT.DB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

End of output

GLPSOL write format[edit]

$ glpsol --write short.sol --math short.mod
3 2
2 2 0.46
1 0.46 0
3 1 0.18
3 2 0.14
1 0.6 0
1 0.2 0

GLPSOL sensitivity analysis[edit]

See here for information regarding the table headers.

$ glpsol --ranges short.rng --math short.mod
GLPK 4.45 - SENSITIVITY ANALYSIS REPORT                                                                         Page   1

Problem:    short
Objective:  obj = 0.46 (MAXimum)

   No. Row name     St      Activity         Slack   Lower bound       Activity      Obj coef  Obj value at Limiting
                                          Marginal   Upper bound          range         range   break point variable
------ ------------ -- ------------- ------------- -------------  ------------- ------------- ------------- ------------
     1 obj          BS        .46000       -.46000          -Inf           -Inf      -1.00000        .      c1
                                            .               +Inf         .46000          +Inf          +Inf

     2 c1           NU       1.00000        .               -Inf           -Inf       -.18000          -Inf
                                            .18000       1.00000           +Inf          +Inf          +Inf

     3 c2           NU       2.00000        .               -Inf           -Inf       -.14000          -Inf
                                            .14000       2.00000           +Inf          +Inf          +Inf

GLPK 4.45 - SENSITIVITY ANALYSIS REPORT                                                                         Page   2

Problem:    short
Objective:  obj = 0.46 (MAXimum)

   No. Column name  St      Activity      Obj coef   Lower bound       Activity      Obj coef  Obj value at Limiting
                                          Marginal   Upper bound          range         range   break point variable
------ ------------ -- ------------- ------------- -------------  ------------- ------------- ------------- ------------
     1 x1           BS        .60000        .60000          -Inf           -Inf        .25000        .25000 c2
                                            .               +Inf           +Inf       1.50000       1.00000 c1

     2 x2           BS        .20000        .50000          -Inf           -Inf        .20000        .40000 c1
                                            .               +Inf           +Inf       1.20000        .60000 c2

End of report

References[edit]

  1. Fourer, Robert; Lopes, Leo; Martin, Kipp (2005), "LPFML: A W3C XML Schema for Linear and Integer Programming", INFORMS Journal on Computing 17 (2): 139-158, doi:10.1287/ijoc.1040.0120 
  2. The obsolete option --wcpxlp is equivalent to --wlp.