sci.op-research

On 2007-11-15 00:27:26 -0400, dontemailme408@gmail.com said:

> On Nov 14, 6:08 am, marko.suonp...@24net.zzn.com wrote:
>> Is it easy to include restriction that only one of two variables in LP
>> problem can be > 0? There would be many such pairs. Currently I am
>> using revised simplex to solve the problem, but obviouslly without the
>> mentioned restriction.
>>
>> Br, Marko
>
> Since no else has mentioned it, I'll suggest that the original poster
> look into the subjects of "Linear Complementarity Problems" and
> "Mathematical Programs with Equilibrium Constraints." These classes
> of problems include the kinds of complementarity constraints mentioned
> in the original posting.
>
> It's possible that the original poster's problem is or can be put into
> the form of an LCP:
>
> Given an matrix n by n matrix M and an n element vector w, find
> vectors q and w such that
>
> q=w-Mz
> x_i * z_i = 0 i=1, 2, ..., n
> w>=0
> z>=0
>
> LCP's are not linear programming problems and most LP software can't
> solve LCP's, but there are other specialized algorithms for the
> solution of LCP's.
>
> There's also been a lot of interest in recent years in modeling and
> algorithms for mathematical programs with equilibrium constraints
> (MPEC). This class of problems includes LCP's but is much more
> general. Algorithms for the solution of MPEC are a topic of current
> research interest.
>
> Brian Borchers
> Department of Mathematics
> New Mexico Tech
> Socorro, NM 87801

There are also some cases where the complementarity is not required for
the solution but can be shown to be true at the optimum. A simple case
of this is the minimization of the absolute value where one has separated
the variable into their negative and positive parts.

x = x_p - x_n, x_p * x_n = 0
abs ( x ) = x_p + x_n

Without the complemetarity the representation of x is not unique but
minimzing the absolute value will force one of the two components to
be zero. This is a special structure but most models are special in
some way and even sometimes in this way.