On Thu, Sep 8, 2016 at 1:19 PM, Michael Hennebry < [email protected]> wrote:
> On Thu, 8 Sep 2016, usa usa wrote: > > On Thu, Sep 8, 2016 at 1:23 AM, Michael Hennebry < >> [email protected]> wrote: >> > > 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: replacing K_j in Constraint A can reduce the number of constraints in >> the beginning, but how to reduce the size of D_S at each iteration so that >> the algorithm can be convergent. >> Otherwise, the number of violated "K_j >= SUM V_j_i*X_i - T j in >> 1..L" >> constraints cannot be reduced efficiently at each iteration. The model >> size >> is still large. >> > > Without the K's, you only have N+1 decision variables. > At optimiality, you will need at most N+1 of the D constraints. > * A: there is only one D constraint. Why N+1 ? * > There is no need to find all violated D constraints. > That you can find one if there is one is > sufficient to guarantee convergeance. > > No promises on how long convergeance will take. > Before optimialty, you might find a lot of most > violated constraints that are not needed at optimality. > Usually it is mathematically allowed to > drop a D constraint once it goes slack. > *A: "slack" means unbinding ? * Degeneracy can change that. > Drop a D constraint only if it is slack and the objective has > changed significantly since said constraint was last tight. > > > > -- > 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
