Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Options

- RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

🔒 This topic is **solved** and **locked**.
Need further help from the community? Please
sign in and ask a **new** question.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Posted 08-07-2011 07:23 PM
(1427 views)

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.

1 ACCEPTED SOLUTION

Accepted Solutions

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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

4 REPLIES 4

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

📢

**ANNOUNCEMENT**

The early bird rate has been extended! Register by March 18 for just $695 - $100 off the standard rate.

Check out the agenda and get ready for a jam-packed event featuring workshops, super demos, breakout sessions, roundtables, inspiring keynotes and incredible networking events.** **

Multiple Linear Regression in SAS

Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.

Find more tutorials on the SAS Users YouTube channel.