[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Hi: Question. Please help.
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] Hi: Question. Please help. |
Date: |
Fri, 1 Aug 2008 11:22:07 +0400 |
>> > 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
>>
> Is it such theorem?
This can be expressed as a theorem, if necessary.
Consider the problem:
minimize |x|
s.t. additional constraints
Obviously, it is equivalent to the following problem:
minimize z
s.t. z >= |x|
additional constraints
Inequality z >= |x| can be replaced by two equivalent inequalities:
z >= -x
z >= +x
Introducing slack non-negative variables x1 >= 0 and x2 >= 0 we have:
z = 2 * x1 - x
z = 2 * x2 + x
from which it follows that:
z = x1 + x2
x = x1 - x2
Therefore the problem can be formulated as follows:
minimize x1 + x2
s.t. x = x1 - x2
x1, x2 >= 0
additional constraints
>> 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.
> I know this subject not so good. Why is it so?
Which subject?
>> Therefore, either b1[i] or b2[i]
>> or both should be non-basic.
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- Re: [Help-glpk] Hi: Question. Please help.,
Andrew Makhorin <=