Square soft packing problem
Brief description
The problem is almost identical to the square packing problem with the difference that we now allow overlaps but we want to minimize them.
CFN model
We reuse the Square packing problem model except that binary constraints are replaced by cost functions returning the overlapping size or zero if no overlaps.
To calculate an initial upper bound we simply compute the worst case scenario where N squares of size N*N are all stacked together. The cost of this is N**4, so we will take N**4+1 as the initial upper bound.
Python model
The following code using pytoulbar2 library solves the corresponding cost function network (e.g. “python3 squaresoft.py 10 20”).
import sys
from random import randint, seed
seed(123456789)
import pytoulbar2
try:
N = int(sys.argv[1])
S = int(sys.argv[2])
assert N <= S
except:
print('Two integers need to be given as arguments: N and S')
exit()
Problem = pytoulbar2.CFN(N**4 + 1)
#create a variable for each square
for i in range(N):
Problem.AddVariable('sq' + str(i+1), ['(' + str(l) + ',' + str(j) + ')' for l in range(S-i) for j in range(S-i)])
#binary soft constraints for overlapping squares
for i in range(N):
for j in range(i+1,N):
ListConstraintsOverlaps = []
for a in [S*k+l for k in range(S-i) for l in range(S-i)]:
for b in [S*m+n for m in range(S-j) for n in range(S-j)]:
#calculating the coordinates of the squares
X_i = a%S
X_j = b%S
Y_i = a//S
Y_j = b//S
#calculating if squares are overlapping
if X_i >= X_j :
if X_i - X_j < j+1:
if Y_i >= Y_j:
if Y_i - Y_j < j+1:
ListConstraintsOverlaps.append(min(j+1-(X_i - X_j),i+1)*min(j+1-(Y_i - Y_j),i+1))
else:
ListConstraintsOverlaps.append(0)
else:
if Y_j - Y_i < i+1:
ListConstraintsOverlaps.append(min(j+1-(X_i - X_j),i+1)*min(i+1-(Y_j - Y_i),j+1))
else:
ListConstraintsOverlaps.append(0)
else:
ListConstraintsOverlaps.append(0)
else :
if X_j - X_i < i+1:
if Y_i >= Y_j:
if Y_i - Y_j < j+1:
ListConstraintsOverlaps.append(min(i+1-(X_j - X_i),j+1)*min(j+1-(Y_i - Y_j),i+1))
else:
ListConstraintsOverlaps.append(0)
else:
if Y_j - Y_i < i+1:
ListConstraintsOverlaps.append(min(i+1-(X_j - X_i),j+1)*min(i+1-(Y_j - Y_i),j+1))
else:
ListConstraintsOverlaps.append(0)
else:
ListConstraintsOverlaps.append(0)
Problem.AddFunction(['sq' + str(i+1), 'sq' + str(j+1)], ListConstraintsOverlaps)
#Problem.Dump('SquareSoft.cfn')
Problem.CFN.timer(300)
res = Problem.Solve(showSolutions=3)
if res:
for i in range(S):
row = ''
for j in range(S):
row += ' '
for k in range(N-1, -1, -1):
if (res[0][k]%(S-k) <= j and j - res[0][k]%(S-k) <= k) and (res[0][k]//(S-k) <= i and i - res[0][k]//(S-k) <= k):
row = row[:-1] + chr(65 + k)
print(row)
else:
print('No solution found!')
C++ program using libtb2.so
The following code uses the C++ toulbar2 library. Compile toulbar2 with “cmake -DLIBTB2=ON -DPYTB2=ON . ; make” and copy the library in your current directory “cp lib/Linux/libtb2.so .” before compiling “g++ -o squaresoft squaresoft.cpp -I./src -L./lib/Linux -std=c++11 -O3 -DNDEBUG -DBOOST -DLONGDOUBLE_PROB -DLONGLONG_COST -DWCSPFORMATONLY libtb2.so” and running the example (e.g. “./squaresoft 10 20”).
/**
* Square Soft Packing Problem
*/
// Compile with cmake option -DLIBTB2=ON -DPYTB2=ON to get C++ toulbar2 library lib/Linux/libtb2.so
// Then,
// g++ -o squaresoft squaresoft.cpp -Isrc -Llib/Linux -std=c++11 -O3 -DNDEBUG -DBOOST -DLONGDOUBLE_PROB -DLONGLONG_COST -DWCSPFORMATONLY libtb2.so
#include "toulbar2lib.hpp"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int main(int argc, char* argv[])
{
int N = atoi(argv[1]);
int S = atoi(argv[2]);
tb2init(); // must be call before setting specific ToulBar2 options and creating a model
ToulBar2::verbose = 0; // change to 0 or higher values to see more trace information
initCosts(); // last check for compatibility issues between ToulBar2 options and Cost data-type
Cost top = N*(N*(N-1)*(2*N-1))/6 + 1;
WeightedCSPSolver* solver = WeightedCSPSolver::makeWeightedCSPSolver(top);
for (int i=0; i < N; i++) {
solver->getWCSP()->makeEnumeratedVariable("sq" + to_string(i+1), 0, (S-i)*(S-i) - 1);
}
for (int i=0; i < N; i++) {
for (int j=i+1; j < N; j++) {
vector<Cost> costs((S-i)*(S-i)*(S-j)*(S-j), MIN_COST);
for (int a=0; a < (S-i)*(S-i); a++) {
for (int b=0; b < (S-j)*(S-j); b++) {
costs[a*(S-j)*(S-j)+b] = ((((a%(S-i)) + i + 1 <= (b%(S-j))) || ((b%(S-j)) + j + 1 <= (a%(S-i))) || ((a/(S-i)) + i + 1 <= (b/(S-j))) || ((b/(S-j)) + j + 1 <= (a/(S-i))))?MIN_COST:(min((a%(S-i)) + i + 1 - (b%(S-j)), (b%(S-j)) + j + 1 - (a%(S-i))) * min((a/(S-i)) + i + 1 - (b/(S-j)), (b/(S-j)) + j + 1 - (a/(S-i)))));
}
}
solver->getWCSP()->postBinaryConstraint(i, j, costs);
}
}
solver->getWCSP()->sortConstraints(); // must be done at the end of the modeling
tb2checkOptions();
if (solver->solve()) {
vector<Value> sol;
solver->getSolution(sol);
for (int y=0; y < S; y++) {
for (int x=0; x < S; x++) {
char c = ' ';
for (int i=N-1; i >= 0; i--) {
if (x >= (sol[i]%(S-i)) && x < (sol[i]%(S-i) ) + i + 1 && y >= (sol[i]/(S-i)) && y < (sol[i]/(S-i)) + i + 1) {
if (c != ' ') {
c = 97+i;
} else {
c = 65+i;
}
}
}
cout << c;
}
cout << endl;
}
} else {
cout << "No solution found!" << endl;
}
delete solver;
return 0;
}