# Literature on “simcity-like” problems

As it will become apparent, my field is not operation-research and so this question will sound very naive. I am sorry for that.

I have a set of "buildings" that I want to place on a small 2d grid; one per cell only. There is a non-linear objective function that accounts for adjacency effects as well as a score for each building.

Problem right now is small enough that I can brute force it, but I would like to read more about this general class of combinatorial problems.

I've tried reading about 0-1 Knapsack problems and bin-packing but none of them seem to deal or care about adjacency effects. Is there a better term/class for this kind of problems?

To try and narrow down the problem, let's just say the objective function is just the "value" associated with each building + some bonus/malus if two buildings are next to each other (i.e. the police station is worth 1 point, the prison is worth 2 points and you get a bonus of one point if they are next to each other)

• It would be helpful, if you could add more information on the objectiv function. Otherwise this looks like a solid question, so no need to apologize:) My first guess would be, that your problem is likely some type of quadratic assignment problem. – Luke599999 Oct 10 '20 at 8:15
• Agree. Generally, constraints or objectives related to the adjacency in location problems lead to quadratic (Boolean) expressions. The Quadratic Assignment Problem (QAP) en.m.wikipedia.org/wiki/Quadratic_assignment_problem is a classical example. – LocalSolver Oct 10 '20 at 22:15
• thanks, the quadratic assignment problem looks just what I was looking for. Thanks! I'll chase the wikipedia references; if you want to write it as a proper answer I can accept it and close this question. – CarrKnight Oct 11 '20 at 8:04
• @CarrKnight, to add other members mentioned, if you are interested in using some classical (heuristics) methods, some plant layout design like CRAF, etc, might be interested. Also, some of them can be embedded in the excel easily. :) – A.Omidi Oct 11 '20 at 9:28

Your problem looks like a quadratic assignment problem. The problem has been researched since at least the 1950s. As long as P$$\neq$$NP, there cannot be any constant factor approximation algorithm. I think there are some O(log(n))-approximation algorithms. There are also a number of well tested exact algorithms, that are better than brute force, and some heuristic algorithms that perform relatively well.