Linear assignment problem of a migration using Proc Optmodel

[danbohac]

I'm new to SAS/OR and trying to solve a combinatorial optimization problem that similar to a LP scheduling problem.  I've drawn out the concept in graph form.

The idea is given an adjacency list that represent Graph1, find the order sequence of node moves from Graph1 to Graph2 to minimize the overall step cost of edges that return to Graph1. The number of nodes moved in each step could be variable to allow clusters of highly connected node to move together.  I've shown two sequences(Test 1 and Test 2) to show the difference order has on the sum of step costs.

I've evaluated the examples under proc clp and proc optmodel to see if I could create the minimum cost sequence.  Here is one example I've been attempting to adapt: http://support.sas.com/kb/37/488.html  I'm currently on SAS 9.22 which may be causing issue with the attempts to use proc clp given changes to the experimental procedure with 9.3.

Any help in showing an example or pointing to the correct procedure and problem formulation would be greatly appreciated.

Thanks,
Dan.

[Philipp_SAS]

Hi Dan,

A couple folks here at SAS/OR R&D looked into a problem like this a while back, I attached the formulation they came up with. The problem with this formulation is that MILP solvers will have a hard time solving these instances to optimality if you have big graphs. Then much more sophisticated algorithms would be needed, those can be done in OPTMODEL but require experts to look into the problem structure. I can post some simple greedy heuristic that can help at least find good solutions for larger graphs, if you are interested.

Philipp

[danbohac]

Philipp,

Thanks for response and example.  I ran the example and it promptly errored. 

I would be interested in seeing the simple greedy heuristic you mentioned.  Is this similiar to the MST problem where the alternative solution can be found using subtour formulation and iteratively adding subtour constraints?  I knew to scale up the solution I would probably need to break any larger graphs into part based on classifying certain patterns.

I appreciate you getting me on the right track and hopefully I can figure out what going on to crash the example.

Dan.

AppName: sas.exe AppVer: 9.21000.18765.32444 ModName: tkemilp.dll

ModVer: 9.21200.19075.28438 Offset: 0004ac44

I attached the log.

[Philipp_SAS · Accepted solution]

Hi Dan,

Sorry that my code crashed on you, I tried running it here on several machines and with several versions of SAS/OR but could not find any problem. I did notice that I left in the "primalin" option, depending on what version of SAS you are running that might be the problem. Otherwise, solving with slightly different edgedata might give you some code that is not running. Your log looks like it's not from the latest SAS/OR release (9.3), so upgrading sure would help. I attached a version of the code without primalin, see if it works.

I also attached a version of the code with a simple greedy heuristic my colleagues here came up with. For small examples it might find good or even optimal solutions. It then feeds in the solution into the MILP solver to improve it or to show that it is optimal. I don't think any kind of "row generation" approach like for TSP would work here. The difficulty is in expressing the cost for each step. The formulation does that correctly but uses many variables to do so. With bigger graphs the number of variables increases a lot and you will have slow solves and eventually run out of memory.

That said, maybe your underlying business problem can be tackled in a different way. SAS has some great consultants who might be able to help you with that.

Let me know how this works for you

Philipp

[danbohac]

Philipp,

Thanks for all your help!  The "primalin" fix worked and I'm also working on the 9.3 upgrade.  I noticed the greedy example actually took a little longer for the same example, but I need to test it on a larger set to see if this is always the case.  This is a great help in getting me to my end solution. 

Thanks,

Dan.