Happy Neighbors Guaranteed with Pyomo!

Why did the mathematician live in a 6x6 lattice? Because s(he) wanted to be surrounded by her/his square neighbors!

Not funny ? I know...

Let's look at nother story :

A total of 9 individuals occupy a 3x3 lattice, with each person residing in a distinct square. An individual's neighbors consist of those who occupy squares that share a common edge with their own square.

Each person in the lattice is given a unique natural number N, with the condition that if a person is assigned a value of N>1, their adjacent neighbors must be assigned all natural numbers from 1 to N-1. (the problem is borrowed form [1])

Look at the following figure to further explain the problem:

• Figure A: shows the empty lattice to be filled with numbers
• Figure B: if number 3 is placed on the pink cell then 2 and 1 should be found in one of neibor cells as you can see.
• Figure C: if number 3 is placed on the white cell then 2 and 1 should be found in one of neibor cells as you can see.
• Figure D: if number 4 is placed on the white cell then 3, 2 and 1 should be found in one of neibor cells. However, as you can see, there is no empty cell left for the white cell to put the 3 on it. .
• Figure E: looks like a feasible solution for the problem. The total summation of numbers = 16. However, it is not a feasible one since 2 has no mutual edge with the top right corner (3).
• Figure F: it is not a correct configuration (hint: look at the number 3).

But what is the optimal solution ?

How to fill these cells to maximize the total score ?

Looks easy ? No.

Problem formulation

Let's formulate the problem. This the first and the most important part of any optimization problem (right after data gathering and preparation).

• Eq (1): The binary variable yin determines the integer number assigned to xi . It should be noted that xi is not required to be defined as an integer.
• Eq (2): Each cell only selects one number from 1 to N
• Eq (3): Is teh most sophisticated one in this formulation. If the value of cell i is m (then yi,m =1) , This will force at least one yjn in the neighbour cells of i (Ai) is one.

The formulation can be further enhanced. How ?

By limiting the upper bound for xi . Why ? based on the location of xi it may not be allowed to take all numbers from 1 to N (see case D). so the upper bound of each cell is found (N_{i,max}) .

By adding this filter to the formulation, the number of binary variables will reduce.

Pyomo Code

Results

3*3 lattice

4*4 lattice

5*5 lattice

6*6 lattice

Applications:

1. Scheduling: Can be used to schedule tasks or events subject to various constraints such as resource availability, precedence relationships, and timing constraints.
2. Planning: Can be used to plan and optimize the use of resources over time, such as personnel, equipment, and facilities.
3. Optimization: Can be used to solve optimization problems, such as minimizing the cost of a project subject to various constraints, or maximizing the efficiency of a production process.
4. Combinatorial problems: Can be used to solve combinatorial problems, such as the traveling salesman problem, the knapsack problem, and the graph coloring problem.
5. Decision support: Can be used to assist decision-making processes, such as choosing the best alternative among a set of options subject to constraints.
6. Artificial intelligence: core technology used in various AI applications such as natural language processing, computer vision, and robotics.

Reference:

https:// research.ibm. com/haifa/ ponderthis/challenges/December2012.html