What is the best algorithm to find the optimal path in reducing company's real-estate footprint?

Question

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.

Answer 1

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.