Can primary and secondary objectives be combined?

[Top_Katz]

Hi!  This is something of a conceptual / problem formulation question.  I actually received some very useful assistance from this community in formulating a simple linear optimization with PROC OPTMODEL.  I am creating a set of (unordered) pairs from a population.  Each pairing has a cost (symmetric, since the pairing is unordered), and each individual can be involved in at most one pairing.  The initial formulation minimized the sum of costs.  Now I can use the minimum cost obtained to create a new constraint for a secondary objective, which is to minimize the maximum cost of each pairing, subject to the previous constraints, plus the constraint that the sum of the costs must be no greater than the original minimum sum.  I might get a different solution with the same sum of costs (I can't go lower if I actually obtained the minimum in my first optimization), but a lower maximum individual cost.  I could also reverse this process -- first minimize the maximum individual pair cost, then use the objective value obtained to constrain the individual costs while minimizing the sum of costs.  Again, my second solution may have a lower sum of costs than the first solution, but with the same maximum individual pair cost.  And the maximum individual cost and sum of costs from the reversed two-stage process will not necessarily be the same as in the original two stages.  For example, I had a population in which the minimum sum of costs for eleven pairs was 340, with a highest cost of 58.  I could achieve a maximum individual cost of 57, but the lowest sum of costs for that was 352.

Is there a way to do either of these two-stage optimizations as a combined single-stage optimization?

Here is my PROC OPTMODEL code for minimizing the sum, followed by minimizing the maximum individual cost:

%let run = 02 ;
%let numpairs&run. = 11 ;
%let cut_off&run. = 0.9 ;

ods output SolutionSummary = &wlib..pd_ods_SolutionSummary_&run. ;

proc optmodel ;
set <num,num> PAIRS ;
num _dist_ {PAIRS} ;
num obs_num {PAIRS} ;
read data &wlib..pairs_dist_01 into PAIRS = [_1_ _2_] obs_num _dist_ ;
set NODES = union {<i,j> in PAIRS} {i,j} ;
var Pair {PAIRS} binary ;
min Objective = sum {<i,j> in PAIRS} (_dist_[i,j] * Pair[i,j]) ;
con NumPairs:
sum {<i,j> in PAIRS} Pair[i,j] = &&numpairs&run.. ;
con Unique {j in NODES}:
sum {<i,(j)> in PAIRS} Pair[i,j] + sum {<(j),k> in PAIRS} Pair[j,k] <= 1 ;

solve ;
print Pair ;
create data &wlib..pd_solution_&run. from [i j] _dist_ obs_num Pair ;
save mps &wlib..pd_mps_&run. ;
quit ;

proc sql noprint ; reset ;
select compress(cValue1)
into :objval&run.
from &wlib..pd_ods_SolutionSummary_&run.
where Label1 = "Objective Value"
;
quit ;

%put objval&run. = &&objval&run.. ;

%let objval&run. = %sysfunc(round(&&objval&run..)) ;

%put objval&run. = &&objval&run.. ;

%let runp = &run. ;
%let run = &runp.a ;
%let numpairs&run. = &&numpairs&runp.. ;
%let cut_off&run. = &&cut_off&runp.. ;

ods output SolutionSummary = &wlib..pd_ods_SolutionSummary_&run. ;

proc optmodel ;
set <num,num> PAIRS ;
num _dist_ {PAIRS} ;
num obs_num {PAIRS} ;
read data &wlib..pairs_dist_01 into PAIRS = [_1_ _2_] obs_num _dist_ ;
set NODES = union {<i,j> in PAIRS} {i,j} ;
var Pair {PAIRS} binary ;
var UpperBound >= 0 <= max {<i,j> in PAIRS} _dist_[i,j] ;
min Objective = UpperBound ;
con ObjSum:
sum {<i,j> in PAIRS} (_dist_[i,j] * Pair[i,j]) <= &&objval&runp.. ;
con IndUpper {<i,j> in PAIRS}:
(_dist_[i,j] * Pair[i,j]) <= UpperBound ;
con NumPairs:
sum {<i,j> in PAIRS} Pair[i,j] = &&numpairs&run.. ;
con Unique {j in NODES}:
sum {<i,(j)> in PAIRS} Pair[i,j] + sum {<(j),k> in PAIRS} Pair[j,k] <= 1 ;

solve ;
print Pair ;
create data &wlib..pd_solution_&run. from [i j] _dist_ obs_num Pair ;
save mps &wlib..pd_mps_&run. ;
quit ;

/**/
title2 "Print &wlib..pd_solution_&run. (where = (Pair ge &&cut_off&run..))" ;
proc print data = &wlib..pd_solution_&run. (where = (Pair ge &&cut_off&run..)) ;
run ;
title2 ;
/**/

proc sql noprint ; reset ;
select compress(cValue1)
into :objval&run.
from &wlib..pd_ods_SolutionSummary_&run.
where Label1 = "Objective Value"
;
quit ;

%put objval&run. = &&objval&run.. ;

%let objval&run. = %sysfunc(round(&&objval&run..)) ;

%put objval&run. = &&objval&run.. ;

Thanks!

[RobPratt]

First note that for your current approach of optimizing the objectives sequentially, you can do it all in one PROC OPTMODEL session, avoiding a lot of code duplication.  See examples 19 and 27 here.  This SAS Global Forum 2014 paper also demonstrates that approach (see the section called "A SECONDARY OBJECTIVE").  Note the use of the PRIMALIN option to speed up the second MILP solve.

An alternative approach to handle multiple objectives is to combine them.  If they all have the same objective sense (min and min, in your case), a simple idea is to just add them.  But usually you need to use weights so that the objective values have the same scale or to reflect their relative importance.  For example, if a 1-unit increase in Objective1 is equivalent to a 10-unit increase in Objective2, you could combine them as follows:

   min CombinedObjective = 10 * Objective1 + Objective2;

If some objectives are min and some are max, you can use a negative weight for each max to "flip" it to min.

You could even map out the efficient frontier by changing the weights in a loop that calls the solver once per choice of weights.

[Top_Katz]

Hi RobPratt!  Thank you so much for the quick response.  I was wondering whether there might be some tricky way of formulating the problem so that it would enforce the priorities of the primary and secondary objective.  With the combined objective function, I think it's true that if the objective values for both problems are discrete, and if you skew the weighting enough, then you can guarantee the priorities, so that would work in this case, but you have to know beforehand what the ranges of the two objective values are, so that you can ensure the worst case of the secondary objective is less than the difference between the two best weighted primary objective values.