# Decision Optimization

View Only

## Priority sequence into an MIP formulation?

• #### 1.  Priority sequence into an MIP formulation?

Posted Mon June 13, 2022 03:05 AM
Edited by Shah Mon June 13, 2022 06:22 AM
Hi all,

I'm trying to solve a staff leave allocation problem. User would like to have the allocation based on seniority of staff. That means, final allocation should not have senior staffs unallocated if staffs junior to him is allocated. Seniority rank here is a sequence of natural numbers starting from 1,2,3 and so on.
The isuue that I'm facing is that while trying to maximize allocations, model couldn't really focus on this seniority aspect. Any thoughts? guidance?

------------------------------
Thanks,
Shah
------------------------------

• #### 2.  RE: Priority sequence into an MIP formulation?

IBM Champion
Posted Mon June 13, 2022 02:41 PM
The first question is whether seniority is a hard constraint (if a senior staffer does not get leave, nobody below them does) or aspirational (client would like to respect seniority but it is not an absolute requirement).

The hard constraint case should be fairly easy to formulate (depending on the specifics of your model). For instance, suppose that x[i,j] is a binary variable taking value 1 if staff member i gets leave at time j. If staff member k is the next staffer after i in descending priority order, you can just add a constraint saying sum(j) x[k,j] <= sum(j) x[i,j], which means staffer k does not get leave until staffer i assigned a leave time. The specific formulation will depend on the rest of your model, but the concept should be clear: constraint all variables related to assigning leave to a staffer to zero unless the next higher priority staffer has been given leave.

For the "aspirational" case, you are looking at a multiobjective model. There are a number of ways to handle multiple objectives. One would be a lexicographic approach (which recent versions of CPLEX directly support). Set objective 1 to be maximization of the number of staff awarded leaves. Set objective 2 (lower priority) to be minimization of the number of staff denied leave when at least one lower seniority person got leave (= number of cranky staff). CPLEX will find a solution that achieves a maximum number L of leaves granted, and then look for a solution with a minimal number of discontented staff subject to the requirement that L staff members get leave.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

• #### 3.  RE: Priority sequence into an MIP formulation?

Posted Tue June 14, 2022 01:51 AM

The challenge with the hard constraints is that the number of constraints become huge as there are about 20k staffs and we will have to enforce the constraint for every pair depending upon their seniority. The requirement is hard though. Let me try with your second suggestion.

------------------------------
Shah
------------------------------

• #### 4.  RE: Priority sequence into an MIP formulation?

IBM Champion
Posted Tue June 14, 2022 10:52 AM
You said seniority went 1, 2, 3, ... (where I'm assuming for discussion purposes that 1 is the highest seniority). If there are no ties, you only need one constraint per employee, not one for every pair. You just require that the employee immediately ahead of person X get leave before X gets leave.

If there are a small number of ties, you add a small number of constraints. For instance, if X has seniority n and two people have seniority n-1, you need two constraints preventing X from getting leave prematurely.

If there are a relatively small number of seniority levels with several/many employees at each level, the best approach might be to add a binary variable for each level indicating whether everyone at that level got leave (with appropriate constraints to define it) and then use the binary variable for level n to constrain everyone at level n+1.

------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
------------------------------

• #### 5.  RE: Priority sequence into an MIP formulation?

Posted Wed June 15, 2022 07:44 AM
Okay, Professor Paul. yes seniority is like 1,2,3 and no ties. I though we should add a constraint for senior with all below him. Let me try this and get back to you. Thanks!

------------------------------
Shah
------------------------------

• #### 6.  RE: Priority sequence into an MIP formulation?

Posted Mon June 20, 2022 01:53 PM
Thanks Professor Paul. For hard constraints, it worked

------------------------------
Shah
------------------------------