P-median¶

/********** Pmedian.java **********/

import java.util.*;
import java.io.*;
import localsolver.*;


public class Pmedian{

    /* Number of locations */
    int N;
    
    /* Number of edges between locations. */
    int E;
    
    /* Size of the subset S of locations. */
    int p;
    
    /* Weight matrix of the shortest path between locations. */
    int[][] w;

    /* Maximum distance between two locations. */
    int wmax;

    /* LocalSolver. */
    LocalSolver localsolver;

    /* Decisions variables */
    LSExpression[] x;

    /* Objective */
    LSExpression totalCost;

    /* List of selected locations */
    List<Integer> solution;

    /* Reads instance data. */
    void readInstance(String fileName){
        try{
            Scanner input = new Scanner(new File(fileName));
            N = input.nextInt();
            E = input.nextInt();
            p = input.nextInt();

            w = new int[N][N];
            wmax = 0;
            for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                    w[i][j] = input.nextInt();
                    if(w[i][j] > wmax)
                    wmax = w[i][j];
                }
            }
        } catch(IOException e){
            e.printStackTrace();
        }
    }

    /* Declares the optimization model. */
    void solve(int limit){
        try{
            localsolver = new LocalSolver();
            LSModel model = localsolver.getModel();

            // Boolean decisions
            x = new LSExpression[N];
            for(int i = 0; i < N; i++) {
                x[i] = model.boolVar();
            }

            // No more than p locations are selected
            LSExpression openedLocations = model.sum();
            for(int i = 0; i < N; i++) {
                openedLocations.addOperand(x[i]);
            }

            model.constraint(model.leq(openedLocations,p));

            // Costs between location i and j is w[i][j] if j is selected in S or 2*wmax if not
            LSExpression[][] costs = new LSExpression[N][N];
            for(int i = 0; i < N; i++) {
                for(int j = 0; j < N; j++) {
                    costs[i][j] = model.iif(x[j], w[i][j], 2*wmax);
                }
            }

            // Cost between location i and the closest selected location
            LSExpression[] cost = new LSExpression[N];
            for(int i = 0; i < N; i++) {
                cost[i] = model.min();
                for(int j = 0; j < N; j++) {
                    cost[i].addOperand(costs[i][j]);
                }
            }
        
            // Minimize the total cost
            totalCost = model.sum();
            for(int i = 0; i < N; i++){
                totalCost.addOperand(cost[i]);
            }
            model.minimize(totalCost);

            model.close();

            /* Parameterizes the solver. */
            LSPhase phase = localsolver.createPhase();
            phase.setTimeLimit(limit);
            localsolver.solve();

            solution = new ArrayList<Integer>();
            for(int i = 0; i < N; i++){
                if(x[i].getValue() == 1)
                    solution.add(i);
            }
        } catch(LSException e){
            System.out.println("LSException:" + e.getMessage());
            System.exit(1);
        }
    }

    /* Writes the solution in a file following the following format: 
     * - value of the objective
     * - indiced of the selected locations (between 0 and N-1) */
    void writeSolution(String fileName){
        try{
            BufferedWriter output = new BufferedWriter(new FileWriter(fileName));
            output.write(totalCost.getValue() + "\n");
            for (int i = 0; i < solution.size(); i++){
                output.write(solution.get(i) + " " );
            }
            output.write("\n");
            output.close();
        } catch(IOException e){
            e.printStackTrace();
        }
    }

    public static void main(String[] args){
        if (args.length < 1) {
            System.out.println("Usage: java Pmedian inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "10";

        Pmedian model = new Pmedian();
        model.readInstance(instanceFile);
        model.solve(Integer.parseInt(strTimeLimit));
        if(outputFile != null) {
            model.writeSolution(outputFile);
        }
    }
}