tag:blogger.com,1999:blog-593563533834706486.post321296204809159219..comments2024-03-20T19:41:44.472-04:00Comments on Yet Another Math Programming Consultant: Sorting by MIPErwin Kalvelagenhttp://www.blogger.com/profile/09496091402502236997noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-593563533834706486.post-37362297973325656252011-10-17T16:13:19.598-04:002011-10-17T16:13:19.598-04:00replace the sort() constraint by y(i) >= y(j) f...replace the sort() constraint by y(i) >= y(j) for all i > j.<br /><br />In GAMS: <br />sort(i,j)$(ord(i)>ord(j)).. y(i) =g= y(j);<br /><br />I don't think this will cut off any fractional solutions, but may be it can help Gurobi creating better cuts.<br /><br />Here are the results with Gurobi:<br />n=100, old sort: 6.8 sec, new sort: 37.3 sec<br />n=150, old sort: 22.0 sec, new sort: >1000 sec<br /><br />So this does not seem to help (although 2 models is hardly proof).Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-86808270993315839772011-10-17T11:33:28.204-04:002011-10-17T11:33:28.204-04:00I have made some further tests with CPLEX 12.3, us...I have made some further tests with CPLEX 12.3, using a model with n = 1000, that is, we have 1 Million variables (+ the 1000 helper variables which are typically eliminated in the presolve phase), on an Intel dual core machine. I have tested with 3 different LP algorithms:<br /><br />Primal Simplex (CPLEX's automatic choice): 92 sec.<br />Barrier: 22 sec.<br />Network Simplex: 4 sec.<br /><br />I append the model again, having added some comments and the variable Sorted which has the same meaning as Erwins variable y.<br /><br /><br />#=============================DECLARATION<br /><br />param n := 500 integer;<br /><br />set INDEX := 1..n;<br /><br />param values{INDEX} := Uniform01(); # contains the unsorted values<br /><br />var Assign{INDEX,INDEX} >= 0; # assigns the (sorted) index i to the value with index j<br /><br />var Sorted{INDEX}; # helper variable: will contain the sorted values.<br /><br /><br />#==============================MODEL<br /><br /># this objective does the whole trick:<br /># by using i as a factor, the j with the greatest value will be assigned to the<br /># greatest index n, the second greatest value to index n-1 and so on<br />maximize obj: sum{i in INDEX, j in INDEX} Assign[i,j] * i * values[j];<br /><br /># the assignment constraints<br />subject to assign1{i in INDEX}: sum {j in INDEX} Assign[i,j] = 1;<br /><br />subject to assign2{j in INDEX}: sum {i in INDEX} Assign[i,j] = 1;<br /><br /># this constraint only computes the sorted array<br />subject to sorted_def{i in INDEX}: Sorted[i] = sum {j in INDEX} Assign[i,j] * values[j];<br /><br />#==============================SOLVE AND DISPLAY<br />solve;<br /><br />display values, Sorted;Michael Römerhttp://wior.wiwi.uni-halle.de/noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-45049220873604684282011-10-17T09:38:33.525-04:002011-10-17T09:38:33.525-04:00What would happen if you replaced the sort() const...What would happen if you replaced the sort() constraint by y(i) >= y(j) for all i > j? Of course it would make the model larger, but would it make the model easier to solve? Another idea: create an additional set of binary variables that are 1 if y(i+1) >= y(i) and 0 otherwise, then maximize the sum of these binary variables.Greg Glocknerhttps://www.blogger.com/profile/14964879286706089383noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-6298607455761661792011-10-17T09:30:05.589-04:002011-10-17T09:30:05.589-04:00Got it!Got it!Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-17927772756340725772011-10-17T09:29:08.497-04:002011-10-17T09:29:08.497-04:00Sorry, in the previous post I meant the factor i w...Sorry, in the previous post I meant the factor i which occurs in the objective function. You<br />could replace the i with any factor factor[i] as long as factor[i] > factor[i-1] for all i and factor[i] >= 0.<br /><br />The solver will always allocate the j with the maximum value[j] to the biggest factor since this has the greatest impact on the objective function (and so on...)Michael Römerhttp://wior.wiwi.uni-halle.de/noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-68962630647441068912011-10-17T09:17:31.698-04:002011-10-17T09:17:31.698-04:00Actually, I was shortly thinking about the same is...Actually, I was shortly thinking about the same issue, but the range of the values does not matter (even if the values are negative). It is only important that the factor, in this case j, is strictly ordered.Michael Römerhttp://wior.wiwi.uni-halle.de/noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-18109030650327257942011-10-17T09:04:58.785-04:002011-10-17T09:04:58.785-04:00Great! May be divide value[j] in obj by max of val...Great! May be divide value[j] in obj by max of values, so it also works for numbers > 1.Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-34719647513595740972011-10-17T08:49:44.508-04:002011-10-17T08:49:44.508-04:00Erwin,
I don't know much about GAMS, but I th...Erwin,<br /><br />I don't know much about GAMS, but I think I understand your model. <br /><br />I'd like to propose a "Sorting by LP" formulation for the same problem. It uses the objective function in a simple but effective way to obtain the correct assignment. <br /><br />Since the model basically forms a network model (leaving out the helper variables y which only facilitate the output), all continous variables take integer values in the optimal solution.<br /><br />Using this formulation, CPLEX 12.3 solves a problem with n = 500 within 5 seconds using the barrier solver using 2 threads.<br /><br />This is the model in AMPL / GMPL:<br /><br />param n := 500 integer;<br /><br />set INDEX := 1..n;<br /><br />param value{INDEX} := Uniform01();<br /><br />var assign{INDEX,INDEX} >= 0, <=1;<br /><br />var y {INDEX} ; <br /><br />maximize obj:<br /> sum{i in INDEX, j in INDEX} assign[i,j] * i * value[j];<br /><br />subject to assign1{i in INDEX}:<br /> sum {j in INDEX} assign[i,j] = 1;<br />subject to assign2{j in INDEX}:<br /> sum {i in INDEX} assign[i,j] = 1;<br /><br />subject to y_def{i in INDEX}:<br /> y[i] = sum {j in INDEX} assign[i,j] * j;<br /><br />solve;<br /><br />display y;Michael Römerhttp://wior.wiwi.uni-halle.de/noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-71982338715617613282011-10-17T00:55:13.875-04:002011-10-17T00:55:13.875-04:00The second issue is probably a result of the first...The second issue is probably a result of the first one.Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-36602763621141812092011-10-16T21:57:17.134-04:002011-10-16T21:57:17.134-04:00I am glad that I never tried to learn GAMS :) can&...I am glad that I never tried to learn GAMS :) can't understand anything from the code.Anonymousnoreply@blogger.com