BookmarkSubscribeRSS Feed
🔒 This topic is solved and locked. Need further help from the community? Please sign in and ask a new question.
Obsidian | Level 7


I am trying to solve a simple implementation of a knapsack problem. My objective is to select maximum units of a plan keeping it constrained to the budget and an average cost. Data looks like this.


**Please let me know if you need any other information.


Network Daypart  Selling ID  Spot_ids Dollars New_budget cost
CBS Primetime 20110 22212 348 350 25.00
CBS Primetime 20112 22213 365 350 25.69
CBS Early Fringe 20113 22214 380 750 35.00
CBS Early Fringe 20113 22215 380 750 38.50
CBS Early Fringe 20114 22216 375 750 22.50
ABC Daytime 30110 22217 290 1500 23.00
ABC Daytime 30110 22218 290 1500 25.00
ABC Daytime 30110 22219 290 1500 28.00
ABC Daytime 30112 22220 545 1500 32.50
ABC Daytime 30113 22221 548 1500 36.48
ABC Primetime 30114 22222 650 1000 42.50
ABC Primetime 30114 22223 650 1000 25.90
ABC Primetime 30115 22224 679 1000 33.30




Optimization Code:

proc optmodel;
		   /* declare variables */
			set <str> SPOT_IDS;

			num Dollars {SPOT_IDS};
			num cost {SPOT_IDS};

/*Value is a value assinged to each unique Spot_id. For now it's all equal to 1*/
			num Value {SPOT_IDS};

/*Data temp is a small subset of entire dataset. It is one Network and 1 daypart at a time processing to reach to the new desired budget amount*/

			read data temp into SPOT_IDS = [Spot_Ids] Dollars cost Value;

			/* declare variables, objective, and constraints */
			var NumSelected {SPOT_IDS} binary;

			/*Objective Function*/
			max TotalValue = sum {i in SPOT_IDS} Dollars[i] * NumSelected[i];

			/*Budget Constraint*/
			con budgetCon:
      			sum {i in SPOT_IDS} Dollars[i] * NumSelected[i] <= New_Budget;

/*Cost Constraint*/
/***** Need help with this****/
/*****I need to average over i****/
/*****Cost Lower bound and Upper bound is the average Cost per Network Daypart multiplied with 0.75 for lower bound and 1.25 for upper bound*****/

			con costCon:

			&Cost_LB_per_Bucket <= (avg{i in SPOT_IDS} cost *  NumSelected[i]) <= &Cost_UB_per_Bucket;*/

		   /* call mixed integer linear programming (MILP) solver */
		    solve with MILP/RELOBJGAP=&RelGap;

		/*create result in form of a dataset*/
			create data results_iter1 from
		        [Spot_Ids] = {i in SPOT_IDS}
		        selected_units_prop_dp = NumSelected [i]
		        Dollars= Dollars [i]





1. Is this the right way of handling this problem?

2. Also how can I average over a sample without making it non linear? A simple sum over count makes it a non linear constraint. If it is a non linear constraint solving it using 'NLP' gives an error too.


Accepted Solutions

You can linearize such a ratio constraint by clearing the denominator.  Look for "ratio constraint" in this book of examples in the SAS/OR documentation.

View solution in original post


You can linearize such a ratio constraint by clearing the denominator.  Look for "ratio constraint" in this book of examples in the SAS/OR documentation.

Obsidian | Level 7

Oh I feel so dumb. This was so simple. Thanks a lot. And the resource is really helpful too. Smiley Happy


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.


Register now!

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.

Discussion stats
  • 2 replies
  • 2 in conversation