topic Find the max type and set a constraint on it in Mathematical Optimization, Discrete-Event Simulation, and OR

Find the max type and set a constraint on it

HiyaC — Mon, 30 Oct 2023 19:24:13 GMT

Hi. I have an optimization problem where we are selecting students from different states with the highest scores for a national competition. The objective is to select the best students aka maximize the score. The constraints are:

1. At least 50% of the students have to be female (weighted by score, not count)

2. The top state concentration <= 30% (weighted by score, not count)

3. All other concentration <= 15% (weighted by score, not count)

I am pretty new to optmodel and I am struggling with constraints 2 &3. For #2, I am not sure how to identify the top state out of the list that will be selected by the solver and how to then put a upper bound to it.

For #3, I could put the states in individual columns in the students dataset and assign them a 0 or 1, like I did for the sex column. I could then add a family of constraints like this, but I'm not sure if that's the best way of going about it.

State1[s] * score[s] * inclusion[s] <=.15 * score[s] * inclusion[s]

/*sex 0 = male, 1 = female*/
dataset students;
	length name $32. state $2.;
	input name $ state $ score sex;
	datalines;

Ally TX 90 1
Sam VA 50 0
Pamela TX 76 1
Arnold WA 99 0
Nathan TX 85 0
;

dataset allStates;
	length state $2.;
	input state $;
	datalines;
AL
AK
AZ
.
.
.
WY
;

proc optmodel;

set <string> studentSet;
str stuName{studentSet};
str state{studentSet};
num score{studentSet};
num sex{studentSet};

var Inclusion{studentSet} binary;

read data students into studentSet = [stuName = name] state score sex;

maximize totalScore = sum{s in studentSet} score[s] * Inclusion[s];

con generCon: sum{s in studentSet} gender[s] * score[s] * Inclusion[s] >=.5 * sum{s in studentSet} score[s] * Inclusion[s];

solve;

print Inclusion;

quit;

Re: Find the max type and set a constraint on it

RobPratt — Tue, 31 Oct 2023 02:22:45 GMT

Here's a way to enforce #2, because the top state is at most 30% if and only if all states are at most 30%. By using the SETOF operator, you can avoid separately reading all the states from a data set.

   set STATES = setof {s in studentSet} state[s];
   con stateCon {st in STATES}:
      sum{s in studentSet: state[s] = st} score[s] * Inclusion[s] <= 0.3 * sum{s in studentSet} score[s] * Inclusion[s];

Alternatively, you can reuse totalScore:

   set STATES = setof {s in studentSet} state[s];
   con stateCon {st in STATES}:
      sum{s in studentSet: state[s] = st} score[s] * Inclusion[s] <= 0.3 * totalScore;

Re: Find the max type and set a constraint on it

HiyaC — Tue, 31 Oct 2023 02:45:04 GMT

Hi Rob, thank you so much for your reply! that is very helpful in solving #2. However, now I'm not sure how to solve #2 and #3 together, because now all states might be lower than 30% but several might still be higher than 15%. Is there any way to add a constraint that says only 1 state is allowed to be 30%?

Re: Find the max type and set a constraint on it

RobPratt — Tue, 31 Oct 2023 13:36:48 GMT

To handle #2 and #3 together, you can introduce new variables and constraints as follows:

   var IsTopState {STATES} binary;
   con OneTopState:
      sum {st in STATES} IsTopState[st] = 1;
   con stateCon {st in STATES}:
      sum{s in studentSet: state[s] = st} score[s] * Inclusion[s]
   <= (0.15 + 0.15 * IsTopState[st]) * sum{s in studentSet} score[s] * Inclusion[s];

The new stateCon constraint is nonlinear but can be automatically linearized with SAS Viya:

   solve linearize;

To manually linearize instead, you can use the following statements:

   var IsTopStateAndInclusion {STATES, studentSet} binary;
   con Linearize1 {st in STATES, s in studentSet}:
      IsTopStateAndInclusion[st,s] <= IsTopState[st];
   con Linearize2 {st in STATES, s in studentSet}:
      IsTopStateAndInclusion[st,s] <= Inclusion[s];
   con stateCon {st in STATES}:
      sum{s in studentSet: state[s] = st} score[s] * Inclusion[s]
   <= 0.15 * sum{s in studentSet} score[s] * (Inclusion[s] + IsTopStateAndInclusion[st,s]);

   solve;