- Given an n×nn×n square area,
- Partition this area into differently sized rectangles,
- Such that the difference in size between the largest and the smallest rectangle is minimized.
Instead of partitioning, we can look at the problem as a tiling problem: given a set of differently sized tiles, place a subset of them on the area such that the whole area is covered and the difference in the size of used tiles (largest minus smallest) is minimized.
The model in [1] looked like:
| Original MIP Model |
|---|
| minu−ℓ∑k,r,i,j|cover(k,r,i,j,i′,j′)xk,r,i′,j′=1∀i′,j′cover cell (i′,j′)yk=∑r,i,j|ok(k,r,i,j)xk,r,i,j∀kselect max one type of rectangleℓ≤areak⋅yk+M(1−yk)∀kbound smallest areau≥areak⋅yk∀kbound largest area∑kareak⋅yk=n2extra constraintxk,r,i,j∈{0,1}yk∈{0,1}u,ℓ≥0M=maxkareakminu−ℓ∑k,r,i,j|cover(k,r,i,j,i′,j′)xk,r,i′,j′=1∀i′,j′cover cell (i′,j′)yk=∑r,i,j|ok(k,r,i,j)xk,r,i,j∀kselect max one type of rectangleℓ≤areak⋅yk+M(1−yk)∀kbound smallest areau≥areak⋅yk∀kbound largest area∑kareak⋅yk=n2extra constraintxk,r,i,j∈{0,1}yk∈{0,1}u,ℓ≥0M=maxkareak |
| Decision Variables |
|---|
| yk={1if tile k is selected0otherwiseyk={1if tile k is selected0otherwise |
| xk,r,i,j={1if tile k (orientation r) is placed at location (i,j)0otherwisexk,r,i,j={1if tile k (orientation r) is placed at location (i,j)0otherwise |
Here I want to discuss a different approach. Instead of solving the problem in one swoop for both yy (select tiles) and xx (place tiles), we can design a simple algorithm that iterates between two different models until we find a feasible integer solution. By ordering things from best to worse, as soon as we find a feasible solution, we have the optimal solution.
The first model is dedicated to select yy variables (i.e. select tiles) such that ∑kareak⋅yk=n2∑kareak⋅yk=n2 and where the objective minu−ℓminu−ℓ is optimized. The second model takes a solution for yy and checks if it is feasible. If not feasible, we go back to model 1 and generate a new, next best solution for yy.
Model 1: selection of tiles, can look like:
| MIP Model 1: Generate proposals for yy |
|---|
| minu−ℓℓ≤areak⋅yk+M(1−yk)∀kbound smallest areau≥areak⋅yk∀kbound largest area∑kareak⋅yk=n2area constraint∑k(2Y∗p,k−1)yk≤∑kY∗p,k−1p∈Pcut off previously found solutionsyk∈{0,1}u,ℓ≥0M=maxkareakminu−ℓℓ≤areak⋅yk+M(1−yk)∀kbound smallest areau≥areak⋅yk∀kbound largest area∑kareak⋅yk=n2area constraint∑k(2Y∗p,k−1)yk≤∑kY∗p,k−1p∈Pcut off previously found solutionsyk∈{0,1}u,ℓ≥0M=maxkareak |
Previously found solutions for yy are stored in the data structure Y∗Y∗. The cut will forbid any previously found solution to be considered again. In the first solve, we can use P=∅P=∅ (no previously found solutions).
The second model establishes whether the solution y∗y∗ in model 1 is feasible. This model, given a selection of tiles (y∗y∗) will try to place the tiles such that all locations of the whole area are covered by exactly one tile.
| MIP Model 2: Check feasibility of y∗y∗ |
|---|
| min0∑k∗,r,i,j|cover(k∗,r,i,j,i′,j′)xk∗,r,i′,j′=1∀i′,j′ and k∗∈K∗cover cell (i′,j′)∑r,i,j|ok(k∗,r,i,j)xk∗,r,i,j=1where k∗∈K∗select one type of rectanglexk∗,r,i,j∈{0,1}K∗={k|y∗k=1}set of selected tilesmin0∑k∗,r,i,j|cover(k∗,r,i,j,i′,j′)xk∗,r,i′,j′=1∀i′,j′ and k∗∈K∗cover cell (i′,j′)∑r,i,j|ok(k∗,r,i,j)xk∗,r,i,j=1where k∗∈K∗select one type of rectanglexk∗,r,i,j∈{0,1}K∗={k|y∗k=1}set of selected tiles |
The algorithm can look like:
- Initialization: P=∅P=∅.
- Solve model 1
- Record the solution y∗ky∗k, augment the set PP and add this solution to Y∗p,kY∗p,k.
- Solve model 2
- If feasible: STOP. We have found the optimal solution.
- Go to step 2.
Small example
When we solve a 10×1010×10 problem, we need 10 cycles:
---- 227 PARAMETER ysolrep solutions for m1 (ordered by obj) obj smallest largest status sol1 3 24 27 Infeasible sol2 6 18 24 Infeasible sol3 6 18 24 Infeasible sol4 7 9 16 Infeasible sol5 7 9 16 Infeasible sol6 7 21 28 Infeasible sol7 7 21 28 Infeasible sol8 7 14 21 Infeasible sol9 7 14 21 Infeasible sol10 8 4 12 Feasible
The status column indicates what model 2 thinks about this proposal. The first 9 generated proposals were infeasible. The first tiling with a difference of 8 was feasible, and we can declare that an optimal solution. We have proven that no better solution exists.
The results look like:
 |
| Solution for 10x10 problem |
Large example
The results for a 25×2525×25 problem are:
 |
| Optimal solution for 25x25 problem |
References
- Mondriaan Tilings, https://yetanothermathprogrammingconsultant.blogspot.com/2020/04/mondriaan-tilings.html The problem and a mathematical model are detailed in this post.
No comments:
Post a Comment