Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied

[Michael Hennebry]

On Tue, 6 Sep 2016, Michael Hennebry wrote:

> Let us name the constraints.

> > > First, I am unclear as to what the exact model is.
> > > This is what I got from yur first post:
> > >
> > > The i SUMs run from 1 to N.
> > > The j SUMs run from 1 to L.
> > >
> > >
> > > Max SUM P_i*X_i
> > >      i
>
> Constraint A:
> > > T + SUM K_j      <=   SUM Q*P_i*X_i
> > >      j                 i
>
> Constraint B:
> > > SUM E_i*X_i <= D*SUM E_i
> > >  i                i
>
> Constraints C_1 ... C_L
> > > K_j >= SUM V_j_i*X_i - T       j in 1..L
> > >         i
> > >
> > > T no explicit bound
> > > 0 <= X_i <= 1   i in 1..N
> > > 0 <= K_i        i in 1..L

> I suspect that with a bit of algrebra one
> could get rid of the K_j's and T altogether.
> That would leave the X_i's as the remaining variables.
> The price would be an exponential number of constraints.
> I'd expect the task of finding the most
> violated constraint to not be very difficult.

No need to get rid of T.
Getting rid of the K_j's is easy:
Replace Constraint A and constraints C with

D:
T +  SUM   (SUM V_j_i*X_i - T)  <= SUM Q*P_i*X_i   for all S subsetof 1..L
    j in S  i in 1..N

This is 2**L constraints.
For given values of X and T,
a most violated is D_S with S = { j in 1..L: SUM V_j_i*X_i - T > 0 }

--
Michael   address@hidden
"Sorry but your password must contain an uppercase letter, a number,
a haiku, a gang sign, a heiroglyph, and the blood of a virgin."
                                                             --  someeecards