DistanceModel3.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;

/**
 * DistanceModel3 implements author's original binary integer program with
 * one modification: binary variables are indexed by vertex and distance, and
 * only the distance zero variables are binary (the others are continuous).
 *
 * @author Paul A. Rubin (rubin@msu.edu)
 */
public final class DistanceModel3 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 DistanceModel3(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++) {
      x[i][0] = mip.boolVar("x_" + i + "_0");
      for (int d = 1; d <= diameter; d++) {
        x[i][d] = mip.numVar(0, 1, "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);
    }
    // For a node to have distance d to the selection set, one of the nodes
    // at distance d from it must be in the set.
    for (int i = 0; i < nVertices; i++) {
      for (int d = 1; d <= diameter; d++) {
        // Sum the selection variables for nodes at distance d from i.
        expr = mip.linearNumExpr();
        for (int j : graph.getNeighborhood(i, d)) {
          expr.addTerm(1.0, x[j][0]);
        }
        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();
  }

}