[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] convex objective function, linear integer constraints
From: |
Peter T. Breuer |
Subject: |
[Help-glpk] convex objective function, linear integer constraints |
Date: |
Thu, 19 Jul 2007 19:13:33 +0200 (MET DST) |
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?
Peter
- [Help-glpk] convex objective function, linear integer constraints,
Peter T. Breuer <=