|
From: | usa usa |
Subject: | Re: [Help-glpk] Formulate a large scale linear programing model by reducing the number of similar constraints and keeping them all satisfied |
Date: | Sun, 4 Sep 2016 12:24:51 -0400 |
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
T + SUM K_j <= SUM Q*P_i*X_i
j i
SUM E_i*X_i <= D*SUM E_i
i i
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'm not sure I got it right.
On Thu, 1 Sep 2016, usa usa wrote:
Also, in my LP model, each constraint will introduce a new decision
variable.
That makes it trickier. Look up column generation.
decVarK_j >= decVarX_i * constValue_i - decVarT
Did you mean decVarK_j >= decVarX_i * constValue_j_i - decVarT ?
If I used the solutions from solving the model with part of the constraints
and then replace the "decVarX_i" and "decVarT" with the solution values and
set
decVarK_j = decVarX_i * constValue_i - decVarT
Did you mean decVarK_j = SUM decVarX_i * constValue_j_i - decVarT ?
i
If decVarK_j is in the current LP, use that value.
Traditionally, values of non-explicit variables are often zero,
though other computations are possible.
Will most of the K_j's be zero?
If not, most of the j-indexed constraints will be active.
In that case, you would still want an algorithm that
does not do as much work as solving the entire LP at once.
I have an idea, but will not guarantee it will work.
If you use max(0, decVarX_i * constValue_j_i - decVarT) ,
all the nonzero decVarK_j's are likely to change with every iteration.
That said, for every feasible solution, changing each decVarK_j to
max(0, decVarX_i * constValue_j_i - decVarT)
will preserve feasibility and optimality.
Also note that the set of explicit j indices need not be contiguous.
1..N subsetof explicitIndices subsetof 1..L is sufficient.
decVarT + sum of (decVarK_j ) from j=1 to L <= [sum of
(constantValueP_i * decVarX_i) from i=1 to N ] * constantQ
T + SUM K_j <= SUM Q*P_i*X_i
j in 1..L i in 1..N
correct?
As noted earlier, you are in the realm of column (variable) generation.
There is a feasible solution with all the K_j's fixed at zero.
It might not be optimal.
Pricing the K_j's to determine which should become
nonzero is an important aspect of column generation.
--
Michael address@hiddenedu
"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] |