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

[Michael Hennebry]

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

T + SUM K_j      <=   SUM Q*P_i*X_i
     j                 i

SUM E_i*X_i <= D*SUM E_i
 i                i

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'm not sure I got it right.

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  ?

> 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

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?
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) ,
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.

Also note that the set of explicit j indices need not be contiguous.
1..N subsetof explicitIndices subsetof 1..L  is sufficient.

>     decVarT + sum of (decVarK_j ) from j=1 to  L  <=  [sum of
> (constantValueP_i  * decVarX_i)  from i=1 to  N ] * constantQ

T + SUM K_j   <=   SUM Q*P_i*X_i
   j in 1..L      i in 1..N

correct?

As noted earlier, you are in the realm of column (variable) generation.
There is a feasible solution with all the K_j's fixed at zero.
It might not be optimal.
Pricing the K_j's to determine which should become
nonzero is an important aspect of column generation.

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