Are you over 18 and want to see adult content?
More Annotations
A complete backup of https://vasotec5.com
Are you over 18 and want to see adult content?
A complete backup of https://simplecirc.com
Are you over 18 and want to see adult content?
A complete backup of https://sumatriptane.com
Are you over 18 and want to see adult content?
A complete backup of https://sabbathschoolpersonalministries.org
Are you over 18 and want to see adult content?
A complete backup of https://independencemuseum.org
Are you over 18 and want to see adult content?
A complete backup of https://absm.org
Are you over 18 and want to see adult content?
A complete backup of https://allsingaporestuff.com
Are you over 18 and want to see adult content?
A complete backup of https://hollyeats.com
Are you over 18 and want to see adult content?
A complete backup of https://mudanzasbarcelona.pro
Are you over 18 and want to see adult content?
A complete backup of https://rosesandrings.com
Are you over 18 and want to see adult content?
A complete backup of https://aubreyorganics.com
Are you over 18 and want to see adult content?
Favourite Annotations
A complete backup of www.vavel.com/colombia/futbol-colombiano/2020/02/15/deportivo-cali/1013730-atletico-nacional-vs-deportivo-c
Are you over 18 and want to see adult content?
A complete backup of www.vavel.com/colombia/futbol-colombiano/2020/02/14/millonarios/1013696-millonarios-vs-boyaca-chico-en-vivo
Are you over 18 and want to see adult content?
A complete backup of www.razon.com.mx/deportes/mitch-evans-gana-en-dramatica-carrera-de-formula-e-en-mexico-autodromo-hermanos-r
Are you over 18 and want to see adult content?
Text
Example:
Shikaku Problem and SolutionAPPROACH
One possible approach is a two-step algorithm: * Generate all feasible rectangles, * Use a simple MIP model to select a subset of these rectangles such that each cell is covered exactly once. For the problem above, we just have 31 feasible rectangles. Feasible means here: (a) rectangle contains exactly one cell with a number, (b) the size of the rectangle is equal to that number. All feasible rectangles The problem of how to generate all feasible rectangles is easier said than done, especially if you want to do this efficiently for larger instances. This is mainly a programming exercise, rather than amodeling problem.
The second part is surprisingly simple. Assume all k∈Kk∈K rectangles are stored in a single large boolean data structure: allRectanglesk,i,j={1if cell (i,j) is part of rectangle k0otherwiseallRectanglesk,i,j={1if cell (i,j) is part of rectangle k0otherwise then the optimization model is a simple setcovering model:
SET COVERING PROBLEM min0∑kallRectanglesk,i,jxk=1∀i,jxk∈{0,1}min0∑kallRectanglesk,i,jxk=1∀i,jxk∈{0,1} In this case, we don't have an objective. We simply state that every cell (i,j)(i,j) must be covered by exactly one rectangle. This is a tiny model and solves very easily. Typically it can be solved completely in the presolve phase: Tried aggregator 1 time. MIP Presolve eliminated 37 rows and 32 columns. MIP Presolve modified 3 coefficients. All rows and columns eliminated. The solution can look like: ---- 89 VARIABLE x.L selection of rectangles k1 1.000, k3 1.000, k5 1.000, k8 1.000, k9 1.000, k12 1.000, k20 1.000, k22 1.000 k26 1.000, k29 1.000, k31 1.000 ---- 97 PARAMETER result solution: selected rectangles c1 c2 c3 c4 c5 c6 r1 1 3 5 5 8 9 r2 1 3 5 5 8 9 r3 12 3 5 5 8 9 r4 12 3 20 20 22 22 r5 12 3 26 26 26 26 r6 29 29 29 29 31 31 The model selects 11 rectangles. We could have predicted this: there are 11 numbered cells in the input data. The parameter RESULT displays the selected rectangle numbers on the grid. You should be able to match this up with the picture of the feasible rectangles shown earlier.GAMS MODEL
$ontext
_Cell Block or Shikaku puzzle_ _Set Covering model for (small) square grids_ _erwin@amsterdamoptimization.com_
$offtext
SETS
i _'rows' _/r1*r6/
j _'columns' _/c1*c6/;
SCALARS
m _'rows'_
n _'columns'_
;
m = CARD(i);
n = CARD(j);
ALIAS(i,p,h);
ALIAS(j,q,w);
TABLE grid(i,j)
c1 c2 c3 c4 c5 c6
r1 2 3 r2 6 3r3 5
r4 3 2 2 r5 4 r6 4 2;
SCALAR nn _'sum of numbers'_; nn = SUM((i,j),grid(i,j));DISPLAY nn;
ABORT$(nn <> CARD(i)*CARD(j)) "error in grid specification"; _*------------------------------------------_ _* generate all possible rectangles__* requirements:_
_* 1. block contains exactly one number from grid_ _* 2. size of block is equal to this number_ _*------------------------------------------_
SET
k _'rectangle number' _/k1*k10000/ allRectangles(k,i,j) r(i,j) _'current rectangle'_;
SINGLETON SET
kk(k) _'current index' _/k1/;
LOOP((p,q),
LOOP((w,h)$(ORD(p)+ORD(h)-1<=m AND ORD(q)+ORD(w)-1<=n), _* candidate rectangle_ r(i,j) = (ORD(i)>=ORD(p) AND ORD(i)<=ORD(p)+ORD(h)-1 ANDORD(j)>=ORD(q) AND
ORD(j)<=ORD(q)+ORD(w)-1); _* check: only one grid number and size = gridnumber_ IF(SUM(r$grid(r),1)=1 AND CARD(r)=SUM(r,grid(r)), allRectangles(kk,r) = YES;kk(k)=kk(k-1);
);
);
);
_*------------------------------------------_ _* model: select rectangles such that each_ _* cell is covered exactly once_ _*------------------------------------------_
BINARY VARIABLE x(k) _'selection of rectangles'_; VARIABLE z _'dummy objective'_;EQUATIONS
dummy _'dummy objective'_ covering(i,j) _'each cell is covered by exactly one rectangle'_;
covering(i,j).. SUM(allRectangles(k,i,j),x(k)) =e= 1;dummy.. z =e= 0;
MODEL cover /all/;
_* just need feasibility_ SOLVE cover minimizing z using mip;DISPLAY x.l;
_* reporting_
PARAMETER result(i,j) _'solution: selected rectangles'_; LOOP(k$(x.l(k)>0.5), result(i,j)$allRectangles(k,i,j) = ORD(k););
OPTION result:0;
DISPLAY result;
Notes:
* The data check makes sure the sum of the numbers is equal to the size (area) of the grid. * The enumeration of the feasible rectangles is using a simplistic and crude algorithm. It may need to be refined for larger instances. * allRectangles(k,i,j) is implemented as a set. * As we are looking for a feasible solution only, there is no need to specify a gap with the optcr option.A LARGER PROBLEM
A larger problem is taken from .17 x 15 problem
Some statistics:
* This problem has 17 rows and 15 columns. * The number of feasible rectangles is 253. * The number of numbered cells is 66. This is also the number of rectangles we need to select. * If one wants to make a big impression, mention that the number of ways we can choose 66 out of 253 is: (25366)=66281207211442081043167193447008690678844358496354619442275550(25366)=66281207211442081043167193447008690678844358496354619442275550 The results look like: ---- 105 VARIABLE x.L selection of rectangles k1 1.000, k3 1.000, k6 1.000, k11 1.000, k13 1.000, k16 1.000, k30 1.000, k34 1.000 k36 1.000, k37 1.000, k41 1.000, k44 1.000, k45 1.000, k51 1.000, k54 1.000, k63 1.000 k65 1.000, k69 1.000, k73 1.000, k82 1.000, k84 1.000, k87 1.000, k90 1.000, k91 1.000 k94 1.000, k103 1.000, k107 1.000, k110 1.000, k112 1.000, k125 1.000, k128 1.000, k130 1.000 k132 1.000, k134 1.000, k136 1.000, k140 1.000, k143 1.000, k150 1.000, k152 1.000, k154 1.000 k159 1.000, k162 1.000, k171 1.000, k174 1.000, k190 1.000, k192 1.000, k195 1.000, k199 1.000 k201 1.000, k202 1.000, k203 1.000, k204 1.000, k209 1.000, k216 1.000, k219 1.000, k222 1.000 k226 1.000, k228 1.000, k235 1.000, k238 1.000, k244 1.000, k245 1.000, k247 1.000, k249 1.000 k251 1.000, k253 1.000 ---- 113 PARAMETER result solution: selected rectangles c1 c2 c3 c4 c5 c6 c7 c8 c9 r1 1 3 3 6 6 11 11 11 11 r2 1 3 3 6 6 11 11 11 11 r3 30 30 30 30 34 34 36 37 37 r4 30 30 30 30 34 34 36 51 51 r5 30 30 30 30 34 34 63 65 65 r6 73 73 73 73 34 34 63 65 65 r7 87 87 90 90 91 91 94 65 65 r8 103 103 103 103 103 103 94 107 107 r9 103 103 103 103 103 103 94 125 125 r10 134 136 136 140 140 143 143 125 125 r11 134 154 154 159 159 159 159 159 159 r12 171 154 154 174 174 174 174 174 174 r13 171 190 190 192 195 195 195 199 199 r14 204 190 190 192 195 195 195 209 209 r15 204 190 190 216 216 219 219 222 222 r16 204 190 190 216 216 235 235 235 238 r17 204 244 244 245 245 245 247 247 249 + c10 c11 c12 c13 c14 c15 r1 11 11 13 13 16 16 r2 11 11 13 13 16 16 r3 41 41 13 13 44 45 r4 54 54 13 13 44 45 r5 54 54 69 69 44 45 r6 82 84 84 84 44 45 r7 82 84 84 84 44 45 r8 107 110 110 112 44 45 r9 128 128 130 112 132 132 r10 128 128 130 150 150 152 r11 162 162 130 150 150 152 r12 162 162 130 150 150 152 r13 199 201 201 202 203 203 r14 209 209 209 202 203 203 r15 222 222 222 226 226 228 r16 238 238 238 226 226 228 r17 249 249 251 251 253 253 Again the presolver could eliminate all rows and columns.QUESTIONS
I still have some lingering questions about this problem. * How would a better algorithm that enumerates all feasible rectangles look like? I guess it would start with the cells containingnumbers.
* Can we use the solution pool to automate this step? * Is the solution unique? * Are there cases where the presolver is not solving the completeproblem?
REFERENCES
* https://puzzlemadness.co.uk/ Posted by Erwin Kalvelagenat 10:23 PM
3 comments:
Links to this post
Labels: Mixed-Integer Programming,
Modeling
,
Puzzle
,
Set Covering Model
MONDAY, MARCH 9, 2020TILING
This problem is original from . I made it a bit more general.PROBLEM STATEMENT
Given a collection of square tiles, what is the MAXIMUM SQUARE SPACE we can fill with them?EXAMPLE
Let's consider our inventory: ---- 29 PARAMETER input inventory data count width area tile1 6 1 1 tile2 5 2 4 tile3 4 3 9 tile4 3 4 16 tile5 2 5 25 tile6 1 6 36 total 21 196 So we have a total of 21 tiles of different sizes. Their total area is 196. This means that the best we can hope for is to fill square space of 14×14=19614×14=196. The optimization model shows we can fill this whole 14×1414×14 area, using up all the tiles. No leftovers. As we will see later, this is somewhat of a special case. The optimal solution can look like: ---- 110 PARAMETER tiles solution x y width area tile1-1 12 1 1 tile1-2 13 1 1 tile1-3 13 1 1 tile1-4 13 1 1 1 tile1-5 13 2 1 1 tile1-6 13 3 1 1 tile2-1 3 10 2 4 tile2-2 7 6 2 4 tile2-3 1 12 2 4 tile2-4 3 12 2 4 tile2-5 7 8 2 4 tile3-1 3 9 tile3-2 3 3 9 tile3-3 6 3 9 tile3-4 9 3 9 tile4-1 3 6 4 16 tile4-2 9 4 16 tile4-3 5 10 4 16 tile5-1 9 4 5 25 tile5-2 9 9 5 25 tile6-1 3 6 36 space 14 196 The solution presented in a numeric table is a bit difficult to grasp, so let's make a picture:An optimal solution
It is noted that this solution is not unique. A proper tiling has no overlapping tiles and no uncovered spaces, i.e., no holes. The picture confirms this is the case here. Below I will discuss two different formulations. Warning: they are abit tricky.
FORMULATION A: NO-OVERLAP CONSTRAINTS One way to model this is to consider no-overlap constraints between two squares. The idea is as follows. Assume we have two squares i,ji,j with size sksk and location (xk,yk)(xk,yk), then we can say: xj≥xi+sioryj≥yi+siorxi≥xj+sjoryi≥yj+sjxj≥xi+sioryj≥yi+siorxi≥xj+sjoryi≥yj+sj A standard way to shoehorn this into a MIP model is to use big-Mconstraints:
xj≥xi+si−M(1−δ(1)i,j)yj≥yi+si−M(1−δ(2)i,j)xi≥xj+sj−M(1−δ(3)i,j)yi≥yj+sj−M(1−δ(4)i,j)∑dδ(d)i,j≥1xj≥xi+si−M(1−δi,j(1))yj≥yi+si−M(1−δi,j(2))xi≥xj+sj−M(1−δi,j(3))yi≥yj+sj−M(1−δi,j(4))∑dδi,j(d)≥1 Alternatively, using the complement: xj≥xi+si−Mδ(1)i,jyj≥yi+si−Mδ(2)i,jxi≥xj+sj−Mδ(3)i,jyi≥yj+sj−Mδ(4)i,j∑dδ(d)i,j≤3xj≥xi+si−Mδi,j(1)yj≥yi+si−Mδi,j(2)xi≥xj+sj−Mδi,j(3)yi≥yj+sj−Mδi,j(4)∑dδi,j(d)≤3 The disadvantage of this formulation is that we need good, tight valuesfor MM.
Using this framework we can formulate the model: MODEL A: NO-OVERLAP CONSTRAINTSSets
i,jtilesapossible widths for space to fill: 1,2,…c={x,y}coordinatesk={isizeisize of
tile iMbig-M constantssizeSpacea=1,2,…,maxSpacepossible sizes of total space we can fillsizeisize of tile iMbig-M constantssizeSpacea=1,2,…,maxSpacepossible sizes of total space we can fillVariables
ti∈{0,1}select tile ipi,c≥0position of tile i, (x,y) coordinatesWwidth of space we can fillAarea of space to fillδi,j,k,c∈{0,1}no-overlap casesθa∈{0,1}select width of space to fillti∈{0,1}select tile ipi,c≥0position of tile i, (x,y) coordinatesWwidth of space we can fillAarea of space to fillδi,j,k,c∈{0,1}no-overlap casesθa∈{0,1}select width ofspace to fill
Objective
maxWmaxW
Maximize width of space we can fillConstraints
pi,c+sizei≤W∀i,cpi,c+sizei≤W∀i,c Each tile should be located inside the space we want to fill. Really only important for selected tiles, but it is easier to apply this constraint to all tiles. pj,c≥pi,c+sizei−M(1−δi,j,iby Mi,jMi,j.
I also added some ordering constraints: ti≥ti+1if sizei=sizei+1ti≥ti+1if sizei=sizei+1 This will select tiles according to their ordinal number. Furthermore, ∑cpi,c≥∑cpi+1,cif sizei=sizei+1∑cpi,c≥∑cpi+1,cif sizei=sizei+1 This will order the locations, and hopefully breaks some symmetry inthe model.
This model works fine for our example data. However, for larger instances, things become very slow. FORMULATION B: GRID APPROACH In this formulation, we work with binary variables: xi,p,q={1if tile i is placed at location (p,q)0otherwisexi,p,q={1if tile i is placed at location (p,q)0otherwise Then for each location (p,q)(p,q) we check that the number tiles covering this location is equal to one within the area to fill and zero outside. To model this we develop a binary parameter coverp1,q1,i,p,q={1if (p1,q1) is covered whentile i is placed
at (p,q)0otherwisecoverp1,q1,i,p,q={1if (p1,q1) is covered when tile i is placed at (p,q)0otherwise Furthermore, we maintain a boolean matrix yp1,q1yp1,q1 with yp1,q1={1if (p1,q1) is within our current area to fill0otherwiseyp1,q1={1if (p1,q1) is within our current area to fill0otherwise Notice that this area is shrinking during the solution process, so this matrix is dynamic (i.e. avariable).
y matrix
Detail: yy has P+1P+1 rows and columns. Initially, we just have one final row and column of zeroes. The size of PP is determined from the inventory: sum all areas of the tiles, take the square root and round down. The way we keep track of yy is to introduce a binary variable δp∈{0,1}δp∈{0,1} with δp≤δp−1∑pδp=Wδp≤δp−1∑pδp=W Now we just can do yp,q=δp⋅δqyp,q=δp⋅δq, for which a standard linearization isavailable.
With this, the covering constraint can look like: ∑i,p,qcoverp1,q1,i,p,qxi,p,q=yp1,q1∀p1,q1∑i,p,qcoverp1,q1,i,p,qxi,p,q=yp1,q1∀p1,q1 This says: each cell inside the area to fill is covered by exactly one tile, and cells outside can not be covered. The complete model canlook like:
MODEL B: GRID APPROACHSets
itilesp,qgridpoints, p,q∈{1,..,P} p1,q1gridpoints plus extra rowand
column, p1,q1∈{1,…,P+1}itilesp,qgridpoints, p,q∈{1,..,P} p1,q1gridpoints plus extra row and column, p1,q1∈{1,…,P+1}Parameters
sizeisize of tile icoverp1,q1,i,p,q∈{0,1}1 if (p1,q1) is covered by tile i at (p,q)sizeisize of tile icoverp1,q1,i,p,q∈{0,1}1 if (p1,q1) is covered bytile i at (p,q)
Variables
xi,p,q∈{0,1}place tile i at location (p,q)yp1,q1∈{0,1}1 inside area to be filled, 0 outsideδp1∈{0,1}1 if p1≤WWwidth of space we can fillxi,p,q∈{0,1}place tile i at location (p,q)yp1,q1∈{0,1}1 inside area to be filled, 0 outsideδp1∈{0,1}1 if p1≤WWwidth of space we can fill The yy variables can be relaxed to yp1,q1∈yp1,q1∈.Objective
maxWmaxW
Maximize width of space we can fillConstraints
∑p,qxi,p,q≤1∀i∑p,qxi,p,q≤1∀i Each tile can be placed once ∑i,p,qcoverp1,q1,i,p,q⋅xi,p,q=yp1,q1∀p1,q1∑i,p,qcoverp1,q1,i,p,q⋅xi,p,q=yp1,q1∀p1,q1 Cover constraint. Inside the fill-area, each cell must be covered exactly once. Outside: zero coverage. δp1≤δp1−1∑p1δp1=Wδp1≤δp1−1∑p1δp1=W Force a pattern like 111000. Number of ones is WW. The last element is a 0. This is used to form the yy matrix. yp1,q1≤δp1yp1,q1≤δq1yp1,q1≥δp1+δq1−1yp1,q1≤δp1yp1,q1≤δq1yp1,q1≥δp1+δq1−1 Maintain the yy matrix. The first W rows and columns are ones. The other entries are zeros. One extra row and column of zeros for safeguarding against covering outside the area. These constraints are a linearization of a binary multiplication. This model can handle larger problems. I tried the inventory: ---- 56 PARAMETER input inventory data count width area tile1 9 1 1 tile2 8 2 4 tile3 7 3 9 tile4 6 4 16 tile5 5 5 25 tile6 4 6 36 tile7 3 7 49 tile8 2 8 64 tile9 1 9 81 total 45 825 This is a larger data set with 45 tiles. The total area of the tiles is 825. The square root is √825=28.723825=28.723 So the maximum square we can hope to fill is 28×2828×28 with an area of 784. The generated MIP model is very large:MODEL STATISTICS
BLOCKS OF EQUATIONS 8 SINGLE EQUATIONS 3,473 BLOCKS OF VARIABLES 5 SINGLE VARIABLES 36,196 1 projected NON ZERO ELEMENTS 614,345 DISCRETE VARIABLES 35,353 Although it is large, it solves rather easily. We just needed 10 nodes. It has the following optimal solution: ---- 161 PARAMETER tiles solution x y width area item1-1 27 23 1 1 item1-2 10 1 1 item1-3 10 13 1 1 item1-4 9 1 1 item1-5 14 5 1 1 item1-6 14 18 1 1 item1-7 20 6 1 1 item1-8 27 24 1 1 item2-1 25 23 2 4 item2-2 1 9 2 4 item2-3 14 2 4 item2-4 24 2 4 item2-5 16 2 4 item2-6 26 2 4 item3-1 3 9 item3-2 11 16 3 9 item3-3 6 3 9 item3-4 11 3 9 item3-5 3 3 9 item3-6 25 25 3 9 item3-7 11 13 3 9 item4-1 2 14 4 16 item4-2 10 5 4 16 item4-3 10 9 4 16 item4-4 2 24 4 16 item5-1 10 5 25 item5-2 15 18 5 25 item5-3 15 23 5 25 item5-4 6 14 5 25 item5-5 20 23 5 25 item6-1 15 6 36 item6-2 14 6 6 36 item6-3 18 6 36 item6-4 14 12 6 36 item7-1 3 7 49 item7-2 3 7 7 49 item7-3 21 7 49 item8-1 20 15 8 64 item8-2 20 7 8 64 item9-1 6 19 9 81 space 28 784 Indeed we find the 28×2828×28 tiling.An optimal solution
SUMMARY OF PERFORMANCE These results are with Cplex, 8 threads, default settings.DATA SET 1
DATA SET 2
DATA
Tiles
21
45
Area
196
824
SOLUTION
Width
14
28
Area
196
784
Tiles used
21
40
MODEL A
Variables
919
4,125
Binary variables
875
4,033
Constraints
1,126
5,116
Solution time
39
NA
Nodes
73,975
NA
MODEL B
Variables
4,378
36,196
Binary variables
4,151
35,353
Constraints
950
3,473
Solution time
1.3
256
Nodes
0
10
Obviously, approach B is performing much better, even though it generates much larger MIP models. AN EXAMPLE WITH SMALLER COVERED AREA Above we discussed two examples: * In the first example, we could use all the tiles of the inventory. * In the second example, the square area we could cover was equal to the maximum possible area calculated from the total area of thetiles.
Here is a small example where we are much below this maximum estimate. The data looks like: ---- 44 PARAMETER input inventory data count width area tile1 1 1 1 tile2 1 2 4 tile3 1 3 9 tile4 1 4 16 tile5 1 5 25 tile6 1 6 36 tile7 1 7 49 tile8 1 8 64 tile9 1 9 81 total 9 285 So we have one of each size from 1 to 9. Looking at the total area, the maximum size we can expect is:⌊√285⌋=16⌊285⌋=16 When wesolve this, we see:
---- 125 PARAMETER tiles solution width area tile9-1 9 81 space 9 81 I.e. just the 9×99×9 tile is used.CONCLUSION
This problem is a bit more complex to model as a MIP. The first "no-overlap" formulation did not perform very well. The second "grid cover" formulation did much better, and I could solve some larger problems in a few minutes.REFERENCES
* Max square side length of smaller squares, https://stackoverflow.com/questions/60526058/max-square-side-lenght-of-smaller-squares Posted by Erwin Kalvelagenat 4:07 AM
No comments:
Links to this post
Labels: Mixed-Integer Programming,
Modeling
MONDAY, MARCH 2, 2020 NON-CONVEX QUADRATIC MODELS II: RECTANGULAR COVERING RECTANGULAR COVERING This problem is from . PROBLEM STATEMENT: given NN data points, arrange kk boxes such that every point is inside a box and the size of the boxes is minimized. We assume the boxes have sides parallel to the axes. I.e. the box is notangled.
A 2d data set with N=50N=50 points can look like:N=50 data points
The best configuration of K=5K=5 boxes for this data set is: Optimal solution for K=5 rectangles The problem is like the opposite of the "largest empty box" , where we try to find the largest box without any data points inside.2D MODEL
Let's define some symbols: * We will denote the data points by ii and the rectangles by kk. * The coordinates of the data points are stored in pi,c∈pi,c∈ with c∈{x,y}c∈{x,y}. * The location and size of the rectangles are rk,s∈rk,s∈ . Here s∈{x,y,w,h}s∈{x,y,w,h}. * The assignment of (data) points to rectangles is modeled with a binary variable xi,k∈{0,1}xi,k∈{0,1}. A high-level model for 2 dimensions can look like: HIGH-LEVEL 2D MIQP MODEL min∑krk,w⋅rk,h∑kxi,k=1∀ixi,k=1⟹⎧⎪ ⎪ ⎪ ⎪⎨⎪⎪ ⎪
⎪⎩pi,x≥rk,xpi,y≥rk,ypi,x≤rk,x+rk,wpi,y≤rk,y+rk,h∀i,kxi,k∈{0,1}rk,h∈rk,x+rk,w≤Urk,y+rk,h≤Umin∑krk,w⋅rk,h∑kxi,k=1∀ixi,k=1⟹{pi,x≥rk,xpi,y≥rk,ypi,x≤rk,x+rk,wpi,y≤rk,y+rk,h∀i,kxi,k∈{0,1}rk,h∈rk,x+rk,w≤Urk,y+rk,h≤U The implication says "if xi,k=1xi,k=1 then point ii should be in box kk". This can be implemented using indicator constraints or with abig-M construct:
pi,x≥rk,x−M(1−xi,k)pi,y≥rk,y−M(1−xi,k)pi,x≤rk,x+rk,w+M(1−xi,k)pi,y≤rk,y+rk,h+M(1−xi,k)pi,x≥rk,x−M(1−xi,k)pi,y≥rk,y−M(1−xi,k)pi,x≤rk,x+rk,w+M(1−xi,k)pi,y≤rk,y+rk,h+M(1−xi,k) A value for MM can be M=U−LM=U−L. We can of course scale the data pi,cpi,c to pi,c∈pi,c∈ beforehand, in which case we can set M=1M=1. This is what I did in my experiments. I also add the constraint: rk,x≥rk−1,xrk,x≥rk−1,x to make the solution more predictable. The solution will be ordered by the xx-coordinate of the box. It also reduces symmetry in the model. The objective has non-convex quadratic terms. So we need a NON-CONVEXQUADRATIC SOLVER.
The detailed data and the solution look like: ---- 56 PARAMETER p data points x y i1 0.80601 0.17283 i2 0.52952 0.14887 i3 0.64826 0.69240 i4 0.35222 0.02016 i5 0.43130 0.55356 i6 0.64087 0.77456 i7 0.23545 0.78074 i8 0.26800 0.08158 i9 0.97328 0.11440 i10 0.87431 0.66711 i11 0.75621 0.96771 i12 0.19863 0.24001 i13 0.21990 0.26101 i14 0.98863 0.17156 i15 0.06625 0.93008 i16 0.80603 0.83235 i17 0.10543 0.02902 i18 0.22927 0.09355 i19 0.12983 0.90322 i20 0.43682 0.72756 i21 0.24754 0.57512 i22 0.36012 0.51628 i23 0.71015 0.74601 i24 0.70367 0.74621 i25 0.18517 0.93583 i26 0.81681 0.67338 i27 0.46350 0.57754 i28 0.08932 0.65688 i29 0.97335 0.69059 i30 0.89449 0.07780 i31 0.14124 0.39550 i32 0.99382 0.49870 i33 0.05406 0.56047 i34 0.32927 0.79803 i35 0.22975 0.85134 i36 0.78532 0.27930 i37 0.18014 0.28874 i38 0.38628 0.82680 i39 0.48970 0.57654 i40 0.46709 0.14913 i41 0.19949 0.83893 i42 0.25438 0.57046 i43 0.55116 0.95672 i44 0.02634 0.93260 i45 0.49950 0.08040 i46 0.44529 0.43742 i47 0.55100 0.41666 i48 0.29626 0.69398 i49 0.93426 0.58556 i50 0.28083 0.92941 ---- 56 VARIABLE x.L assignment variables k1 k2 k3 k4 k5 i1 1 i2 1 i3 1 i4 1 i5 1 i6 1 i7 1 i8 1 i9 1 i10 1 i11 1 i12 1 i13 1 i14 1 i15 1 i16 1 i17 1 i18 1 i19 1 i20 1 i21 1 i22 1 i23 1 i24 1 i25 1 i26 1 i27 1 i28 1 i29 1 i30 1 i31 1 i32 1 i33 1 i34 1 i35 1 i36 1 i37 1 i38 1 i39 1 i40 1 i41 1 i42 1 i43 1 i44 1 i45 1 i46 1 i47 1 i48 1 i49 1 i50 1 ---- 56 VARIABLE r.L rectangles x y w h k1 0.02634 0.69240 0.77969 0.27530 k2 0.05406 0.24001 0.20032 0.41687 k3 0.10543 0.02016 0.42409 0.12897 k4 0.36012 0.41666 0.19087 0.16088 k5 0.78532 0.07780 0.20850 0.61279 ---- 56 VARIABLE z.L = 0.51132 objective This model was solved to proven global optimality with Gurobi in about 670 seconds. Cplex also can solve models of this type. TO HIGHER DIMENSIONS The above model dealt with the 2D problem. It is not very difficult to extend this to more dimensions. Let's try to make this general, forany dimension.
First of all, I reorganized my sets a bit: * We have d∈{1,…,D}d∈{1,…,D} indicating the dimension we are looking at. Think about this as 1=x,2=y,3=z,...1=x,2=y,3=z,.... * To characterize a box, for each dimension, we have a coordinate and a side-length. So, cs∈{coord,side}cs∈{coord,side}. With this, we can write: * pi,dpi,d are the coordinates of the points, * rk,d,csrk,d,cs indicate the location and size of the boxes. The model can now look like: HIGH-LEVEL N-DIMENSIONAL MINLP MODEL min∑k∏drk,d,side∑kxi,k=1∀ixi,k=1⟹{pi,d≥rk,d,coordpi,d≤rk,d,coord+rk,d,side∀i,k,dxi,k∈{0,1}rk,d,cs∈rk,d,coord+rk,d,side≤Umin∑k∏drk,d,side∑kxi,k=1∀ixi,k=1⟹{pi,d≥rk,d,coordpi,d≤rk,d,coord+rk,d,side∀i,k,dxi,k∈{0,1}rk,d,cs∈rk,d,coord+rk,d,side≤U The objective is not quadratic. We can make it quadratic by chaining. We introduce a variable vv which is defined by:vk,d={vk,d−1⋅rk,d,sidefor d≥3rk,2,side⋅rk,1,sidefor d=2vk,d={vk,d−1⋅rk,d,sidefor d≥3rk,2,side⋅rk,1,sidefor d=2 Now we can just minimize ∑kvk,D∑kvk,D. For the special case of a 3d problem, we can simplify this to: min∑kareak⋅rk,3,sideareak=rk,2,side⋅rk,1,sidemin∑kareak⋅rk,3,sideareak=rk,2,side⋅rk,1,side A small data set (N=20N=20 points, and K=5K=5) leads to: ---- 62 PARAMETER p data points dim1 dim2 dim3 i1 0.80601 0.17283 0.52952 i2 0.14887 0.64826 0.69240 i3 0.35222 0.02016 0.43130 i4 0.55356 0.64087 0.77456 i5 0.23545 0.78074 0.26800 i6 0.08158 0.97328 0.11440 i7 0.87431 0.66711 0.75621 i8 0.96771 0.19863 0.24001 i9 0.21990 0.26101 0.98863 i10 0.17156 0.06625 0.93008 i11 0.80603 0.83235 0.10543 i12 0.02902 0.22927 0.09355 i13 0.12983 0.90322 0.43682 i14 0.72756 0.24754 0.57512 i15 0.36012 0.51628 0.71015 i16 0.74601 0.70367 0.74621 i17 0.18517 0.93583 0.81681 i18 0.67338 0.46350 0.57754 i19 0.08932 0.65688 0.97335 i20 0.69059 0.89449 0.07780 ---- 62 VARIABLE x.L assignment variables k1 k2 k3 k4 k5 i1 1 i2 1 i3 1 i4 1 i5 1 i6 1 i7 1 i8 1 i9 1 i10 1 i11 1 i12 1 i13 1 i14 1 i15 1 i16 1 i17 1 i18 1 i19 1 i20 1 ---- 62 VARIABLE r.L rectangles dim1.coord dim1.side dim2.coord dim2.side dim3.coord dim3.side k1 0.02902 0.77701 0.22927 0.74401 0.07780 0.03660 k2 0.08932 0.14613 0.64826 0.28757 0.26800 0.70534 k3 0.17156 0.18066 0.02016 0.24086 0.43130 0.55733 k4 0.36012 0.51418 0.46350 0.24017 0.57754 0.19701 k5 0.72756 0.24015 0.17283 0.07471 0.24001 0.33511 ---- 62 VARIABLE z.L = 0.10539 objective This model can be solved with Gurobi. Cplex does not allow non-convex quadratic constraints.3d solution
LINEAR FORMULATION BY SET COVERING This formulation was inspired by the comments by Rob Pratt below. The idea is to generate all possible rectangles in advance. We pick two arbitrary points to determine the horizontal part of the rectangle and two arbitrary points to determine the vertical part of the rectangle. This would mean (502)×(502)=1,500,625(502)×(502)=1,500,625 rectangles. In addition, we need to keep track of which points are covered by each rectangle kk. Let's introduce: si,k={1if point i is covered by rectangle k0otherwisesi,k={1if point i is covered by rectangle k0otherwise The resulting model is min∑kxkareak∑kxk=5∑ksi,kxk≥1∀ixk∈{0,1}min∑kxkareak∑kxk=5∑ksi,kxk≥1∀ixk∈{0,1} This is now a very large, but very easy linear MIP model.Notes:
* As we generate all rectangles in advance, we can also calculate the area (or volume) in advance. That explains why the model becomeslinear.
* Note that the horizontal pair of points x1,x2x1,x2 can be identical to the vertical pair y1,y2y1,y2. They are drawnindependently.
* We did not generate rectangles with just a single point. We caneasily add them.
* When generating two "horizontal" points x1,x2x1,x2 and two "vertical" points y1,y2y1,y2, one or more of the points may be outside the resulting box. We can just drop that candidate rectangle. See the picture below. Note that elsewhere in the generation process we will form the rectangle: y1,x2y1,x2 in the xx direction and x1,y1x1,y1 inthe yy direction.
* So: we generated more rectangles than needed if we did not drop cases like in the previous bullet. A little bit more logic is needed to prevent these unneeded rectangles. Note this will not change the solution. We just will generate a smaller model. * I think if you do this right, then just 50,658 rectangles will be generated. This means we could discard 96.6% of the candidaterectangles!
* This can be extended to larger dimensions. I expect the total number of possible boxes can become very large, very quickly. This candidate rectangle is dropped from consideration.REFERENCES
* How can I find k minimum bounding rectangles to enclose all thegiven
points?, https://stackoverflow.com/questions/60401171/how-can-i-find-k-minimum-bounding-rectangles-to-enclose-all-the-given-points * Non-convex Quadratic Models, http://yetanothermathprogrammingconsultant.blogspot.com/2020/02/non-convex-quadratic-models.html Posted by Erwin Kalvelagenat 1:57 AM
8 comments:
Links to this post
Labels: MINLP
,
MIQCP
,
MIQP
,
non-convex optimizationOlder Posts
Home
Subscribe to: Posts (Atom)ABOUT ME
* Erwin Kalvelagen
View my complete profileHOME PAGE
Amsterdam Optimization Modeling Group LLCBLOG ARCHIVE
* ▼ 2020
(11)
* ▼ March
(3)
* CellBlock or Shikaku puzzle* Tiling
* Non-convex quadratic models II: rectangular coveri...* ► February
(2)
* ► January
(6)
* ► 2019
(50)
* ► December
(5)
* ► November
(5)
* ► October
(5)
* ► September
(2)
* ► August
(5)
* ► July
(3)
* ► June
(4)
* ► May
(5)
* ► April
(4)
* ► March
(2)
* ► February
(4)
* ► January
(6)
* ► 2018
(79)
* ► December
(4)
* ► November
(4)
* ► October
(6)
* ► September
(4)
* ► August
(5)
* ► July
(7)
* ► June
(4)
* ► May
(11)
* ► April
(11)
* ► March
(9)
* ► February
(6)
* ► January
(8)
* ► 2017
(94)
* ► December
(8)
* ► November
(6)
* ► October
(8)
* ► September
(8)
* ► August
(3)
* ► July
(6)
* ► June
(5)
* ► May
(11)
* ► April
(11)
* ► March
(12)
* ► February
(7)
* ► January
(9)
* ► 2016
(166)
* ► December
(15)
* ► November
(12)
* ► October
(18)
* ► September
(11)
* ► August
(12)
* ► July
(6)
* ► June
(13)
* ► May
(21)
* ► April
(13)
* ► March
(13)
* ► February
(17)
* ► January
(15)
* ► 2015
(80)
* ► December
(15)
* ► November
(8)
* ► October
(7)
* ► September
(1)
* ► August
(3)
* ► July
(4)
* ► June
(8)
* ► May
(3)
* ► April
(8)
* ► March
(8)
* ► February
(6)
* ► January
(9)
* ► 2014
(45)
* ► December
(6)
* ► November
(6)
* ► October
(2)
* ► September
(6)
* ► August
(2)
* ► July
(3)
* ► June
(3)
* ► May
(1)
* ► April
(7)
* ► March
(2)
* ► February
(5)
* ► January
(2)
* ► 2013
(72)
* ► December
(1)
* ► November
(1)
* ► October
(3)
* ► September
(2)
* ► August
(4)
* ► July
(6)
* ► June
(9)
* ► May
(10)
* ► April
(5)
* ► March
(7)
* ► February
(9)
* ► January
(15)
* ► 2012
(86)
* ► December
(12)
* ► November
(7)
* ► October
(10)
* ► September
(4)
* ► August
(10)
* ► July
(7)
* ► June
(2)
* ► May
(4)
* ► April
(7)
* ► March
(11)
* ► February
(7)
* ► January
(5)
* ► 2011
(76)
* ► December
(9)
* ► November
(10)
* ► October
(10)
* ► September
(7)
* ► August
(4)
* ► July
(9)
* ► June
(6)
* ► May
(6)
* ► April
(6)
* ► March
(1)
* ► February
(6)
* ► January
(2)
* ► 2010
(89)
* ► December
(5)
* ► November
(2)
* ► October
(10)
* ► September
(4)
* ► August
(7)
* ► July
(8)
* ► June
(10)
* ► May
(9)
* ► April
(8)
* ► March
(10)
* ► February
(7)
* ► January
(9)
* ► 2009
(194)
* ► December
(12)
* ► November
(10)
* ► October
(11)
* ► September
(17)
* ► August
(9)
* ► July
(15)
* ► June
(18)
* ► May
(22)
* ► April
(21)
* ► March
(29)
* ► February
(14)
* ► January
(16)
* ► 2008
(197)
* ► December
(16)
* ► November
(9)
* ► October
(24)
* ► September
(16)
* ► August
(16)
* ► July
(30)
* ► June
(48)
* ► May
(38)
SEARCH THIS BLOG
Simple theme. Powered by Blogger .Details
Copyright © 2024 ArchiveBay.com. All rights reserved. Terms of Use | Privacy Policy | DMCA | 2021 | Feedback | Advertising | RSS 2.0