[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Piecewise linear objective functions

From: Ivo van Baren
Subject: Re: [Help-glpk] Piecewise linear objective functions
Date: Thu, 9 Aug 2007 11:54:57 +0200

Andrew and Hartwig,
Please find below a pointer to an interesting article that compares various formulations for non-convex piecewise linear cost functions. The formulation affects the run time of the usually hard to solve MIP models. Non-convex and concave cost functions occur quite often in supply chain modelling, e.g. transportation costs with scale/utilization effects.  
Croxton, K. L., Gendron, B. and Magnanti, T. L., "A comparison of mixed-integer programming models for non-convex piecewise linear cost minimization problems," Management Sci., v49, pp. 1268-1273, 2003.
Best regards,
Ivo van Baren

2007/8/9, Andrew Makhorin <address@hidden>:
> I would like to know if it is possible with GLPK to solve problems
> with a piecewise linear objective function.

It is possible. However, you need to reformulate your problem,
because glpk does not support non-linear objective and constraints.
A standard way to model a piecewise objective is using SOS2
constraints, which, in turn, can be modeled as follows:

> I currently work on a model for supply chain planning which uses a
> term in the objective funktion with is equal to zero as long as the
> value of a decision variable is greater than a given constant value,
> and wich is equal to the product of a cost constant and the
> difference of the constant and the decision variable.

> I use ILOG OPL Studio for developing the model and CPLEX for solving
> it.

Please note that glpk is much weaker than cplex in the sense of
ability to solve large or hard MIPs.

> Recently I got the hint to look for GLPK, so I made it running on my
> PC and ported the model. Everything is fine except the piecewise
> objective term.

> (In ILOG OPL I modeled it with a function within the objective
> function:

> maximize sum(...) ... + cost * maxl(0, constant - Variable);  )

> BTW: is there any GUI for GLPK which has similar functionality like
> OPL Studio for CPLEX?

Unfortunately, not.

Help-glpk mailing list

reply via email to

[Prev in Thread] Current Thread [Next in Thread]