tag:blogger.com,1999:blog-593563533834706486.post6178221035296013233..comments2024-03-28T10:35:10.453-04:00Comments on Yet Another Math Programming Consultant: An assignment problem with a wrinkleErwin Kalvelagenhttp://www.blogger.com/profile/09496091402502236997noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-593563533834706486.post-7057147273991289102021-01-27T21:29:04.445-05:002021-01-27T21:29:04.445-05:00Assuming you encoded the graph object directly fro...Assuming you encoded the graph object directly from the data (rather than creating a list of edges and then reading into a graph library), then you would just want to look at the time for the shortest path solve. I got around 0.3 seconds. I don't expect decent implementations of single s-t Dijkstra's in C/C++/Java to vary that much. So, I would expect your time to be in the ballpark. Unless it exploits acyclic digraph, then maybe it could be a little bit faster.matthew.galati@gmail.comhttps://www.blogger.com/profile/09122430479964389895noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-42356528652116336342021-01-27T21:26:10.302-05:002021-01-27T21:26:10.302-05:00Yes. Using a network solver would be pretty fast t...Yes. Using a network solver would be pretty fast too (for the solve). But, there will be a lot of overhead to first find the network embedding from the matrix, translate the matrix into a graph and then, of course, network simplex is going to be much slower than a pure shortest path algorithm. Network simplex (a flow formulation) is definitely overkill here.matthew.galati@gmail.comhttps://www.blogger.com/profile/09122430479964389895noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-22907309115169358522021-01-27T21:12:42.794-05:002021-01-27T21:12:42.794-05:00Interesting. I have not used these type of algorit...Interesting. I have not used these type of algorithms a lot, so this is let's say educational for me.Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-14075407559578109372021-01-27T21:05:58.372-05:002021-01-27T21:05:58.372-05:00I tried to pass it on to Cplex as an LP (and then ...I tried to pass it on to Cplex as an LP (and then solve it with the network solver). I should feed it directly into a shortest path algorithm.Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-23164415699977358822021-01-27T20:02:15.562-05:002021-01-27T20:02:15.562-05:00I think since the graph is directed acyclic, you c...I think since the graph is directed acyclic, you can do better than Dijkstra's (utilizing topological sort). But, I have not implemented that yet. It's on my ToDo list.<br /><br />In any case, the bulk of the time will be building the graph in memory.matthew.galati@gmail.comhttps://www.blogger.com/profile/09122430479964389895noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-91738674385621596632021-01-27T20:00:35.509-05:002021-01-27T20:00:35.509-05:00Hi Paul.
In this case, the threading is only for...Hi Paul. <br /><br />In this case, the threading is only for reading the input data (from a table of links) and building the graph data structures. That is ~2.9 seconds.<br /><br />Dijkstra's runs single-threaded here (since there is only one source) and takes 0.31 seconds. <br /><br />OPTNETWORK: https://go.documentation.sas.com/?cdcId=pgmsascdc&cdcVersion=v_008&docsetId=casnopt&docsetTarget=casnopt_optnet_overview.htm&locale=enmatthew.galati@gmail.comhttps://www.blogger.com/profile/09122430479964389895noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-91147229152087874982021-01-27T19:52:29.901-05:002021-01-27T19:52:29.901-05:00Interesting. We seem to match pretty closely on re...Interesting. We seem to match pretty closely on real time. I'm using an ordinary HP desktop, and I think the graph library I'm using is single threaded -- definitely not 16 threads, I don't have that many cores -- so I'm surprised my time is competitive. My graph is also a bit smaller (but not much).Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-62278166790053969742021-01-27T19:48:31.839-05:002021-01-27T19:48:31.839-05:00I just wrote some Java code to use a purely graph ...I just wrote some Java code to use a purely graph model, but it's a bit more compact -- basically what Erwin has in his comment. For a 100 x 1000 test case, the graph has roughly 90 thousand nodes and 40.2 million arcs. I get the optimal solution in about 3.5 seconds (including both graph construction and finding the shortest path). I ran some smaller examples against the MIP model from this post and confirmed that the objective values are correct. I'm hoping to post details in the next day or so on my blog.Paul A. Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-3113281976938772072021-01-27T19:35:55.144-05:002021-01-27T19:35:55.144-05:00Solves quickly with Dijkstra on my laptop.Solves quickly with Dijkstra on my laptop.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-52179432744756359032021-01-27T19:32:14.669-05:002021-01-27T19:32:14.669-05:00That worked quite nicely.
NOTE: ----------------...That worked quite nicely. <br /><br />NOTE: -----------------------------------------------------------------------------------------<br />NOTE: -----------------------------------------------------------------------------------------<br />NOTE: Running OPTNETWORK.<br />NOTE: -----------------------------------------------------------------------------------------<br />NOTE: -----------------------------------------------------------------------------------------<br />NOTE: Reading the links data.<br />NOTE: Data input used 1.32 (cpu: 5.87) seconds.<br />NOTE: Building the input graph storage used 1.59 (cpu: 14.16) seconds.<br />NOTE: The number of nodes in the input graph is 94953.<br />NOTE: The number of links in the input graph is 44601302.<br />NOTE: Processing shortest paths problem using 16 threads across 1 machines.<br />NOTE: Processing the shortest paths problem between 1 source nodes and 1 sink nodes.<br /> Real<br /> Algorithm Sources Complete Time<br /> shortestPath 1 100% 0.31<br />NOTE: Processing the shortest paths problem used 0.31 (cpu: 0.31) seconds.<br />NOTE: The Cloud Analytic Services server processed the request in 3.509987 seconds.<br />NOTE: The data set SASCAS1.OUT has 101 observations and 6 variables.<br />NOTE: PROCEDURE OPTNETWORK used (Total process time):<br /> real time 3.56 seconds<br /> cpu time 0.04 seconds<br />matthew.galati@gmail.comhttps://www.blogger.com/profile/09122430479964389895noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-9751918664456407622021-01-27T19:08:17.981-05:002021-01-27T19:08:17.981-05:00I tried this. Seems to work for small instances. T...I tried this. Seems to work for small instances. The big one is still big. Too large for me to solve on my laptop (90k nodes, 4e7 arcs).Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-70414969854130355682021-01-27T19:02:18.256-05:002021-01-27T19:02:18.256-05:00Yes, that smaller network seems correct: arc from ...Yes, that smaller network seems correct: arc from source to (1,j) with cost a(1)b(j), arc from (i,j) to (i+1,k), where, j < k, with cost a(i+1)b(k), and arc from (m,j) to sink with cost 0.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-522447427872538662021-01-27T18:50:10.920-05:002021-01-27T18:50:10.920-05:00This comment has been removed by the author.Rob Pratthttps://www.blogger.com/profile/16525877394541155854noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-91833091403303718262021-01-27T14:06:37.643-05:002021-01-27T14:06:37.643-05:00Can we not just have node(i,j) -> n(i+1,j+k) fo...Can we not just have node(i,j) -> n(i+1,j+k) for k=1,2,... Each incoming (or each outgoing) arc has a cost a(i)/b(j).Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-66889603133486865412021-01-27T11:01:23.518-05:002021-01-27T11:01:23.518-05:00That is truly a large network. I am sure I have ne...That is truly a large network. I am sure I have never solved an LP of this size, but may be a shortest path algorithm can handle this. Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-46011608540310580022021-01-27T10:31:59.789-05:002021-01-27T10:31:59.789-05:00My colleague (and regular commenter on this blog) ...My colleague (and regular commenter on this blog) Rob Pratt suggested a purely graph model:<br /><br />Node(i,j,k), where (j < k) indicates that a_i is assigned to b_j and a_{i+1} is assigned to b_k. The main arcs are (i,j,k)->(i+1,k,\ell) with k < \ell and cost a_{i+1} b_k. The arc from a dummy source node to (1,j,k) picks up the initial cost a_1 b_j + a_2 b_k, and the cost from the last real node (m-1,j,k) to a dummy sink node is 0. The the problem is to find the shortest path from the dummy source to the sink in a directed acyclic graph. For the large model that is 50 million nodes and 2.5 billion arcs. It would take a lot more memory than the milp, but I think it would be faster.<br />pihttps://www.blogger.com/profile/00954503509976411806noreply@blogger.com