IP.java

package setgame;

import ilog.concert.IloException;
import ilog.concert.IloLinearNumExpr;
import ilog.concert.IloNumVar;
import ilog.concert.IloRange;
import ilog.cplex.IloCplex;
import java.util.HashSet;

/**
 * IP implements an integer programming model to find all sets.
 * @author Paul A. Rubin (rubin@msu.edu)
 */
public final class IP implements AutoCloseable {
  private static final double HALF = 0.5;  // used for rounding
  private final IloCplex model;         // the MIP model
  private final IloNumVar[] include;    // indicator to include a card
  private final IloNumVar[][] appears;  // appears[i][j] = 1 if value j for
                                        // feature i appears in the set
  private final IloNumVar[] different;  // 1 if feature values all differ,
                                        // 0 if they are all the same
  private final HashSet<HashSet<Integer>> found;   // solutions found

  /**
   * Constructor.
   * @param game the game to solve
   * @throws IloException if CPLEX fails to build the model
   */
  public IP(final Set game) throws IloException {
    model = new IloCplex();
    found = new HashSet<>();
    // Define the variables.
    include = new IloNumVar[Set.NCARDS];
    appears = new IloNumVar[Set.NFEATURES][Set.NVALUES];
    different = new IloNumVar[Set.NFEATURES];
    for (int c = 0; c < Set.NCARDS; c++) {
      include[c] = model.boolVar("include_" + c);
    }
    for (int f = 0; f < Set.NFEATURES; f++) {
      different[f] = model.boolVar("all_different_" + f);
      for (int v = 0; v < Set.NVALUES; v++) {
        appears[f][v] = model.boolVar("feature_" + f + "_value_" + v);
      }
    }
    // We use the trivial objective (minimize 0).
    // Constraint: the set must have the correct size.
    model.addEq(model.sum(include), Set.SETSIZE);
    // Constraint: the number of values for any feature appearing in the set
    // must be either 1 (all the same) or the set size (all different).
    for (int f = 0; f < Set.NFEATURES; f++) {
      model.addEq(model.sum(appears[f]),
                  model.sum(1.0, model.prod(2.0, different[f])));
    }
    // Constraint: a value of a feature appears in the set if and only if
    // any card with that value is selected.
    for (int f = 0; f < Set.NFEATURES; f++) {
      for (int v = 0; v < Set.NVALUES; v++) {
        IloLinearNumExpr expr = model.linearNumExpr();
        for (int c : game.findCards(f, v)) {
          model.addGe(appears[f][v], include[c]);
          expr.addTerm(1.0, include[c]);
        }
        model.addLe(appears[f][v], expr);
      }
    }
    // Suppress output.
    model.setOut(null);
    // Avoid warm starts (which do not work).
    model.setParam(IloCplex.Param.Advance, 0);
  }

  /**
   * Solves the model.
   * @return true if the model is feasible (hence automatically optimal)
   * @throws IloException if CPLEX blows up
   */
  public boolean solve() throws IloException {
    // Allow parallel threads.
    model.setParam(IloCplex.Param.Threads, 0);
    model.solve();
    if (model.getStatus() == IloCplex.Status.Optimal) {
      // A solution was found. Recover it.
      HashSet<Integer> set = toSet(model.getValues(include));
      // Add a constraint to rule the solution out.
      model.add(exclude(set));
      return true;
    } else {
      return false;
    }
  }

  /**
   * Converts the values of "include" in a solution to a card set.
   * @param x the solution
   * @return the corresponding set
   */
  private HashSet<Integer> toSet(final double[] x) {
    HashSet<Integer> s = new HashSet<>();
    for (int c = 0; c < Set.NCARDS; c++) {
      if (x[c] > HALF) {
        s.add(c);
      }
    }
    return s;
  }

  /**
   * Solves a single model using a callback to exclude previous solutions.
   * Note: To avoid having to synchronize methods (and test whether multiple
   * threads found the same solution) we throttle the solver to a single
   * thread.
   * @return the number of solutions found.
   * @throws IloException if CPLEX blows up
   */
  public int solve2() throws IloException {
    // Clear the solution accumulator.
    found.clear();
    // Attach a callback to reject solutions.
    model.use(new Callback(), IloCplex.Callback.Context.Id.Candidate);
    // Force single threading.
    model.setParam(IloCplex.Param.Threads, 1);
    // Solve the model (stopping due to infeasibility).
    model.solve();
    // Return the solution count.
    return found.size();
  }

  /**
   * Creates a constraint to exclude an identified set.
   * @param set the set to exclude
   * @return a range constraint that excludes the set
   * @throws IloException if CPLEX gets snippy
   */
  private IloRange exclude(final HashSet<Integer> set) throws IloException {
    IloLinearNumExpr expr = model.linearNumExpr();
    for (int c : set) {
      expr.addTerm(1.0, include[c]);
    }
    return model.le(expr, Set.SETSIZE - 1);
  }

  /**
   * Closes the model.
   */
  @Override
  public void close() {
    model.close();
  }

  /**
   * Callback implements a generic callback to add no good constraints whenever
   * a set is found.
   */
  private final class Callback implements IloCplex.Callback.Function {

    /**
     * Constructor (which does nothing).
     */
    Callback() { };

    /**
     * Rejects the current candidate solution using a no-good constraint.
     * @param context the context information
     * @throws IloException if CPLEX gets snippy
     */
    @Override
    public void invoke(final IloCplex.Callback.Context context)
                       throws IloException {
      // Get the candidate set.
      double[] x = context.getCandidatePoint(include);
      // Convert it to a set.
      HashSet<Integer> s = toSet(x);
      // Add the set to the pool of solutions.
      found.add(s);
      // Turn the set into a range constraint.
      IloRange r = exclude(s);
      // Reject the solution.
      context.rejectCandidate(r);
    }

  }
}