T-Packing

tpack.cc

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

#define fst first
#define snd second

#include <ilcplex/ilocplex.h>
ILOSTLBEGIN

int main() {
  int n = 6, m = 6;
  
  typedef vector< pair<int, int> > piece;
  vector<piece> all;
  int di[] = {1,0,-1,0}, dj[] = {0,1,0,-1};
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      for (int k = 0; k < 4; ++k) {
        piece x;
        x.push_back({i,j});
        for (int l = 0; l < 4; ++l) 
          if (k != l) x.push_back({i+di[l], j+dj[l]});
        all.push_back(x);
      }
    }
  }
  all.erase(remove_if(all.begin(), all.end(),
        [&n,&m](const piece &x) {
          for (auto a: x) {
            if (a.fst < 0 || a.snd < 0 ||
                a.fst >= n || a.snd >= m) return true;
          }
          return false;
        }), all.end());

  cout << all.size() << endl;

  IloEnv env;
  IloModel model(env);
  IloNumVarArray vars(env);
  IloRangeArray cond(env);
 
  for (int i = 0; i < all.size(); ++i) 
    vars.add(IloBoolVar(env));
 
  IloExpr objFunc(env);
  for (int i = 0; i < all.size(); ++i) 
    objFunc += vars[i];
  model.add(IloMaximize(env, objFunc));
 
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      IloExpr cij(env);
      for (int k = 0; k < all.size(); ++k) {
        if (find(all[k].begin(), all[k].end(), make_pair(i,j)) != all[k].end())
          cij += vars[k];
      }
      cond.add(cij <= 1);
    }
  }
  model.add(cond);
  IloCplex cplex(model);
  cplex.solve();
 
  IloNumArray vals(env);
  cplex.getValues(vals, vars);
  env.out() << "Solution status = " << cplex.getStatus() << endl;
  env.out() << "Solution value = " << cplex.getObjValue() << endl;
  env.out() << "Value = " << vals << endl;
 
  for (int i = 0; i < all.size(); ++i) {
    if (vals[i]) {
      for (auto a: all[i]) 
        cout << "(" << a.fst << "," << a.snd << ") ";
      cout << endl;
    }
  }
 
  env.end();
}

/*
80
Found incumbent of value 0.000000 after 0.00 sec. (0.01 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 4 rows and 33 columns.
MIP Presolve modified 16 coefficients.
Reduced MIP has 32 rows, 48 columns, and 184 nonzeros.
Reduced MIP has 48 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.20 ticks)
Probing time = 0.00 sec. (0.08 ticks)
Tried aggregator 1 time.
Presolve time = 0.00 sec. (0.09 ticks)
Probing time = 0.00 sec. (0.08 ticks)
Clique table members: 32.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 32 threads.
Root relaxation solution time = 0.00 sec. (0.24 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                            0.0000       48.0000       54     --- 
*     0+    0                            8.0000       48.0000       54  500.00%
      0     0        8.6667    28        8.0000        8.6667       54    8.33%
      0     0        cutoff              8.0000        8.6667       54    8.33%
Elapsed time = 0.01 sec. (0.81 ticks, tree = 0.00 MB, solutions = 2)

Root node processing (before b&c):
  Real time             =    0.00 sec. (0.40 ticks)
Parallel b&c, 32 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.00 sec. (0.40 ticks)
Solution status = Optimal
Solution value = 8
Value = [1, 0, 0, 1, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 0, 0, 0, 0, 1, 0,
0, 0, 0, 0, 1, 0, 0, 0, 0, 0]
(0,1) (1,1) (0,2) (0,0) 
(0,4) (1,4) (0,5) (0,3) 
(2,0) (3,0) (2,1) (1,0) 
(2,2) (3,2) (2,3) (1,2) 
(2,5) (3,5) (1,5) (2,4) 
(4,1) (5,1) (3,1) (4,0) 
(4,3) (5,3) (3,3) (4,2) 
(4,4) (5,4) (4,5) (3,4) 
*/