topic Re: PROC OPTMODEL for Nonlinear Integer Optimization - HELP!!!! in Mathematical Optimization, Discrete-Event Simulation, and OR

PROC OPTMODEL for Nonlinear Integer Optimization - HELP!!!!

PatrickYang — Wed, 13 Dec 2017 00:18:28 GMT

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

Re: PROC OPTMODEL for Nonlinear Integer Optimization - HELP!!!!

RobPratt — Wed, 13 Dec 2017 00:25:43 GMT

Yes, this looks correct to me.

Re: PROC OPTMODEL for Nonlinear Integer Optimization - HELP!!!!

PatrickYang — Wed, 13 Dec 2017 17:14:10 GMT

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.

Re: PROC OPTMODEL for Nonlinear Integer Optimization - HELP!!!!

RobPratt — Wed, 13 Dec 2017 17:52:22 GMT

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.

Re: PROC OPTMODEL for Nonlinear Integer Optimization - HELP!!!!

PatrickYang — Thu, 14 Dec 2017 16:43:59 GMT

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.

Re: PROC OPTMODEL for Nonlinear Integer Optimization - HELP!!!!

lipury — Thu, 14 Dec 2017 19:36:17 GMT

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

Re: PROC OPTMODEL for Nonlinear Integer Optimization - HELP!!!!

PatrickYang — Fri, 15 Dec 2017 16:59:04 GMT

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!!!! 🙂

Re: PROC OPTMODEL for Nonlinear Integer Optimization - HELP!!!!

lipury — Fri, 15 Dec 2017 22:17:36 GMT

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.