[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] Formulate a large scale linear programing model by reduc
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 20: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:19 PM, Michael Hennebry <
address@hidden> wrote:
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
Line wrap made a bit of a mess of the D constraints:
T + SUM (SUM V_j_i*X_i - T) <= SUM Q*P_i*X_i
j in S i in 1..N i in 1..N
for all S subsetof 1..L
This is 2**L constraints.
One constraint for each subset of 1..L .
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 are 2**L D constraints,
one for each subset of 1..L .
You have N+1 decision variables.
N+1 tight constraints are sufficient to define any basic solution,
including any basic optimal solution.
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 ? *
Yes.
--
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
- Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied, (continued)
- Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied, usa usa, 2016/09/01
- Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied, Michael Hennebry, 2016/09/02
- Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied, Michael Hennebry, 2016/09/08
- Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied, usa usa, 2016/09/08
- Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied, Michael Hennebry, 2016/09/08
- Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied, usa usa, 2016/09/08
- Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied,
Michael Hennebry <=
- Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied, usa usa, 2016/09/08