2
$\begingroup$

I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it.

Here is the problem: A company is in the process of reducing its office space and wishes to find the path that will minimize double-rent costs during the transition period.

Constraints:

  • There are 200 teams in the company (team = indivisible unit). Teams are of different sizes ranging from 10 to 500 individuals.
  • The start and end locations for each team are given.
  • There are 250 office locations initially (1 per team), 150 will ultimately be removed and 100 will be added. The 100 remaining locations may see a change in occupant, and there will/can be empty locations at any time period.
  • The transition period is of 24 time-periods (months), however, teams do not need to move every month, and should move only when new buildings are added. Teams may move 0, 1, 2 or 3 times during the 24 month time-span
  • Locations are added at different time periods. Once a building is added, monthly rent starts to be charged.
  • Locations which are removed have leases ending at different time periods, but leases can be terminated early for a set fee.

Cost function to minimize:

$$C = \sum_{t=0}^{24}\left (M(F_{t},F_{t-1}) + DR\left (F_{t} \right ) +T(F_{t})\right)$$

with:

  • $M(F_{t},F_{t-1})$ the cost of moving teams from one location to another between 2 subsequent time periods, here moving cost per team is an arbitrary constant.
  • $DR\left (F_{t} \right )$ the cost of double-rents for the footprint at time t. If at time t, a team's start and end locations are available, only the rent of the team's start location is counted for computation of double rent.
  • $T(F_{t})$ the total of early lease termination fees at a time period. Early lease termination fees depend on each location.

Options explored:

I have started exploring different tracks to answer this problem, namely :

  1. Create a graph with every possible permutation at every time step and then find the shortest path using a tree search algorithm. However, the large number of teams, locations and time periods define an immense number of permutations hence I am pretty sure I cannot list all possible trajectories.
  2. I am thinking of using a classical Solver-type tool in Python to find optimal path, however, I fear the number of variables may be too large.

My research also led me to potential methods in the fields of Dynamic Programming, Integer Programming, Branch & Bound.

Is there a clear algorithm or manner to address this that comes to mind ?

Edit : I forgot to mention that teams may move 0, 1, 2 or 3 times during the 24 month time-span.

$\endgroup$
5
  • $\begingroup$ Can you share with us in what context you encountered this task? Is this a practical problem, where you are looking for practical solutions? Is it an algorithms exercise, where you are looking for an algorithm with a proof and a particular running time? $\endgroup$ – D.W. Nov 25 '20 at 22:25
  • $\begingroup$ It is a practical/real world problem. Thus I have a certain leeway regarding constraints and assumptions and I can potentially apply any method to find a solution. $\endgroup$ – JuanC Nov 25 '20 at 22:36
  • $\begingroup$ And it sounds like you don't want to move a team more than once? $\endgroup$ – D.W. Nov 25 '20 at 22:39
  • $\begingroup$ Thank you for your answer, I forgot to mention that teams can move between 0 and 3 times (maximum). Can I just add the constraint $\sum_{i}m_{t,i}\leq 3$ ? $\endgroup$ – JuanC Nov 27 '20 at 18:13
  • $\begingroup$ Yup, that works. $\endgroup$ – D.W. Nov 27 '20 at 18:37
1
$\begingroup$

This kind of scheduling problem might fall within the area of operations research.

I would suggest using integer linear programming. You can formulate this as an instance of ILP, and then solve with an off-the-shelf ILP solver (e.g., Gurobi or CPLEX).

I'll outline a way you could formulate this as an instance of ILP. We'll let $\ell$ range over locations, $t$ over teams, and $i$ over months (time periods). Introduce the following zero-or-one variables:

  • $x_{t,\ell,i}=1$ if team $t$ is at location $\ell$ during month $i$.

  • $s_{\ell,i}=1$ if you start renting the location $\ell$ at the start of month $i$.

  • $e_{\ell,i}=1$ if you terminate (end) renting the location $\ell$ at the end of month $i$.

  • $a_{\ell,i}=1$ if location $\ell$ is available for use during month $i$.

  • $m_{t,i}=1$ if team $t$ moves at the end of month $i$ to a new location.

Then all of your constraints can be expressed as linear inequalities:

  • $\sum_{\ell} x_{t,\ell,i}=1$: each time has a home somewhere in each month.

  • $x_{t,\ell,1}=1$ if $\ell$ is the starting location for team $t$; $x_{t,\ell,24}=1$ if $\ell$ is the ending location for team $t$.

  • $s_{\ell,1}=1$ if $\ell$ is one of the original 250 locations. $s_{\ell,1}=0$ if $\ell$ is not one of the original 250 locations.

  • $a_{\ell,i} = s_{\ell,1} + \dots + s_{\ell,i} - (e_{\ell,1} + \dots + e_{\ell,i-1})$.

  • $x_{t,\ell,i} - m_{t,i} \le x_{t,\ell,i+1} \le x_{t,\ell,i} + m_{t,i}$.

  • $\sum_t x_{t,\ell,i} \le a_{\ell,i}$.

Now the cost is a sum of the moving costs (a linear function of the $m$'s), the rent costs (a linear function of the $a$'s), and the early termination fees (a linear function of the $e$'s), so the cost is a linear function of the variables. Thus, you have an ILP instance, which you can give to an ILP solver and ask it to find the optimal solution -- or the best solution it can find within a set time bound. You'll have about $350\times 200 \times 24$ variables, i.e., about 1.6M variables, which is large but not necessarily infeasible.

$\endgroup$
2
  • $\begingroup$ Thank you for your answer it has definitely put me in the right direction and I have started implementing the problem with PuLP. The $s_{l,i}$s are given and unchangeable hence I should not define them as variables but declare them and call them in the constraints? Furthermore, just to be clear, I should add more constraints for the $e$s, $a$s and $m$s to reflect the choice of $x$s and be "inseparable" from them? Thank you again, I am relatively new to linear programming so any insights would be super helpful. $\endgroup$ – JuanC Dec 4 '20 at 20:11
  • $\begingroup$ @JuanC, yes, in that case they become just constants. If all the starting times are known in advance the problem is easier and maybe there is a better formula (I don't know). Are all the ending times known in advance too? I edited the answer to add one more set of constraints I had forgotten. You should check my logic to see if I'm missing anything else. I'm not sure what you mean by the "inseperable" part so I don't know how to help with that; sorry. $\endgroup$ – D.W. Dec 4 '20 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.