DistanceModel2.java

package models;

import ilog.concert.IloException;
import ilog.concert.IloLinearNumExpr;
import ilog.concert.IloNumVar;
import ilog.cplex.IloCplex;
import java.util.HashSet;
import java.util.Set;
import socialnet.Graph;

/**
 * DistanceModel implements the binary integer program proposed by the author
 * of the problem, modified using a suggestion from Rob Pratt.
 *
 * @author Paul A. Rubin (rubin@msu.edu)
 */
public final class DistanceModel2 implements AutoCloseable {
  private static final double HALF = 0.5;  // for rounding tests
  private final int nVertices;  // number of vertices in the graph
  private final int diameter;   // the graph diameter

  // CPLEX objects.
  private final IloCplex mip;        // the MIP model
  private final IloNumVar[][] x;     // x[v][d] = 1 if vertex v has distance d
                                     // to the selection set

  /**
   * Constructor.
   * @param graph the source graph
   * @param nSelect the number of nodes to select
   * @throws IloException if model construction fails
   */
  public DistanceModel2(final Graph graph, final int nSelect)
         throws IloException {
    nVertices = graph.getnVertices();
    diameter = graph.getDiameter();
    // Initialize the model.
    mip = new IloCplex();
    // Create the variables and simultaneously set up the objective function.
    x = new IloNumVar[nVertices][diameter + 1];
    IloLinearNumExpr obj = mip.linearNumExpr();
    for (int i = 0; i < nVertices; i++) {
      for (int d = 0; d <= diameter; d++) {
        x[i][d] = mip.boolVar("x_" + i + "_" + d);
        obj.addTerm(d, x[i][d]);
      }
    }
    // Add the objective function.
    mip.addMinimize(obj);
    // The number of variables selected (having distance 0 to the selection
    // set) must be correct.
    IloLinearNumExpr expr = mip.linearNumExpr();
    for (int i = 0; i < nVertices; i++) {
      expr.addTerm(1.0, x[i][0]);
    }
    mip.addEq(expr, nSelect, "selection_size");
    // Every node has exactly one distance to the selection set.
    for (int i = 0; i < nVertices; i++) {
      mip.addEq(mip.sum(x[i]), 1.0, "unique_distance_" + i);
    }
    // Rob Pratt's modification: For a node to be at distance d from the
    // selection set, one of its neighbors must be at distance d-1.
    for (int i = 0; i < nVertices; i++) {
      for (int d = 1; d <= diameter; d++) {
        // Sum the indicators for neighbors being at distance d-1.
        expr = mip.linearNumExpr();
        for (int j : graph.getNeighborhood(i, 1)) {
          expr.addTerm(1.0, x[j][d - 1]);
        }
        mip.addLe(x[i][d], expr, "distance_" + i + "_" + d);
      }
    }
  }

  /**
   * Solves the model.
   * @param timeLimit the time limit for the solver (in seconds)
   * @return the final solver status
   * @throws IloException if the solution fails
   */
  public IloCplex.Status solve(final double timeLimit) throws IloException {
    mip.setParam(IloCplex.DoubleParam.TimeLimit, timeLimit);
    mip.solve();
    return mip.getStatus();
  }

  /**
   * Gets the final objective value.
   * @return the objective value
   * @throws IloException if there is no objective value
   */
  public double getObjValue() throws IloException {
    return mip.getObjValue();
  }

  /**
   * Gets the set of nodes selected by the solution.
   * @return the set of selected nodes
   * @throws IloException if no solution exists
   */
  public Set<Integer> getSolution() throws IloException {
    HashSet<Integer> sol = new HashSet<>();
    for (int i = 0; i < nVertices; i++) {
      if (mip.getValue(x[i][0]) > HALF) {
        sol.add(i);
      }
    }
    return sol;
  }

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

}