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

[Michael Hennebry]

Let us name the constraints.

On Sun, 4 Sep 2016, usa usa wrote:

> On Fri, Sep 2, 2016 at 3:36 PM, Michael Hennebry <
> address@hidden> wrote:
>
> > 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

> > On Thu, 1 Sep 2016, usa usa wrote:
> >
> > Also, in my LP model, each constraint will introduce a new decision
> > > variable.
> >
> > That makes it trickier.  Look up column generation.
> >
> >     decVarK_j >= decVarX_i * constValue_i  - decVarT
> > >
> >
> > Did you mean decVarK_j >= decVarX_i * constValue_j_i - decVarT  ?
>
> *    A:  It means decVarK_j >=  SUM E ( decVarX_i * constValue_j_i for i in
> 1...N) - decVarT  ?*

Is this supposed to be constraint C_j ?
Is E suposed to be there?  Should it have an index?

> > If I used the solutions from solving the model with part of the constraints
> > > and then replace the "decVarX_i" and "decVarT" with the solution values
> > > and
> > > set
> > >
> > >      decVarK_j = decVarX_i * constValue_i  - decVarT
> >
> > Did you mean decVarK_j = SUM decVarX_i * constValue_j_i  - decVarT ?
> >                           i
> >
> >  *   A:  It means decVarK_j = SUM E( decVarX_i * constValue_j_i  for i in
> 1...N ) - decVarT ?*
>                                                      i
>
>
> > If decVarK_j is in the current LP, use that value.
> > Traditionally, values of non-explicit variables are often zero,
> > though other computations are possible.
> > Will most of the K_j's be zero?
>
> *    A:  No, the values of K_j depend on SUM E ( decVarX_i * constValue_j_i
> for i in 1...N) - decVarT *
>
>
> > If not, most of the j-indexed constraints will be active.
> > In that case, you would still want an algorithm that
> > does not do as much work as solving the entire LP at once.
> > I have an idea, but will not guarantee it will work.
> > If you use max(0, decVarX_i * constValue_j_i - decVarT) ,

Should have been max(0, SUM decVarX_i*constValue_j_i - decVarT)
                         i
Doesn't help.

> > all the nonzero decVarK_j's are likely to change with every iteration.
> > That said, for every feasible solution, changing each decVarK_j to
> > max(0, decVarX_i * constValue_j_i - decVarT)
> > will preserve feasibility and optimality.
>
>
>
>
> *   A: I do not quite understand this. For j=1 ... L, if in one iteration,
> I chose j =1 ... M with M is much smaller than L. For example, L = 100000,
> and M = 1000. So, in the LP model, I only have optimal solutions for the
> constraints of        decVarK_j >=  SUM E ( decVarX_i * constValue_j_i for
> i in 1...N)*
>
>
>
>
> *for j =1...M. *
>
> *How can I use the solutions for j=1...M to change each decVarK_j to max(0,
> decVarX_i * constValue_j_i - decVarT)  with j = 1... N ? *

I do not know that you can.
That was more or less the point.
When one does column generation,
one usually arranges for the unmentioned variables to be zero.
To do column generation, you will need to reformulate without the K_j's.
Replace them with something that you expect to be mostly zero.
You will almost certainly need to represent nonzero variables.

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.


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