tag:blogger.com,1999:blog-593563533834706486.post8293428115501864058..comments2024-03-28T10:35:10.453-04:00Comments on Yet Another Math Programming Consultant: 2d knapsack problemErwin Kalvelagenhttp://www.blogger.com/profile/09496091402502236997noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-593563533834706486.post-16633235214400377882023-12-19T04:22:10.109-05:002023-12-19T04:22:10.109-05:00can you provide the code to display the output in ...can you provide the code to display the output in container form for the 3rd case(using cp-sat solver)?<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-27351502691805786292023-10-30T09:13:45.599-04:002023-10-30T09:13:45.599-04:00This is a two-dimensional cutting stock problem. T...This is a two-dimensional cutting stock problem. There is a body of literature about this problem.Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-76198317099559612272023-10-30T09:07:02.735-04:002023-10-30T09:07:02.735-04:00Problem: a timber warehouse has a bundle of assort...Problem: a timber warehouse has a bundle of assorted widths and lengths, thickness is uniform. A customer places an order for a number of boards of varying widths and lengths, thickness is uniform. Is there a mathematical solution or software which identifies the most efficient way of meeting the order from the available timber?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-69692406353042199082021-11-18T18:33:13.061-05:002021-11-18T18:33:13.061-05:00Last update. I have changed the name of the exampl...Last update. I have changed the name of the example to knapsack_2d_sat.py. And we have implemented support for floating point coefficients and offsets in the objective. See https://github.com/google/or-tools/blob/master/examples/python/knapsack_2d_sat.pyLaurent Perronhttps://www.blogger.com/profile/01233027642403281187noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-75620897610172115202021-11-14T17:17:19.055-05:002021-11-14T17:17:19.055-05:00I have rewritten the example, added a second model...I have rewritten the example, added a second model where the dimensions of the item depends on its state(not_selected, no_rotation, rotated).<br />In the meantime, I have added a linear relaxation to the no_overlap_2d constraint that makes your equation obsolete.<br />I have also implemented detection of possible linearization of the product of two affine expression, which is necessary to rebuild the linear term in the energetic redundant equation.<br /><br />This currently requires using the master branch of or-tools, while waiting for 9.2 to be released (hopefully this month).<br />With this version, I solve the problem much faster than the previous code.<br /><br />The example is available at: https://github.com/google/or-tools/blob/master/examples/python/packing_2d_sat.py<br />Laurent Perronhttps://www.blogger.com/profile/01233027642403281187noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-71854680620467545222021-10-14T11:05:53.868-04:002021-10-14T11:05:53.868-04:00So, the jupyter backend seems to be mono-core, or ...So, the jupyter backend seems to be mono-core, or close to.<br />Laurent Perronhttps://www.blogger.com/profile/01233027642403281187noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-33517435079787487172021-10-14T07:58:54.610-04:002021-10-14T07:58:54.610-04:00In the morning it seems a bit slower:
return code...In the morning it seems a bit slower:<br /><br />return code:4<br />status:OPTIMAL<br /><br />CpSolverResponse summary:<br />status: OPTIMAL<br />objective: 4617934<br />best_bound: 4617934<br />booleans: 444<br />conflicts: 1608380<br />branches: 1653210<br />propagations: 11072083<br />integer_propagations: 38767100<br />restarts: 1714<br />lp_iterations: 0<br />walltime: 331.133<br />usertime: 331.133<br />deterministic_time: 191.74<br />primal_integral: 347.965Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-68195189032717373412021-10-14T07:07:16.742-04:002021-10-14T07:07:16.742-04:00I did not print the version, but I see it installe...I did not print the version, but I see it installed: ortools-9.1.9490-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whlErwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-27312823549161716822021-10-14T07:01:36.280-04:002021-10-14T07:01:36.280-04:00Hi Laurent: that was my first formulation. I repla...Hi Laurent: that was my first formulation. I replaced it with a linear expression just because it was a little bit more compact. I ran it on colab.google.com. That may be a less "stable" environment (a small VM) than running it locally on a real machine. Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-38881724300280746652021-10-14T06:56:08.936-04:002021-10-14T06:56:08.936-04:00That is certainly confirmed for these models. Some...That is certainly confirmed for these models. Sometimes the covering formulation can lead to really, really big models.Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-76444395934193298472021-10-14T05:08:09.441-04:002021-10-14T05:08:09.441-04:00Using the old formulation does not change performa...Using the old formulation does not change performance. Which version of or-tools did you use ?Laurent Perronhttps://www.blogger.com/profile/01233027642403281187noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-16739593208547602372021-10-14T05:03:59.406-04:002021-10-14T05:03:59.406-04:00Hi,
I tweaked a little the model (not sure it he...Hi, <br /><br />I tweaked a little the model (not sure it helps)<br /><br />```for i in range(nr):<br /> model.Add(xw[i] == wr[i]).OnlyEnforceIf(u[i])<br /> model.Add(xw[i] == 0).OnlyEnforceIf(u[i].Not())<br /> model.Add(yh[i] == hr[i]).OnlyEnforceIf(u[i])<br /> model.Add(yh[i] == 0).OnlyEnforceIf(u[i].Not())<br />```<br /><br /><br />On my machine, it solves quite fast<br /><br />CpSolverResponse summary:<br />status: OPTIMAL<br />objective: 4617936<br />best_bound: 4617936<br />booleans: 592<br />conflicts: 30049<br />branches: 51905<br />propagations: 627691<br />integer_propagations: 670265<br />restarts: 237<br />lp_iterations: 24505<br />walltime: 6.20536<br />usertime: 6.20536<br />deterministic_time: 13.1242<br />primal_integral: 106.057<br /><br />return code:4<br />status:OPTIMAL<br /><br />CpSolverResponse summary:<br />status: OPTIMAL<br />objective: 4617936<br />best_bound: 4617936<br />booleans: 592<br />conflicts: 30049<br />branches: 51905<br />propagations: 627691<br />integer_propagations: 670265<br />restarts: 237<br />lp_iterations: 24505<br />walltime: 6.20536<br />usertime: 6.20536<br />deterministic_time: 13.1242<br />primal_integral: 106.057<br /><br /><br /> x y w h x2 y2 v<br />0 0 0 14 2 14 2 223516<br />1 0 2 14 2 14 4 223516<br />2 0 4 14 2 14 6 223516<br />3 14 18 14 2 28 20 223516<br />4 18 5 5 13 23 18 551072<br />5 23 5 5 13 28 18 551072<br />6 0 18 14 2 14 20 223516<br />7 0 6 18 6 18 12 755094<br />8 14 0 3 6 17 6 113436<br />9 17 0 13 5 30 5 551072<br />10 0 12 18 6 18 18 755094<br />11 28 5 2 14 30 19 223516<br />Laurent Perronhttps://www.blogger.com/profile/01233027642403281187noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-58096792595725548262021-10-12T13:15:23.432-04:002021-10-12T13:15:23.432-04:00Erwin, I looked at a similar model years ago. Desp...Erwin, I looked at a similar model years ago. Despite the larger size, the covering MIP far outperformed the "continuous size" model. I believe this is because the continuous size model depends on disjunctive constraints; in the LP relaxation, disjunctive constraints tend to spread the values to 1/n, so the LP relaxation gives poor information. If necessary, I believe you could improve the performance of the covering MIP via symmetry reduction and/or column generation.Greg Glocknerhttps://www.blogger.com/profile/14964879286706089383noreply@blogger.com