Re: [Help-glpk] Hi: Question. Please help.

[Andrew Makhorin]

>> I am trying to use GLPK in a flux-balance analysis context in biology.
>> Once the linear constraints are defined and maximization of the
>> objective function is done, I often find that the solution contains too
>> many changes across the free variable set, and I cannot change that many
>> variables (over 1000 sometimes) for my engineering problem. I can at the
>> most take care of say a 15-20. How can I restrict the number (not
>> magnitude) of changes in the LP maximization?

> You may try solving your problem in two stages as follows. On the first
> stage you solve your original problem as usual. And on the second stage
> you fix the objective function at the optimal value found on the first
> stage (or limit it by some percentage of its optimal value) and then
> minimize the sum of |b[i]|, where b[i] are free variables. In LP context
> sum |b[i]| can be replaced by sum(b1[i] + b2[i]), where b1[i] and b2[i]
> are non-negative, and b1[i] - b2[i] = b[i].

> Sorry.. I've probably misunderstood this. Let's take 
> -3=5-8, 
> 5>=0, 8>=0,
> but 
> |-3|<>5+8

In that context b1[i] and b2[i] cannot be non-zero at the same time,
because either b1[i] or b2[i] (or both) is always non-basic in any
optimal basic solution.

This only works if the objective is the following:

   z = sum |b[i]|

and has to be minimized. Since the objective is separable, piecewise
linear and convex, it can be replaced by

   z = sum (b1[i] + b2[i]),

with additional equality constraints

   b[i] = b1[i] - b2[i],

where it is assumed that b[i] is free, b1[i] >= 0, b2[i] >= 0.

Obviously, if both b1[i] and b2[i] are basic, corresponding basic
solution cannot be dual feasible. Therefore, either b1[i] or b2[i]
or both should be non-basic.