[PYTHON] Minimize the number of polishings by combinatorial optimization

Introduction

--Manufacturer A manufactures and sells decorative boards. ――In the final process of manufacturing decorative boards, the scratches found in the inspection are polished and cleaned. ――Suppose you want to minimize the effort of polishing.

Polishing method

――The polishing device grinds the automatically determined width from end to end when you specify a line. ――Since it is rotated 90 degrees in the middle, it means that it can be polished row by row or column by column. --The purpose is to minimize the number of rows or columns that cover all scratches.

image

Formulation

This problem becomes a set cover problem.

Minimize $ \ sum_i {x_i} + \ sum_j {y_j} $ Number of polishings
Variables $ x_i \ in \ {0, 1 \} ~ ~ \ forall i \ in rows $ Polish rows Whether
$ y_j \ in \ {0, 1 \} ~ ~ \ forall j \ in Column $ Whether to polish the column
Constraints $ x_i + y_j \ ge 1 ~ ~ \ forall i, j \ in \ mbox {scratched area} $ All scratches Polish

Run in Python

Create a 4-by-6 dummy. The white part is the scratch.

python3


%matplotlib inline
import numpy as np, matplotlib.pyplot as plt
from pulp import *
np.random.seed(55)
a = np.random.randint(0, 8, 24).reshape(4, -1) // 7
plt.imshow(a, cmap='gray', interpolation='none');

image

Create and execute a mathematical model.

python3


m = LpProblem()
x = [LpVariable('x%d'%i, cat=LpBinary) for i in range(a.shape[0])] #Whether to polish the row
y = [LpVariable('y%d'%i, cat=LpBinary) for i in range(a.shape[1])] #Whether to polish the row
m += lpSum(x + y) #Objective function(Number of times to polish)
for i in range(a.shape[0]):
    for j in range(a.shape[1]):
        if a[i, j]:
            m += x[i] + y[j] >= 1 #Polish rows or columns if scratched
m.solve()
for i in range(a.shape[0]):
    if value(x[i]):
        print('line%Polish d'%i)
for j in range(a.shape[1]):
    if value(y[j]):
        print('Column%Polish d'%j)
>>>
Polish line 3
Polish row 2

You can see that it is made with 2 times, which is the minimum number of polishing times.

that's all

Recommended Posts