tag:blogger.com,1999:blog-593563533834706486.post2119658149436186871..comments2024-03-28T10:35:10.453-04:00Comments on Yet Another Math Programming Consultant: Assignment problem with a wrinkle formulated as a network problemErwin Kalvelagenhttp://www.blogger.com/profile/09496091402502236997noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-593563533834706486.post-32879327751573061002021-02-01T07:34:29.023-05:002021-02-01T07:34:29.023-05:00Don't worry. I was just thinking out loud.Don't worry. I was just thinking out loud.Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-79188400118814286542021-01-31T20:59:54.669-05:002021-01-31T20:59:54.669-05:00Are you asking how to enumerate all possible paths...Are you asking how to enumerate all possible paths? <br /><br />Or, are you asking how the shortest path algorithm is so fast - which obviously does not do full enumeration? <br /><br />The standard approach uses Dijkstra's algorithm which is O(m + n log n). The specialized algorithm for a DAG uses topological sort and then a labeling pass similar to Dijkstra and is O(m + n).matthew.galati@gmail.comhttps://www.blogger.com/profile/09122430479964389895noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-42871040531329527652021-01-31T17:51:02.989-05:002021-01-31T17:51:02.989-05:00Well, a lot less. Well, a lot less. Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-9011432217753948162021-01-31T17:38:22.124-05:002021-01-31T17:38:22.124-05:00That performance is mind-boggling. Not sure how to...That performance is mind-boggling. Not sure how to calculate the number of possible paths. Should be a little bit less than 1000^100. Erwin Kalvelagenhttps://www.blogger.com/profile/09496091402502236997noreply@blogger.comtag:blogger.com,1999:blog-593563533834706486.post-53653795608798215282021-01-31T11:11:15.487-05:002021-01-31T11:11:15.487-05:00I can reduce the time a bit by adding a special va...I can reduce the time a bit by adding a special variant of ShortestPath which takes advantage of the fact that we have a DAG. In this case, the user would need to tell the solver that the graph is acyclic. It will throw an error if it is not.<br /><br />Before --<br />NOTE: Processing the shortest paths problem used 0.31 (cpu: 0.31) seconds.<br /><br />After --<br />NOTE: Processing the shortest paths problem used 0.24 (cpu: 0.24) seconds.<br /><br /><br />matthew.galati@gmail.comhttps://www.blogger.com/profile/09122430479964389895noreply@blogger.com