patternMinor
Maximize enclosed area of given figures on 2d grid
Viewed 0 times
gridfiguresmaximizeenclosedgivenarea
Problem
I need to solve an optimization problem for a given set of polyominoes, for example the five Tetrominoes known from Tetris. The goal is to place each one of the figures on the 2d grid, so the area they enclose is maximal.
Staying with our Tetromino example, the optimal solution would be:
Bruteforcing the problem becomes unfeaseable very quickly, especially since my check with bfs search alone that an area is even enclosed at all must be performed countless times. I tried to implement systems to recognize when it won't be possible to close the circle with the remaining polyominoes, but didn't achieve a significant speed-up with them.
I also researched into strategies for the related polyomino tiling problem to see if I can adapt them, but had no success so far. The most promising approach I found was to translate it into Mixed-Integer Linear Programming like here or in this variation. But to apply this approach to my problem I need to both add the restriction of the enclosed area and then formulate its size as a linear objective function, whereby especially the encoding of the latter may not be possible at all.
Are there other algorithms to find the global maximum for this type of optimization problem that I've overlooked? Or are there data structures or strategies for branch elimination to drastically speed up the search of all possibilities?
Staying with our Tetromino example, the optimal solution would be:
Bruteforcing the problem becomes unfeaseable very quickly, especially since my check with bfs search alone that an area is even enclosed at all must be performed countless times. I tried to implement systems to recognize when it won't be possible to close the circle with the remaining polyominoes, but didn't achieve a significant speed-up with them.
I also researched into strategies for the related polyomino tiling problem to see if I can adapt them, but had no success so far. The most promising approach I found was to translate it into Mixed-Integer Linear Programming like here or in this variation. But to apply this approach to my problem I need to both add the restriction of the enclosed area and then formulate its size as a linear objective function, whereby especially the encoding of the latter may not be possible at all.
Are there other algorithms to find the global maximum for this type of optimization problem that I've overlooked? Or are there data structures or strategies for branch elimination to drastically speed up the search of all possibilities?
Solution
In case anyone is interested, this is the solution implemented with https://github.com/afish/MilpManager
It's inspired by https://cs.stackexchange.com/a/153823/79175 (including the discussions we had in the comments).
Source code:
```
var integerWidth = 15;
var epsilon = 0.001;
var storeDebugExpressions = false;
var cacheConstants = false;
var storeDebugConstraints = false;
var solver = new CplexMilpSolver(new CplexMilpSolverSettings
{
IntegerWidth = integerWidth,
Epsilon = epsilon,
StoreDebugExpressions = storeDebugExpressions,
CacheConstants = cacheConstants,
StoreDebugConstraints = storeDebugConstraints
});
solver.Cplex.SetParam(ILOG.CPLEX.Cplex.Param.MIP.Tolerances.Integrality, 0.000000000001);
var pieces = new []{
new []{
"XX",
"X ",
"X "
},
new[]{
" XX",
"XX "
},
new[]{
"XX ",
" XX"
},
new[]{
"X ",
"XX",
"X "
},
new[]{
"XX",
"XX"
},
new[]{
"XXXX"
},
new[]{
"X ",
"X ",
"XX"
}
};
var totalLength = pieces.Select(p => (int)Math.Max(p.Length, p[0].Length)).Sum();
var maxLength = pieces.Max(p => (int)Math.Max(p.Length, p[0].Length));
var width = 11; // Or totalLength + 2 to make sure it's big enough for any shapes
var height = 9; // Or totalLength + 2 to make sure it's big enough for any shapes
var piecesCount = pieces.Length;
// Right, down, left, up
var directions = 4;
var heads = Enumerable.Range(0, height).Select(h =>
Enumerable.Range(0, width).Select(w =>
Enumerable.Range(0, piecesCount).Select(p =>
Enumerable.Range(0, directions).Select(d =>
solver.CreateAnonymous(Domain.BinaryInteger)
).ToArray()
).ToArray()
).ToArray()
).ToArray();
var isInterior = Enumerable.Range(0, height).Select(h =>
Enumerable.Range(0, width).Select(w =>
solver.CreateAnonymous(Domain.BinaryInteger)
).ToArray()
).ToArray();
var isBoundary = Enumerable.Range(0, height).Select(h =>
Enumerable.Range(0, width).Select(w =>
solver.CreateAnonymous(Domain.BinaryInteger)
).ToArray()
).ToArray();
Func rotatePiece = (piece, direction) => {
if(direction == 0){
return piece;
}else if(direction == 2){
return piece.Select(l => string.Join("", l.Reverse())).Reverse().ToArray();
}else if(direction == 1){
return Enumerable.Range(0, piece[0].Length)
.Select(c => string.Join("", Enumerable.Range(0, piece.Length).Select(w => piece[piece.Length - 1 - w][c])))
.ToArray();
}else {
return Enumerable.Range(0, piece[0].Length)
.Select(c => string.Join("", Enumerable.Range(0, piece.Length).Select(w => piece[w][piece[0].Length - 1 - c])))
.ToArray();
}
};
// Put pieces on the board
for(int p=0;p(
solver.FromConstant(1),
solver.Operation(
Enumerable.Range(0, height).SelectMany(h =>
Enumerable.Range(0, width).SelectMany(w =>
Enumerable.Range(0, directions).Select(d =>
heads[h][w][p][d]
)
)
).ToArray()
)
);
}
// Make sure pieces don't fall off the board
for(int h = 0; h = width){
heads[h][w][p][d].Set(solver.FromConstant(0));
}
}else if(d == 1){
if(h + piece.Length - 1 >= height){
heads[h][w][p][d].Set(solver.FromConstant(0));
}
}else if(d == 2){
if(w - piece[0].Length + 1 (solver.FromConstant(0));
}
}else if(d == 3){
if(h - piece.Length + 1 (solver.FromConstant(0));
}
}
}
}
}
}
// Set impacts
IList>[][] allImpacts = Enumerable.Range(0, height).Select(h =>
Enumerable.Range(0, width).Select(w =>
new List>()
).ToArray()
).ToArray();
for(int h = 0; h = 0 && finalY =0 && finalX (
solver.Operation(
allImpacts[h][w].Select(t => heads[t.Item1][t.Item2][t.Item3][t.Item4]).ToArray()
)
);
}
}
// Make sure pieces do not overlap
for(int h = 0; h (
solver.Operation(
allImpacts[h][w].Select(t => heads[t.Item1][t.Item2][t.Item3][t.Item4]).ToArray()
),
solver.FromConstant(1)
);
}
}
// Extend interior
for(int h = 0; h = height){
continue;
}
if(w + x = width){
continue;
}
solver.Set(
solver.FromConstant(1),
solver.Operation(
solver.Operation(
isInterior[h][w],
It's inspired by https://cs.stackexchange.com/a/153823/79175 (including the discussions we had in the comments).
Source code:
```
var integerWidth = 15;
var epsilon = 0.001;
var storeDebugExpressions = false;
var cacheConstants = false;
var storeDebugConstraints = false;
var solver = new CplexMilpSolver(new CplexMilpSolverSettings
{
IntegerWidth = integerWidth,
Epsilon = epsilon,
StoreDebugExpressions = storeDebugExpressions,
CacheConstants = cacheConstants,
StoreDebugConstraints = storeDebugConstraints
});
solver.Cplex.SetParam(ILOG.CPLEX.Cplex.Param.MIP.Tolerances.Integrality, 0.000000000001);
var pieces = new []{
new []{
"XX",
"X ",
"X "
},
new[]{
" XX",
"XX "
},
new[]{
"XX ",
" XX"
},
new[]{
"X ",
"XX",
"X "
},
new[]{
"XX",
"XX"
},
new[]{
"XXXX"
},
new[]{
"X ",
"X ",
"XX"
}
};
var totalLength = pieces.Select(p => (int)Math.Max(p.Length, p[0].Length)).Sum();
var maxLength = pieces.Max(p => (int)Math.Max(p.Length, p[0].Length));
var width = 11; // Or totalLength + 2 to make sure it's big enough for any shapes
var height = 9; // Or totalLength + 2 to make sure it's big enough for any shapes
var piecesCount = pieces.Length;
// Right, down, left, up
var directions = 4;
var heads = Enumerable.Range(0, height).Select(h =>
Enumerable.Range(0, width).Select(w =>
Enumerable.Range(0, piecesCount).Select(p =>
Enumerable.Range(0, directions).Select(d =>
solver.CreateAnonymous(Domain.BinaryInteger)
).ToArray()
).ToArray()
).ToArray()
).ToArray();
var isInterior = Enumerable.Range(0, height).Select(h =>
Enumerable.Range(0, width).Select(w =>
solver.CreateAnonymous(Domain.BinaryInteger)
).ToArray()
).ToArray();
var isBoundary = Enumerable.Range(0, height).Select(h =>
Enumerable.Range(0, width).Select(w =>
solver.CreateAnonymous(Domain.BinaryInteger)
).ToArray()
).ToArray();
Func rotatePiece = (piece, direction) => {
if(direction == 0){
return piece;
}else if(direction == 2){
return piece.Select(l => string.Join("", l.Reverse())).Reverse().ToArray();
}else if(direction == 1){
return Enumerable.Range(0, piece[0].Length)
.Select(c => string.Join("", Enumerable.Range(0, piece.Length).Select(w => piece[piece.Length - 1 - w][c])))
.ToArray();
}else {
return Enumerable.Range(0, piece[0].Length)
.Select(c => string.Join("", Enumerable.Range(0, piece.Length).Select(w => piece[w][piece[0].Length - 1 - c])))
.ToArray();
}
};
// Put pieces on the board
for(int p=0;p(
solver.FromConstant(1),
solver.Operation(
Enumerable.Range(0, height).SelectMany(h =>
Enumerable.Range(0, width).SelectMany(w =>
Enumerable.Range(0, directions).Select(d =>
heads[h][w][p][d]
)
)
).ToArray()
)
);
}
// Make sure pieces don't fall off the board
for(int h = 0; h = width){
heads[h][w][p][d].Set(solver.FromConstant(0));
}
}else if(d == 1){
if(h + piece.Length - 1 >= height){
heads[h][w][p][d].Set(solver.FromConstant(0));
}
}else if(d == 2){
if(w - piece[0].Length + 1 (solver.FromConstant(0));
}
}else if(d == 3){
if(h - piece.Length + 1 (solver.FromConstant(0));
}
}
}
}
}
}
// Set impacts
IList>[][] allImpacts = Enumerable.Range(0, height).Select(h =>
Enumerable.Range(0, width).Select(w =>
new List>()
).ToArray()
).ToArray();
for(int h = 0; h = 0 && finalY =0 && finalX (
solver.Operation(
allImpacts[h][w].Select(t => heads[t.Item1][t.Item2][t.Item3][t.Item4]).ToArray()
)
);
}
}
// Make sure pieces do not overlap
for(int h = 0; h (
solver.Operation(
allImpacts[h][w].Select(t => heads[t.Item1][t.Item2][t.Item3][t.Item4]).ToArray()
),
solver.FromConstant(1)
);
}
}
// Extend interior
for(int h = 0; h = height){
continue;
}
if(w + x = width){
continue;
}
solver.Set(
solver.FromConstant(1),
solver.Operation(
solver.Operation(
isInterior[h][w],
Code Snippets
var integerWidth = 15;
var epsilon = 0.001;
var storeDebugExpressions = false;
var cacheConstants = false;
var storeDebugConstraints = false;
var solver = new CplexMilpSolver(new CplexMilpSolverSettings
{
IntegerWidth = integerWidth,
Epsilon = epsilon,
StoreDebugExpressions = storeDebugExpressions,
CacheConstants = cacheConstants,
StoreDebugConstraints = storeDebugConstraints
});
solver.Cplex.SetParam(ILOG.CPLEX.Cplex.Param.MIP.Tolerances.Integrality, 0.000000000001);
var pieces = new []{
new []{
"XX",
"X ",
"X "
},
new[]{
" XX",
"XX "
},
new[]{
"XX ",
" XX"
},
new[]{
"X ",
"XX",
"X "
},
new[]{
"XX",
"XX"
},
new[]{
"XXXX"
},
new[]{
"X ",
"X ",
"XX"
}
};
var totalLength = pieces.Select(p => (int)Math.Max(p.Length, p[0].Length)).Sum();
var maxLength = pieces.Max(p => (int)Math.Max(p.Length, p[0].Length));
var width = 11; // Or totalLength + 2 to make sure it's big enough for any shapes
var height = 9; // Or totalLength + 2 to make sure it's big enough for any shapes
var piecesCount = pieces.Length;
// Right, down, left, up
var directions = 4;
var heads = Enumerable.Range(0, height).Select(h =>
Enumerable.Range(0, width).Select(w =>
Enumerable.Range(0, piecesCount).Select(p =>
Enumerable.Range(0, directions).Select(d =>
solver.CreateAnonymous(Domain.BinaryInteger)
).ToArray()
).ToArray()
).ToArray()
).ToArray();
var isInterior = Enumerable.Range(0, height).Select(h =>
Enumerable.Range(0, width).Select(w =>
solver.CreateAnonymous(Domain.BinaryInteger)
).ToArray()
).ToArray();
var isBoundary = Enumerable.Range(0, height).Select(h =>
Enumerable.Range(0, width).Select(w =>
solver.CreateAnonymous(Domain.BinaryInteger)
).ToArray()
).ToArray();
Func<string[], int, string[]> rotatePiece = (piece, direction) => {
if(direction == 0){
return piece;
}else if(direction == 2){
return piece.Select(l => string.Join("", l.Reverse())).Reverse().ToArray();
}else if(direction == 1){
return Enumerable.Range(0, piece[0].Length)
.Select(c => string.Join("", Enumerable.Range(0, piece.Length).Select(w => piece[piece.Length - 1 - w][c])))
.ToArray();
}else {
return Enumerable.Range(0, piece[0].Length)
.Select(c => string.Join("", Enumerable.Range(0, piece.Length).Select(w => piece[w][piece[0].Length - 1 - c])))
.ToArray();
}
};
// Put pieces on the board
for(int p=0;p<piecesCount;++p){
solver.Set<Equal>(
solver.FromConstant(1),
solver.Operation<Addition>(
Enumerable.Range(0, height).SelectMany(h =>
Enumerable.Range(0, width).SelectMany(w =>
Enumerable.Range(0, directions).Select(d =>
Tried aggregator 2 times.
MIP Presolve eliminated 4659 rows and 4747 columns.
MIP Presolve modified 688 coefficients.
Aggregator did 1432 substitutions.
Reduced MIP has 809 rows, 847 columns, and 4647 nonzeros.
Reduced MIP has 847 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (10.92 ticks)
Found incumbent of value 0.000000 after 0.06 sec. (33.44 ticks)
Probing time = 0.00 sec. (2.70 ticks)
Tried aggregator 1 time.
Reduced MIP has 809 rows, 847 columns, and 4647 nonzeros.
Reduced MIP has 847 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (2.75 ticks)
Probing time = 0.02 sec. (2.69 ticks)
Clique table members: 1918.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.02 sec. (17.35 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
* 0+ 0 0.0000 35.0000 565 ---
0 0 29.7678 243 0.0000 29.7678 565 ---
* 0+ 0 2.0000 29.7678 657 ---
0 0 29.2337 242 2.0000 Cuts: 36 657 ---
* 0+ 0 3.0000 29.2337 657 874.46%
0 0 28.7133 242 3.0000 Cuts: 99 816 857.11%
0 0 28.5944 248 3.0000 Cuts: 26 881 853.15%
0 0 28.3575 243 3.0000 Cuts: 21 958 845.25%
0 0 28.1942 256 3.0000 Cuts: 27 1036 839.81%
0 0 28.1076 244 3.0000 Cuts: 25 1120 836.92%
* 0+ 0 4.0000 28.1076 1120 602.69%
0 0 28.1076 245 4.0000 Cuts: 12 1130 602.69%
0 0 28.0851 255 4.0000 Cuts: 9 1150 597.76%
0 0 27.9794 239 4.0000 Cuts: 28 1229 597.76%
0 0 27.8878 280 4.0000 Cuts: 25 1330 597.20%
0 0 27.8093 275 4.0000 Cuts: 23 1402 595.23%
0 0 27.6921 275 4.0000 Cuts: 40 1520 592.30%
0 0 27.6921 276 4.0000 Cuts: 7 1525 592.30%
* 0+ 0 20.0000 27.6921 1525 38.46%
0 2 27.6921 276 20.0000 27.6060 1525 38.03%
Elapsed time = 0.97 sec. (335.52 ticks, tree = 0.01 MB, solutions = 5)
* 5+ 5 21.0000 27.5336 1944 31.11%
* 56 40 integral 0 22.0000 27.4817 5646 24.92%
* 63+ 38 25.0000 27.4817 5959 9.93%
Clique cuts applied: 15
Cover cuts applied: 19
Implied bound cuts applied: 63Context
StackExchange Computer Science Q#153818, answer score: 2
Revisions (0)
No revisions yet.