IBM ILOG Solver User's Manual > Local Search > Combining Complete and Local Search: Locating Warehouses > Complete program

The complete program follows. You can also view the entire program online in the file YourSolverHome/examples/src/lswhouse.cpp.

 
#include <ilsolver/iimls.h>
 
ILOSTLBEGIN
 
 
// Function to read the problem from a file
 
void readProblem(IloEnv env,
                 istream &is,
                 IloInt &nbClients,
                 IloInt &nbWhouses,
                 IloIntArray &capacities,
                 IloIntArray &demands,
                 IloIntArray &buildCosts,
                 IloArray<IloIntArray> &serveCosts) {
  is >> nbWhouses >> nbClients;
  capacities = IloIntArray(env, nbWhouses);
  demands = IloIntArray(env, nbClients);
  buildCosts = IloIntArray(env, nbWhouses);
  serveCosts = IloArray<IloIntArray>(env, nbClients);
  env.out() << nbClients << " clients, " << nbWhouses << " warehouses" << endl;
  IloInt i;
  for (i = 0; i < nbWhouses; i++) {
    is >> capacities[i];
    is >> buildCosts[i];
  }
  env.out() << "Capacities: " << capacities << endl;
  env.out() << "Build costs: " << buildCosts << endl;
  for (i = 0; i < nbClients; i++) {
    serveCosts[i] = IloIntArray(env, nbWhouses);
    is >> demands[i];
    for (IloInt j = 0; j < nbWhouses; j++) is >> serveCosts[i][j];
  }
  env.out() << "Demands: " << demands << endl;
}
 
// Function to display the solution
 
void DisplaySolution(IloSolver solver,
                     const char *phrase,
                     IloIntVar cost,
                     IloIntVarArray offer) {
  solver.out() << endl << phrase << endl
               << "[" << solver.getValue(cost) << "]" << endl
               << solver.getIntVarArray(offer) << endl;
}
 
// Function to perform simple tabu search with a short term memory
 
void TabuSearch(IloSolver solver,
                IloIntVarArray open,
                IloSolution sol,
                IloSolution whole,
                IloGoal subGoal,
                IloInt iter = IloIntMax) {
  IloEnv env = solver.getEnv();
  IloRandom rand(env);
  IloNHood nh = IloRandomize(env, IloFlip(env, open), rand);
  IloMetaHeuristic mh = IloTabuSearch(env, 2);
  IloIntVar cost = sol.getObjectiveVar();
  IloSearchSelector selectMove = IloMinimizeVar(env, cost, 1.0);
 
  // Goal makes a move, and updates the (whole) best solution if better.
  IloGoal move = IloSingleMove(env, sol, nh, mh, selectMove, subGoal) &&
                 IloStoreBestSolution(env, whole);
  // Standard optimization loop.
  do {
    IloInt i = 0;
    while (--iter >= 0 && solver.solve(move)) {
      solver.out() << "Iter = " << ++i << ", "
                   << sol.getObjectiveValue() << " : ";
      for (IloInt j = 0; j < open.getSize(); j++)
        solver.out() << solver.getValue(open[j]);
      solver.out() << " (Best = " << whole.getObjectiveValue() << ")" << endl;
    }
  } while (iter > 0 && !mh.complete());
}
 
// Goal to assign customers to specific warehouses
 
ILCGOAL4(IlcSetOffer, IlcIntVarArray, offer, IlcIntVarArray, open,
                      IloArray<IloIntArray>, costs, IloIntArray, buildCosts) {
  IlcInt i = IlcChooseMinSizeInt(offer);
  if (i >= 0) {
    // Choose closest warehouse first.
    IlcInt best = -1;
    IlcInt lowest = IlcIntMax;
    for (IlcIntExpIterator it(offer[i]); it.ok(); ++it) {
      IloIntArray row = costs[i];
      IlcInt cost = row[*it] + buildCosts[*it] * (open[*it].getMin() == 0);
      if (cost <= lowest) { lowest = cost; best = *it; }
    }
    return IlcAnd(IlcOr(IlcSetValue(offer[i], best),
                        IlcRemoveValue(offer[i], best)),
                  this);
  }
  return 0;
}
 
ILOCPGOALWRAPPER4(IloSetOffer, solver, IloIntVarArray, offer, IloIntVarArray, open,
                  IloArray<IloIntArray>, costs, IloIntArray, buildCosts) {
  return IlcSetOffer(solver,
                     solver.getIntVarArray(offer),
                     solver.getIntVarArray(open),
                     costs,
                     buildCosts);
}
 
// Main program
 
int main(int argc, char *argv[]){
  IloEnv env;
  try {
    IloModel m(env);
    // Open input file.
    ifstream infile;
    const char *fname;
    if (argc > 1) fname = argv[1];
    else          fname = "../../../examples/data/cap71.txt";
    infile.open(fname);
    if (!infile.good()) {
      env.out() << "Could not open " << fname << endl;
      env.end();
      return 0;
    }
    // Decide on local search, proof, or local search, then proof.
    const char *lp = "lp";
    if (argc > 2) lp = argv[2];
    IloBool local = IloFalse;
    IloBool proof = IloFalse;
    if (strchr(lp, 'l')) local = IloTrue;
    if (strchr(lp, 'p')) proof = IloTrue;
  
    // Read in the problem
    IloInt nbWhouses, nbClients;
    IloIntArray capacities(env);
    IloIntArray demands(env);
    IloIntArray buildCosts(env);
    IloArray<IloIntArray> serveCosts;
    readProblem(env, infile, nbClients, nbWhouses,
                capacities, demands, buildCosts, serveCosts);
    infile.close();
    // Build all the constraints.
    IloIntVarArray offer(env, nbClients, 0, nbWhouses - 1);
    IloIntVarArray transCost(env, nbClients, 0, IloIntMax);
    IloIntVarArray open(env, nbWhouses, 0, 1);
    IloIntVarArray load(env, nbWhouses);
    IlcInt i;
    for (i = 0; i < nbWhouses; i++)
      load[i] = IloIntVar(env, 0, capacities[i]);
    m.add(IloPack(env, load, offer, demands));
  
    // Only open if customers are served.
    for (i = 0; i < nbWhouses; i++)
      m.add(open[i] == (load[i] != 0));
    m.add(IloScalProd(open, capacities) >= IloSum(demands));
 
    // Total cost is sum of shipment and build costs
    IloIntVar cost(env, 0, IloIntMax);
    cost.setName("Cost\t");
    m.add(cost == IloSum(transCost) + IloScalProd(open, buildCosts));
  
    // Element constraints.
    for (i = 0; i < nbClients; i++) {
      IloIntArray costs(env, nbWhouses);
      for (IlcInt j = 0; j < nbWhouses; j++)
        costs[j] = serveCosts[i][j];
      IloIntVar dRes(env, costs);
      m.add(IloTableConstraint(env, dRes, costs, offer[i]));
      m.add(transCost[i] == dRes);
    }
  
    // Set up two solutions.
    // sol: Holds only the 0-1 variables which defining the open warehouses
    // whole: Holds the variables which assign a warehouse to each client
    // NOTE: whole defines a solution, whereas sol only defines which
    //       warehouses will be used.  The clients must be then be assigned
    //       a specific warehouse each for a complete solution.
    //       We perform local search over the openness of warehouses,
    //       and at each move assign the customers to warehouses.
    IloSolution sol(env);
    IloObjective obj = IloMinimize(env, cost);
    sol.add(obj);
    for (i = 0; i < nbWhouses; i++) {
      char name[10];
      sprintf(name, "O-%ld", i);
      open[i].setName(name);
      sol.add(open[i]);
    }
    IloSolution whole(env);
    whole.add(obj);
    whole.add(offer);
    IloGoal g;
    IloInt upperBound = IloIntMax;
    IloSolver solver(env);
  
    // Inital solution
    // Complete search goal to assign clients to warehouses
    IloGoal generateOffer =
            IloSetOffer(env, offer, open, serveCosts, buildCosts);
    g = generateOffer &&
        IloStoreSolution(env, sol) &&
        IloStoreSolution(env, whole);
    solver.extract(m);
    if (solver.solve(g)) {
      DisplaySolution(solver, "Initial Solution", cost, offer);
    }
    else {
      solver.out() << "No initial solution" << endl;
      env.end();
      return 0;
    }
    if (local) {
      // Local Search
     
      // The sub-goal to assign clients to open warehouses, at minimum cost
      IloGoal subGoal = IloSelectSearch(env, generateOffer,
                                        IloMinimizeVar(env, cost, 1));
  
      // Run the tabu search
      TabuSearch(solver, open, sol, whole, subGoal, 30);
    }
    // Get the upper bound
    upperBound = (IloInt)whole.getObjectiveValue();
    if (proof) {
      cost.setUb(upperBound - 1);
      g = IloGenerate(env, open) &&
          generateOffer &&
          IloStoreSolution(env, whole);
      g = IloSelectSearch(env, g, IloMinimizeVar(env, cost, 1));
  
      // Optimization loop
      if (!local) solver.extract(m);
      if (solver.solve(g)) {
        solver.out() << "Complete search found solution of cost "
                     << solver.getValue(cost) << endl;
        solver.out() << solver.getIntVarArray(offer) << endl;
        if (local) {
          solver.out() << "Better solution found by complete search" << endl;
          solver.out() << "Local search was "
                       << 100.0 * (upperBound / whole.getObjectiveValue() - 1)
                       << "% above optimal" << endl;
        }
      }
      else {
        if (local) solver.out() << "No better solution found" << endl;
        else       solver.out() << "No solution" << endl;
      }
    }
    // Reporting final solution
    cost.setUb(whole.getObjectiveValue());
    g = IloRestoreSolution(env, whole);
    solver.solve(g);
    DisplaySolution(solver, "Final Solution", cost, offer);
  } catch(IloException& ex) {
    cout << "Error: " << ex << endl;
  }
  env.end();
  return 0;
}