CodeIQ https://codeiq.jp/ace/stakemura/q594 / solution: CPLEX

pangram.cc

//
// 最適解： AVG BY FETCH JOIN MAX PAD SIZE SQL SUM WORK （34文字）
// 計算にかかった時間：0.01[s]
// 解法：整数計画（IP）
//
// 解説：
//   重み付き集合被覆問題．問題のサイズが小さいのでIPで解ける．
//   ソルバーとして ILOG/CPLEX 12.5 を使用した．
//

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
using namespace std;

#include <ilcplex/ilocplex.h>

ILOSTLBEGIN

int main() {
  // read input
  vector<string> input;
  for (string s; cin >> s; ) {
    input.push_back(s);
  }
  int n = input.size(); // = 92


  // set CPLEX environment
  IloEnv env;
  IloModel model(env);
  IloNumVarArray vars(env);
  IloRangeArray cond(env);

  // define boolean variables x[0] ... x[n-1]
  for (int i = 0; i < n; ++i) 
    vars.add(IloBoolVar(env));

  // minimize the sum of length[i] * x[i]
  IloExpr objFunc(env);
  for (int i = 0; i < n; ++i) 
    objFunc += int(input[i].size()) * vars[i];
  model.add(IloMinimize(env, objFunc));

  // constraint: each character is covered at least once
  for (int j = 0; j < 26; ++j) {
    IloExpr cj(env);
    for (int i = 0; i < n; ++i) 
      if (input[i].find('A'+j) != input[i].npos) 
        cj += vars[i];
    cond.add(cj >= 1);
  }
 
  // solve IP
  model.add(cond);
  IloCplex cplex(model);
  cplex.solve();
 
  // results:
  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;

  // human readable form
  for (int i = 0; i < n; ++i) 
    if (vals[i]) cout << input[i] << endl;

  env.end();
}

/*
Execution log:

[maehara@server]% time ./main
Found incumbent of value 1248.000000 after 0.00 sec. (0.02 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 4 rows and 20 columns.
Reduced MIP has 22 rows, 194 columns, and 779 nonzeros.
Reduced MIP has 194 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.38 ticks)
Probing time = 0.00 sec. (0.05 ticks)
Tried aggregator 1 time.
MIP Presolve eliminated 0 rows and 4 columns.
Reduced MIP has 22 rows, 190 columns, and 762 nonzeros.
Reduced MIP has 190 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.32 ticks)
Probing time = 0.00 sec. (0.05 ticks)
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                         1112.0000        4.0000       40   99.64%
*     0+    0                           37.0000        4.0000       40   89.19%
      0     0       33.2000    12       37.0000       33.2000       40   10.27%
*     0+    0                           34.0000       33.2000       40    2.35%
      0     0        cutoff             34.0000       33.2000       40    2.35%
Elapsed time = 0.01 sec. (1.48 ticks, tree = 0.00 MB, solutions = 3)

Root node processing (before b&c):
  Real time             =    0.00 sec. (0.64 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.64 ticks)
Solution status = Optimal
Solution value = 34
Value = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 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,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 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, 0, 0, 0, 0, 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, 0, 0, 0, 1, 0,
0, 0, 0, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 0, 0, 0, 1, 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,
0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
0, 0, 0]
AVG
BY
FETCH
JOIN
MAX
PAD
SIZE
SQL
SUM
WORK
./main  0.01s user 0.01s system 119% cpu 0.017 total
*/