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

[usa usa]

Hi, Michael,

Thanks for your answers.

Please check my answers and reviews below marked as bold.

Thanks

David

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

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  ?

    A:  It means decVarK_j >=  SUM E ( decVarX_i * constValue_j_i for i in 1...N) - 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

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

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?

   A: yes
 

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@hiddenedu
"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