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 12-12-2017 07:18 PM
(1880 views)

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.;

1 ACCEPTED SOLUTION

Accepted Solutions

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

Yes, this looks correct to me.

7 REPLIES 7

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

Yes, this looks correct to me.

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

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Hi!

The attached version incorporates the cardinality constraint of 35 apples per bag, which I had omitted. Unfortunately no solution is found with the new formulation after several minutes.

**Don't miss out on SAS Innovate - Register now for the FREE Livestream!**

Can't make it to Vegas? No problem! Watch our general sessions LIVE or on-demand starting April 17th. Hear from SAS execs, best-selling author Adam Grant, Hot Ones host Sean Evans, top tech journalist Kara Swisher, AI expert Cassie Kozyrkov, and the mind-blowing dance crew iLuminate! Plus, get access to over 20 breakout sessions.

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.