[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] convex objective function, linear integer constraints
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] convex objective function, linear integer constraints |
Date: |
Fri, 20 Jul 2007 16:53:57 +0400 |
> 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.