6
$\begingroup$

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)

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$
    – PSLP
    Commented Oct 10, 2020 at 8:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – Hexaly
    Commented Oct 10, 2020 at 22:15
  • $\begingroup$ 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. $\endgroup$
    – CarrKnight
    Commented Oct 11, 2020 at 8:04
  • 1
    $\begingroup$ @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. :) $\endgroup$
    – A.Omidi
    Commented Oct 11, 2020 at 9:28

1 Answer 1

Reset to default
4
$\begingroup$

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.

My go to reference for this comes from the world of VLSI design: Check out Chapter 2 (Lower bounds for placement) of Korte, B., & Vygen, J. (2008). Combinatorial problems in chip design. In Building Bridges (pp. 333-368). Springer, Berlin, Heidelberg.

Improve this answer
$\endgroup$
1
  • $\begingroup$ In practice, the QAP problem is very hard to solve exactly (that is, to get proven optimal solutions), even for small instances. LocalSolver is of interest to this problem: thanks to the heuristic ingredient embedded inside, it is able to deliver quality solutions quite fast to large-scale QAP instances. Here is a ready-to-use QAP model for LocalSolver: localsolver.com/docs/last/exampletour/qap.html. LocalSolver is a commercial optimization solver but you can use it for free in the context of academic research. $\endgroup$
    – Hexaly
    Commented Oct 12, 2020 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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