sci.op-research

On Nov 15, 8:54 am, Gordon Sande wrote:
> On 2007-11-15 00:27:26 -0400, dontemailme...@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
Pardon me for being a pragmatist. But if he's working on a commercial
problem, why doesn't he just try MIP'ing it?

SteveM



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