Hi, Michael, Thanks for your answers.
Please check my answers and reviews below marked as bold. Thanks David On Fri, Sep 2, 2016 at 3:36 PM, Michael Hennebry < [email protected]> wrote: > 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 ? > * A: It means decVarK_j >= SUM E ( decVarX_i * constValue_j_i for i in 1...N) - 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 > > * A: It means decVarK_j = SUM E( decVarX_i * constValue_j_i for i in 1...N ) - 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? > * A: No, the values of K_j depend on SUM E ( decVarX_i * constValue_j_i for i in 1...N) - decVarT * > 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. > * A: I do not quite understand this. For j=1 ... L, if in one iteration, I chose j =1 ... M with M is much smaller than L. For example, L = 100000, and M = 1000. So, in the LP model, I only have optimal solutions for the constraints of decVarK_j >= SUM E ( decVarX_i * constValue_j_i for i in 1...N)* *for j =1...M. * *How can I use the solutions for j=1...M to change each decVarK_j to max(0, decVarX_i * constValue_j_i - decVarT) with j = 1... N ? * 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? > * A: yes* > 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 [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
