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

[usa usa]

On Thu, Sep 8, 2016 at 1:23 AM, Michael Hennebry <address@hidden> wrote:

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 }

  A: Another thought, suppose that L= 1000, in the first iteration, we find that 500 K_j violated, we choose 100 most violated constraints of them as  new constraints :

              K_j >= SUM V_j_i*X_i - T       j in 1..100 (assume that j=1..100 are most violated and j =1...500 are all the violated constraints)

 After solving the new LP model with new added constraints, we may find that some of the original K_j for j =501 to 1000 may become violated. So, how to assure that the number of violated constraints reducing efficiently is a bottle neck problem.

Any help would be appreciated.

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