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

- 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
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-12-2017 07:18 PM

Hi all:

We have a mathematical programming problem which can be briefly described like this:

We have a total of 2000 apples and need to select some of them for assignment to 10 bags. The following constraints/objective function need to be satisfied:

1. Constraint: An apple is assigned to no more than one bag.

2. Constraint: The total number of apples in each bag is 35.

3. Objective function: The total weight of the apples in each bag is as close to 25 lbs as possible.

Clearly, this is an assignment problem which needs to be solved using binary decision variables (We use i to index apples and use j to index bags). In PROC OPTMODEL, the first two constraints are very easy to formulate with binary decision variables.

The main issue is with the objective function which asks the total weight of apples be as close to 25 lbs as possible (i.e., minimize the deviation from 25 on both sides: 1) minimization of surplus from 25 and 2) minimization of slack from 25). We plan to implement an ABSOLUTE VALUE operation on this objective function: Within each bag j: | summation of (values of decision variables * weight of all apples) - 25| should be as small as possible (i.e., absolute value should be as close to zero as possible). Therefore, the objective function is nonlinear in the decision variables due to the absolute value operation.

As of SAS/OR 14.2, PROC OPTMODEL cannot directly handle INTEGER decision variables in a NONLINEAR objective function. We need to linearize this objective function. After consulting around, we got the following code. Wondering if it is correct for our purpose? Any insights will be highly appreciated: Thank you so much!

%let TotalBags=10; /*Total number of bags*/

%let TotalApples=2000; /*Total number of apples*/

%let number_Apple_Goal=35; /*Goal on the number of apples assigned to each bag*/

%let weight_Apple_Goal=25; /*Goal on the weight of apples assigned to each bag*/

set bags = **1..**&TotalBags.;

set apples = **1..**&TotalApples.;

number apple_weight {apples};

var bagApples{apples, bags} binary; /*Decision variables on which apples are assigned to which bags*/

con no_twobags {i in apples}: sum {j in bags} bagApples[i,j] <= **1**; /*No apple is selected for more than one bag*/

con total_apples_bag {j in bags}: sum {i in apples} bagApples[i,j] = &number_Apple_Goal.; /*Goal on the number of apples in a bag*/

var surplus {bags} >= **0**;

var slack {bags} >= **0**;

min obj_abs_weight_goal = sum {j in bags} (surplus[j] + slack[j]);

con obj_to_con_goal {j in bags}: sum {i in apples} bagApples[i,j] * apple_weight[i] - surplus[j] + slack[j] = &weight_Apple_Goal.;

Accepted Solutions

Solution

12-14-2017
11:42 AM

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

Posted in reply to PatrickYang

12-12-2017 07:25 PM

Yes, this looks correct to me.

All Replies

Solution

12-14-2017
11:42 AM

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

Posted in reply to PatrickYang

12-12-2017 07:25 PM

Yes, this looks correct to me.

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

Posted in reply to RobPratt

12-13-2017 12:14 PM

Hi Rob:

Thank you so much! Your response is always helpful.

In fact, one of my team members is wondering about two things:

1. min obj_abs_weight_goal = sum {j in bags} (surplus[j] + slack[j]); Why is the objective function the way it is? My understanding is that, since both surplus and slack parameters are set up to be POSITIVE, the minimization of the summation of the two is equivalent to the minimization of both positive parameters to the extent that they are as close to zero as possible.

2. con obj_to_con_goal {j in bags}: sum {i in apples} bagApples[i,j] * apple_weight[i] - surplus[j] + slack[j] = &weight_Apple_Goal.; What does the summation of the last two terms (i.e., -surplus[j] + slack[j]) on the left-hand side of the equation do? My understanding is that, within each bag indexed by j, the total weight of all assigned apples minus the amount greater than 25, IF ANY (when this happens to bag j, slack for this bag = 0), plus the amount less than 25, IF ANY (when this happens to bag j, surplus for this bag = 0), should equal 25, the target weight for bag j.

Thank you so much, Rob.

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

Posted in reply to PatrickYang

12-13-2017 12:52 PM

Yes, that is the right idea. Both surplus[j] and slack[j] are nonnegative penalty variables for missing the target for bag j. At optimality, they will not both be positive because otherwise you could reduce both variables by the same amount and preserve satisfaction of the obj_to_con_goal[j] constraint while improving the objective function value.

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

Posted in reply to RobPratt

12-14-2017 11:43 AM

Thank you, Rob. Your response has helped our team solve a major issue and allowed us to proceed.

Also, thank you for making PROC OPTMODEL so user-friendly and powerful to use.

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

Posted in reply to PatrickYang

12-14-2017 02:36 PM

Hi!

You might be interested to know that the CLP procedure implements a bin packing constraint, specifically designed to tackle problems like this one. The constraint programming engine can even be invoked from the OPTMODEL procedure using "solve with clp", but the attached code would need to be translated. I have made the assumption that the optimal solution is attainable. Alternately, one can add an objective function, but that formulation took longer to find an inferior solution.

Thanks!

Lindsey

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

Posted in reply to lipury

12-15-2017 11:59 AM

Hi Lindsey:

Thank you for sharing with us this new option. It was unknown to us. We will work on understanding the code and see if we can fully implement it in our work. Hopefully, we can fully figure out the details of the code after going through the documentation. If not, we will respond to this message with the hope to check with you again. Thank you for the new insights!!!! :-)

Thank you for sharing with us this new option. It was unknown to us. We will work on understanding the code and see if we can fully implement it in our work. Hopefully, we can fully figure out the details of the code after going through the documentation. If not, we will respond to this message with the hope to check with you again. Thank you for the new insights!!!! :-)

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

Posted in reply to PatrickYang

12-15-2017 05:17 PM