|
From: | Michael Hennebry |
Subject: | Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied |
Date: | Thu, 8 Sep 2016 12:19:30 -0500 (CDT) |
User-agent: | Alpine 1.00 (DEB 882 2007-12-20) |
On Thu, 8 Sep 2016, usa usa wrote:
On Thu, Sep 8, 2016 at 1:23 AM, Michael Hennebry < address@hidden> 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. 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. 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 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
[Prev in Thread] | Current Thread | [Next in Thread] |