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.
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.
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".
--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)
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.
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.
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