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

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.

• 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?
– D.W.
Nov 25, 2020 at 22:25
• 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. Nov 25, 2020 at 22:36
• And it sounds like you don't want to move a team more than once?
– D.W.
Nov 25, 2020 at 22:39
• 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$ ? Nov 27, 2020 at 18:13
• Yup, that works.
– D.W.
Nov 27, 2020 at 18:37

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.

• 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. Dec 4, 2020 at 20:11
• @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.
– D.W.
Dec 4, 2020 at 20:15