[Help-glpk] modeling piecewise linear objectives and constraints in glpk

[Robbie Morrison]

Hello GLPK users

Andrew Makhorin made a posting to this list on 02 June
2007 with the subject line "SOS2 constraints in GLPK".

I typeset this original posting to make the maths more
readable and added an additional note from Andrew
concerning the modeling of constraints as well as
objectives.

The attached PDF should be of interest to anyone
wishing to model piecewise linear objectives and
constraints in GLPK (or any other MIP solver).

Can someone tell me whether 'f(x)' can be be
vector-valued?  Or is this formulation limited to
scalar functions?  (I think not.)

The method given is similar to the "convex combination
model" in Croxton et al (2002, p4).  Although their
treatment also considers (lower) semi-continuous
functions (with "jumps", see wikipedia) as well as
strictly-continuous functions.  They also set (x1,y1)
to the origin without loss of generality.  (Note also
the small error in fig 2 which is not strictly lower
semi-continuous.)

Details of the attached PDF:

    filename  : glpk-sos2_02.pdf
    size      : 87 120 bytes
    format    : PDF document, version 1.4
    author    : Robbie Morrison <address@hidden>
    pages     : 2 x A4
    md5sum    : 222919f36890aa5ca9eda59687217f8e

Email me if you would like the native ooWriter 2.0
file used to produce this PDF.

Perhaps Xypron would like to put the file on his
unofficial GLPK website (or anyone else for that
matter).

References

  Croxton, Keely L, Gendon, Bernard, and Magnanti,
      Thomas L.  2002.  A comparison of mixed-integer
      programming models for non-convex piecewise
      linear cost minimization problems.  Massachusetts
      Institute of Technology Operations Research
      Center Working Paper OR 363-02

      URI: http://hdl.handle.net/1721.1/5233
      PDF: OR-363-02.pdf (712kiB)

with best wishes
Robbie
---
Robbie Morrison
PhD student -- policy-oriented energy system simulation
Technical University of Berlin (TU-Berlin), Germany
University email (redirected) : address@hidden
Webmail (preferred)           : address@hidden
[from IMAP client]

glpk-sos2_02.pdf
Description: Adobe PDF document