Please review my answers below. thanks
On Tue, Sep 6, 2016 at 2:14 PM, Michael Hennebry < [email protected]> wrote: > Let us name the constraints. > > On Sun, 4 Sep 2016, usa usa wrote: > > 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 >>> >> > Constraint A: > >> T + SUM K_j <= SUM Q*P_i*X_i >>> j i >>> >> > Constraint B: > >> SUM E_i*X_i <= D*SUM E_i >>> i i >>> >> > Constraints C_1 ... C_L > >> 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 >>> >> > 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 ?* >> > > Is this supposed to be constraint C_j ? > * A: yes* > Is E suposed to be there? Should it have an index? > * A : E is a typo and it should not be there.* > > 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) , >>> >> > Should have been max(0, SUM decVarX_i*constValue_j_i - decVarT) > i > Doesn't help. > > 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 ? * >> > > I do not know that you can. > That was more or less the point. > When one does column generation, > one usually arranges for the unmentioned variables to be zero. > To do column generation, you will need to reformulate without the K_j's. > Replace them with something that you expect to be mostly zero. > You will almost certainly need to represent nonzero variables. > > I suspect that with a bit of algrebra one > could get rid of the K_j's and T altogether. > That would leave the X_i's as the remaining variables. > The price would be an exponential number of constraints. > * A: "an exponential number of constraints." will cause "run out of memory" error ? * I'd expect the task of finding the most > violated constraint to not be very difficult. > > > -- > 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
