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;
}