SAS Optimization, and SAS Simulation Studio

turn on suggestions

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

Showing results for

Find a Community

Topic Options

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

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-14-2017 11:14 AM

Hello!

The problem is to assign a number of persons to 5 tasks while maximizing an objective using OPTMODEL. 10% or less of the persons can be assigned 2 tasks while the rest only 1. If the constraint of "no more than 2" can be set up this way,

con no_more_2 {i in persons}: sum {j in tasks} assign[i,j] <= 2;

how should I specify the constraint of "only <= 10% can be assigned 2 tasks?" I tried the following

con percent: sum {i in persons} (if sum {j in tasks}assign[i,j] > 0 then 1 else 0) <= 10%*total ;

It did not work and gave this message:

ERROR: The specified optimization technique does not allow nonlinear constraints.

Thank you for your help!

Accepted Solutions

Solution

06-20-2017
09:32 AM

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-16-2017 08:48 PM

Glad to help. Yes, please use IsTwo[i]. I edited my reply again to correct that.

All Replies

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-14-2017 11:55 AM - edited 06-16-2017 10:12 AM

You can do it by introducing binary variables as follows:

```
var IsTwo {persons} binary;
con no_more_2 {i in persons}: sum {j in tasks} assign[i,j] <= 1 + IsTwo[i];
con percent: sum {i in persons} IsTwo[i] <= 0.1*total ;
```

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-15-2017 04:15 PM

Hi Mr. Pratt,

Thanks so much for the help! I replaced

`con no_more_2 {i in persons}: sum {j in tasks} assign[i,j] <= 1 + IsTwo[i,j];`

`con percent: sum {i in persons} IsTwo[i] <= 10%*total ;`

` `

with

`con no_more_2 {i in persons}: sum {j in tasks} assign[i,j] <= 1 + IsTwo[i];`

`con percent {j in tasks}: sum {i in persons} IsTwo[i] <= 10%*total ;`

` `

It seems to have worked. Hope it is correct. An extended question. If I need to replace "total" with the total of persons who are assigned a task, guess it could be specified like this

`con percent: sum {i in persons} IsTwo[i] <= 10%*sum {i in persons} assign[i,j] ;`

But this dynamic way of defining the constraint does not wok. What am I missing? Thank you!

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-16-2017 10:12 AM - edited 06-16-2017 08:47 PM

Thanks for the correction of IsTwo[i,j] to IsTwo[i]. I edited my reply.

For the percent constraint, there is no reason to have a separate constraint for each j. If you use the EXPAND statement, you will see that the same constraint appears several times, once for each j.

Your revised constraint declaration has two errors:

1. Use 0.1 instead of 10%.

2. The j index is unknown.

Here's one way to model what you want:

```
con percent:
sum {i in persons} IsTwo[i] <= 0.1*sum {i in persons} (sum {j in tasks} assign[i,j] - IsTwo[i]);
```

The idea is that the expression in parentheses is 1 if person i is assigned to at least once task.

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-16-2017 07:41 PM

That is brilliant! Thank you!

Should I change IsTwo[i,j] to IsTwo[i]?

Should I change IsTwo[i,j] to IsTwo[i]?

Solution

06-20-2017
09:32 AM

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-16-2017 08:48 PM

Glad to help. Yes, please use IsTwo[i]. I edited my reply again to correct that.

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-27-2017 07:08 PM

Hi Mr. Pratt,

Sorry for the bother again. I don't think this solution works as planned. For example, if I put 2 instead of 0.1, I obtain about the same number of persons assigned 2 tasks as those 1 task. Can you please take another look at this?

Thank you!

Sorry for the bother again. I don't think this solution works as planned. For example, if I put 2 instead of 0.1, I obtain about the same number of persons assigned 2 tasks as those 1 task. Can you please take another look at this?

Thank you!

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-27-2017 08:06 PM

Please post the full code.

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-28-2017 10:58 AM

Here you go. The solution has about 24% of the persons assigned two tasks and 76% one. Is it a matter of precision? Thank you so much!

proc optmodel forcepresolve=1 presolver=3 fd=central misscheck;

performance details;

profile on percent=0.05;

set persons;

number id{persons}, x{persons}, cond1{persons}, cond2{persons};

read data test into

persons=[id] x cond1 cond2 ;

number sumX=sum{i in persons} x[i];

number target=0.1*sumX; /*targeting pool size information????*/

var assign {persons, 1..5} binary;

var isTwo {persons} binary;

set tasks = 1..5;

var surplus {tasks} >= 0;

var slack {tasks} >= 0;

min objabs = sum {j in tasks} (surplus[j] + slack[j]);

con obj_alt {j in tasks}: sum {i in persons} assign[i,j]* x[i] - surplus[j] + slack[j] = target;

con taskId {j in 1..5}: sum {i in persons} assign[i,j] = 100;

con no_more_2 {i in persons}: sum {j in 1..5} assign[i,j] <= 1 + isTwo[i];

con percent_1: sum {i in persons} isTwo[i] <= 0.22*sum {i in persons} (sum {j in 1..5} assign[i,j] - isTwo[i]);

con percent_1: sum {i in persons} isTwo[i] >= 0.18*sum {i in persons} (sum {j in 1..5} assign[i,j] - isTwo[i]);

con con_d1 {j in 1..5}: sum {i in persons} assign[i,j]* cond1[i] >= .10*100;

con con_d2 {j in 1..5}: sum {i in persons} assign[i,j]* cond1[i] <= .15*100;

con con_d3 {j in 1..5}: sum {i in persons} assign[i,j]* cond2[i] >= .10*100;

expand;

solve with milp obj objabs / absobjgap=0.001 primalin ;

create data output from [persons task] = {{i in persons}, {j in 1..5}} in=assign;

quit;

proc optmodel forcepresolve=1 presolver=3 fd=central misscheck;

performance details;

profile on percent=0.05;

set persons;

number id{persons}, x{persons}, cond1{persons}, cond2{persons};

read data test into

persons=[id] x cond1 cond2 ;

number sumX=sum{i in persons} x[i];

number target=0.1*sumX; /*targeting pool size information????*/

var assign {persons, 1..5} binary;

var isTwo {persons} binary;

set tasks = 1..5;

var surplus {tasks} >= 0;

var slack {tasks} >= 0;

min objabs = sum {j in tasks} (surplus[j] + slack[j]);

con obj_alt {j in tasks}: sum {i in persons} assign[i,j]* x[i] - surplus[j] + slack[j] = target;

con taskId {j in 1..5}: sum {i in persons} assign[i,j] = 100;

con no_more_2 {i in persons}: sum {j in 1..5} assign[i,j] <= 1 + isTwo[i];

con percent_1: sum {i in persons} isTwo[i] <= 0.22*sum {i in persons} (sum {j in 1..5} assign[i,j] - isTwo[i]);

con percent_1: sum {i in persons} isTwo[i] >= 0.18*sum {i in persons} (sum {j in 1..5} assign[i,j] - isTwo[i]);

con con_d1 {j in 1..5}: sum {i in persons} assign[i,j]* cond1[i] >= .10*100;

con con_d2 {j in 1..5}: sum {i in persons} assign[i,j]* cond1[i] <= .15*100;

con con_d3 {j in 1..5}: sum {i in persons} assign[i,j]* cond2[i] >= .10*100;

expand;

solve with milp obj objabs / absobjgap=0.001 primalin ;

create data output from [persons task] = {{i in persons}, {j in 1..5}} in=assign;

quit;

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-28-2017 12:30 PM

I see that you have declared the percent_1 constraint twice, so that should have generated an error.

Can you please also attach the test data set?

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-28-2017 05:04 PM

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

06-28-2017 06:38 PM

The formulation I suggested enforces only the implication "if person i is assigned two tasks then IsTwo[i] = 1," which is fine if you have only the percent_1 constraint. But the percent_2 constraint also requires the converse implication "if IsTwo[i] = 1 then person i is assigned two tasks." Otherwise, the solver can "cheat" by setting IsTwo[i] = 1 to help satisfy percent_2 even if person i is assigned fewer than 2 tasks. The code below implements a more robust formulation that enforces both implications. Notice that I used tasks instead of 1..5 throughout, and I also combined d1 and d2 into a range constraint.

```
proc optmodel;
set persons;
number id{persons}, x{persons}, cond1{persons}, cond2{persons};
read data test into
persons=[id] x cond1 cond2;
number sumX=sum{i in persons} x[i];
number target=0.1*sumX;
set tasks = 1..5;
var assign {persons, tasks} binary;
var surplus {tasks} >= 0;
var slack {tasks} >= 0;
min objabs = sum {j in tasks} (surplus[j] + slack[j]);
con obj_alt {j in tasks}: sum {i in persons} assign[i,j]* x[i] - surplus[j] + slack[j] = target;
con taskId {j in tasks}: sum {i in persons} assign[i,j] = 100;
set counts = 0..2;
var isCount {persons, counts} binary;
con onecount {i in persons}: sum {c in counts} isCount[i,c] = 1;
con isCountDef {i in persons}: sum {j in tasks} assign[i,j] = sum {c in counts} c*isCount[i,c];
con percent_1: sum {i in persons} isCount[i,2] <= 0.22*sum {i in persons} (1 - isCount[i,0]);
con percent_2: sum {i in persons} isCount[i,2] >= 0.18*sum {i in persons} (1 - isCount[i,0]);
con con_d1_d2 {j in tasks}: .10*100 <= sum {i in persons} assign[i,j]* cond1[i] <= .15*100;
con con_d3 {j in tasks}: sum {i in persons} assign[i,j]* cond2[i] >= .10*100;
solve;
put ((sum {i in persons} isCount[i,2]) / (sum {i in persons} (1 - isCount[i,0])));
num numTasks {i in persons} = round(sum {j in tasks} assign[i,j].sol);
put (card({i in persons: numTasks[i] = 2}) / card({i in persons: numTasks[i] > 0}));
create data output from [persons task] in=assign;
quit;
```

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

07-07-2017 03:44 PM

Thank you so much for the detailed reply! My apologies for being able to come back to this so late. As a novice, I do not quite follow your code, especially the part after "solve". What is more, at my end, the code would run forever before showing the "out of memory" message. Is there a setting I need to change to make it work? Thank you!

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

07-10-2017 12:03 PM - edited 07-10-2017 12:04 PM

Here are a few suggestions:

- Increase the MEMSIZE value, as discussed here.
- Use the MAXTIME= option to limit the time.
- Interrupt the solver when the log shows slow progress.
- Use the decomposition algorithm. The following code changes yielded a very good solution quickly for me:

```
for {i in persons} do;
onecount[i].block = i;
isCountDef[i].block = i;
end;
solve with milp / decomp;
```

The PUT and NUM statements after the SOLVE in the previous code display the ratio of people assigned two tasks to people assigned at least one task. The two PUT statements should show the same value in the log, and that value should be between 0.18 and 0.22, as enforced by the optimization model.

The CREATE DATA statement saves the values of the assign variable in the resulting solution to a SAS data set.

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Highlight
- Email to a Friend
- Report Inappropriate Content

07-11-2017 02:07 PM

Thanks for the cool solution! But it has been running for an hour on my computer. I have increased MEMSIZE (Intel i5 and 16G RAM). What else do I need to do? Thanks!