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

[Michael Hennebry]

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