Re: [Help-glpk] convex objective function, linear integer constraints

[Andrew Makhorin]

> I'm interested in maximising a certain convex objective function over a
> set of linear constraints. I want to find the x which maximises (or
> rather, the maximum value of)

>    MIN_j(MAX(0, a_j1 - x_1, x_1 - b_j1), ..., MAX(0, a_jN - x_n, x_n - b_jN))

> as vector x varies over a convex linearly bounded integer n-dim
> subspace.  The a_jk < b_jk are integer constants.

> In fact, x is usually constrained to a simple cube [a_j0,b_j0], and the
> expression above is a measure of the minimum distance to a set of n
> other cubes.

> The objective is piecewise linear, i.e. we know the derivative at any
> point on some edge of a simplex, and it keeps on going in that same
> direction along the edge.  Common sense says that the simplex algorithm
> ought to work, provided I can tell the solving algorithm the derivative
> of the objective whenever it asks (and the derivative is always a
> constant, locally).  Instead, in glpk, I seem to be restricted to giving
> the whole objective function as a linear function, which is too
> restricted for what I want.

> Is there a way out? Something like finding the controlling algrothm in
> the code base and modifying the bit that swaps out one face/plane for
> another in the simplex algorithm so that it uses the derivative info on
> the objective only?

Since the objective is piece-wise linear and convex, you can reformulate
the problem as follows:

minimize z
subject to
z >= 0
z >= aj_1 - x_1
z >= x_1 - bj_1
...
z >= aj_n - x_n
z >= x_n - bj_n

This is a pure lp, so it can be solved with the standard simplex method.

See also models cf12a.mod and cf12b.mod (in directory 'examples')
included in the glpk distribution.