Problem.java

package xmtrclusters;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * Problem holds the data for a problem instance.
 *
 * @author Paul A. Rubin (rubin@msu.edu)
 */
public final class Problem {
  private final int nTrans;         // # of transmitters
  private final int nUsers;         // # of users
  private final int maxClusters;    // maximum # of clusters
  private final int maxSize;        // maximum # of transmitters per cluster
  private final double[][] weight;  // weight for transmitter-user pair
  private final int[] best;         // index of best transmitter for each user
  private final List<Integer> allTransmitters;  // list of all transmitters
  private final double[] maxQuality;  // maximum possible user for each user
  private final HashMap<Integer, Set<Integer>> assignedUsers;
    // maps each transmitter to the users best served by it

  /**
   * Constructs a random problem instance.
   * @param nT the number of transmitters
   * @param nU the number of users
   * @param maxC the maximum number of clusters
   * @param maxT the maximum number of transmitters
   * @param seed the seed for the random number generator.
   */
  public Problem(final int nT, final int nU, final int maxC, final int maxT,
                 final int seed) {
    // Set the problem dimensions.
    nTrans = nT;
    nUsers = nU;
    maxClusters = maxC;
    maxSize = maxT;
    weight = new double[nTrans][nUsers];
    best = new int[nUsers];
    allTransmitters = IntStream.range(0, nTrans).boxed()
                               .collect(Collectors.toList());
    assignedUsers = new HashMap<>();
    for (int t = 0; t < nTrans; t++) {
      assignedUsers.put(t, new HashSet<>());
    }
    // Assign service quality values (weights) randomly and determine the
    // best transmitter for each user.
    Random rng = new Random(seed);
    for (int u = 0; u < nUsers; u++) {
      double z = -1;
      for (int t = 0; t < nTrans; t++) {
        weight[t][u] = rng.nextDouble();
        if (weight[t][u] > z) {
          best[u] = t;
          z = weight[t][u];
        }
      }
      assignedUsers.get(best[u]).add(u);
    }
    // The maximum quality for each user occurs when the worst transmitter for
    // that user is the only transmitter not in the user's cluster.
    maxQuality = new double[nUsers];
    for (int u = 0; u < nUsers; u++) {
      double worst = Double.MAX_VALUE;
      int w = -1;
      for (int t = 0; t < nTrans; t++) {
        if (weight[t][u] < worst) {
          worst = weight[t][u];
          w = t;
        }
      }
      HashSet<Integer> c = new HashSet<>(allTransmitters);
      c.remove(w);
      maxQuality[u] = userQuality(u, c);
    }
  }

  /**
   * Computes the service quality for a single user.
   * @param user the index of the user
   * @param cluster the indices of all transmitters in the same cluster as the
   * user
   * @return the service quality for the user
   */
  public double userQuality(final int user, final Collection<Integer> cluster) {
    // Make sure at least one transmitter is not in the cluster (to avoid
    // division by zero).
    if (cluster.size() == nTrans) {
      throw new IllegalArgumentException("Cannot have all transmitters"
                                         + " in one cluster.");
    }
    // The numerator is the sum of weights for all transmitters in the cluster.
    double num = cluster.stream().mapToDouble(t -> weight[t][user]).sum();
    // The denominator is the sum of weights for all transmitters not in
    // the cluster.
    HashSet<Integer> out = new HashSet<>(allTransmitters);
    out.removeAll(cluster);
    double denom = out.stream().mapToDouble(t -> weight[t][user]).sum();
    return num / denom;
  }

  /**
   * Generates a summary of a solution.
   * @param solution the solution (a collection of clusters of transmitters)
   * @return a string summarizing the solution.
   */
  public String report(final Collection<Collection<Integer>> solution) {
    StringBuilder sb = new StringBuilder();
    sb.append("The solution has ").append(solution.size())
      .append(" clusters.\n");
    for (Collection<Integer> cluster : solution) {
      sb.append("\tCluster ")
        .append(Arrays.toString(cluster.stream().sorted()
                                       .mapToInt(i -> i).toArray()))
        .append(" serves ");
      ArrayList<Integer> list = new ArrayList<>();
      cluster.stream().forEach(t -> list.addAll(assignedUsers.get(t)));
      sb.append(Arrays.toString(list.stream().sorted()
                                    .mapToInt(i -> i).toArray()))
        .append("\n");
    }
    sb.append("\nOverall quality = ").append(totalQuality(solution))
                                     .append(".");
    return sb.toString();
  }

  /**
   * Gets the number of transmitters.
   * @return the number of transmitters
   */
  public int getNTrans() {
    return nTrans;
  }

  /**
   * Gets the number of users.
   * @return the number of users
   */
  public int getNUsers() {
    return nUsers;
  }

  /**
   * Gets the maximum number of clusters.
   * @return the maximum number of clusters
   */
  public int getMaxClusters() {
    return maxClusters;
  }

  /**
   * Gets the maximum cluster size.
   * @return the maximum cluster size
   */
  public int getMaxSize() {
    return maxSize;
  }

  /**
   * Gets the maximum possible quality for each user.
   * @return the vector of quality bounds
   */
  public double[] getMaxQuality() {
    return Arrays.copyOf(maxQuality, maxQuality.length);
  }

  /**
   * Gets the indices of the best transmitters for each user.
   * @return the vector of best transmitter indices
   */
  public int[] getBest() {
    return Arrays.copyOf(best, best.length);
  }

  /**
   * Gets the weights for a given user.
   * @param user the index of the user
   * @return the vector of weights for all transmitters and that user
   */
  public double[] getWeights(final int user) {
    return allTransmitters.stream().mapToDouble(t -> weight[t][user]).toArray();
  }

  /**
   * Computes the total quality of a proposed solution.
   * @param clusters a collection of clusters
   * @return the total user quality for that solution
   */
  public double totalQuality(final Collection<Collection<Integer>> clusters) {
    return clusters.stream().mapToDouble(c -> clusterQuality(c)).sum();
  }

  /**
   * Computes the total quality measure for all users in a cluster.
   * @param cluster the cluster of transmitters
   * @return the total quality for users in that cluster
   */
  public double clusterQuality(final Collection<Integer> cluster) {
    // Find the users in the cluster.
    ArrayList<Integer> list = new ArrayList<>();
    cluster.stream().forEach(t -> list.addAll(assignedUsers.get(t)));
    // Total their quality values.
    return list.stream().mapToDouble(u -> userQuality(u, cluster)).sum();
  }
}