help-glpk
[Top][All Lists]
Advanced

[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.






reply via email to

[Prev in Thread] Current Thread [Next in Thread]