On Thu, Sep 8, 2016 at 1:23 AM, Michael Hennebry <
[email protected]> 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 [email protected]
> "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
>
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk
