Let's stack books flat with combinatorial optimization

background

I'm trying to have an online meeting on my laptop. The position of the laptop is low, so the camera angle is from the bottom. I want to hurry to raise the height of my laptop, but I only have a few books at hand. Laptops are larger than books, so you need to stack books in two rows. Also, if the heights of the books in the two rows are different, the balance will be bad, so I want to make the heights of the books in the two rows the same.

problem

Stack some books in two rows and make them as high as possible. At that time, the height difference between the two rows of books should be up to 1 mm.

Way of thinking

Solve using combinatorial optimization. The procedure is to formulate the problem, create a model in Python, and solve it in the solver. Please also refer to "Python in optimization".

Formulation

--Input parameters --books: Height of each book --limit: Upper limit of height difference between 2 columns --Variables --ʻObj: The lower of the heights of the two rows --suml: Height in the left column --sumr: Height in the right column --vl: Whether to stack each book in the left column (0: do not stack, 1: stack) --vr: Whether to stack each book in the right column (0: do not stack, 1: stack) --Objective function: Maximize the lower of the heights of the two columns --Constraints --ʻObj is the smaller of suml and sumr (1) --suml is the height of the left column (2) --sumr is the height of the right column (3) --The difference between suml and sumr is less than or equal to limit (4) --Books can only be placed on either the left or right side (5)

Let's solve it with Python

Input parameters are created appropriately with random numbers.

import random
from ortoolpy import model_max, addvars, addbinvars, lpDot, value

random.seed(1)
books = [random.randint(10, 20) for _ in range(20)]  #Book thickness (millimeters)
limit = 1  #Allowable value for the difference between the left and right heights (millimeters)

n = len(books)
m = model_max()  #Mathematical model
obj, suml, sumr = addvars(3)  #Lower height, left height, right height
vl = addbinvars(n)  #Do you put a book on the left
vr = addbinvars(n)  #Do you put the book on the right
m += obj  #Objective function (make it as high as possible)
m += obj <= suml  # (1)
m += obj <= sumr  # (1)
m += suml == lpDot(books, vl)  # (2)
m += sumr == lpDot(books, vr)  # (3)
m += suml - sumr <= limit  # (4)
m += sumr - suml <= limit  # (4)
for vli, vri in zip(vl, vr):
    m += vli + vri <= 1  # (5)
m.solve()  #Solving with solver
print(f'{m.status = }')
print(f'{value(suml) = }')
print(f'{value(sumr) = }')
print(f'{[int(value(vli) - value(vri)) for vli, vri in zip(vl, vr)]}')

lpDot (X, Y) is the dot product of X and Y. So lpDot (books, vl) is the height of the left column.

output

m.status = 1
value(suml) = 149.0
value(sumr) = 148.0
[-1, -1, -1, 1, -1, 1, -1, 1, 1, 1, -1, 1, 1, 1, -1, -1, -1, 1, 1, -1]

m.status = 1 means that the optimal solution has been obtained. value (X) gets the value of the variable X. The height of the left column is 149 mm, the height of the right column is 148 mm, and the difference is 1 mm. The last list shows that 1 is in the left column and -1 is in the right column.

Digression

The above can be calculated in 0.1 seconds, but if limit is set to 0, the calculation time will be 24 seconds (240 times). In this way, in combinatorial optimization, the calculation time may change significantly if the parameters change slightly. If you want to change the limit in various ways, you may need to devise something like" How to solve the bin packing problem ".

Recommended Posts

Let's stack books flat with combinatorial optimization
Grouping games with combinatorial optimization
Combinatorial optimization with quantum annealing
Solving 4-color problems with combinatorial optimization
Go see whales with combinatorial optimization
Pave the road with combinatorial optimization
Solving game theory with combinatorial optimization
Let's solve the portfolio with continuous optimization
Solving nurse scheduling problems with combinatorial optimization
Create an academic society program with combinatorial optimization
Let's decide the date course by combinatorial optimization
Solving school district organization problems with combinatorial optimization
Solving the N Queen problem with combinatorial optimization
Solving the N Queens problem with combinatorial optimization
Use combinatorial optimization
Optimization learned with OR-Tools [Linear programming: Let's refine oil]
Road installation with optimization
Grouping by combinatorial optimization
Getting Started with Optimization
Let's decide the lecture of PyCon JP 2016 by combinatorial optimization
Let's decide the position of the fire station by combinatorial optimization