linux_x86_64_cplex_12.6.0.1

/* -------------------------------------------------------------------------- * File: iloparbenders.java * Version 12.6 * -------------------------------------------------------------------------- * Licensed Materials - Property of IBM * 5725-A06 5725-A29 5724-Y48 5724-Y49 5724-Y54 5724-Y55 5655-Y21 * Copyright IBM Corporation, 2012, 2014. All Rights Reserved. * * US Government Users Restricted Rights - Use, duplication or * disclosure restricted by GSA ADP Schedule Contract with * IBM Corp. * -------------------------------------------------------------------------- */ /* ********************************************************************** * * * * Parallel distributed Benders decomposition * * * * This file illustrates how a distributed Benders' decomposition * * can be implemented by means of the CPLEX remote object. * * * * ********************************************************************** */ /* The example is focused on a MILP model for the facility location problem, * but can be easily extended to any MILP model. * * The MILP model used in this example is * minimize sum(f in F) sum(j in J) C[f,j]*x[f,j] + sum(f in F) F[f]*y[f] * such that * sum(f in F) x[f,j] >= 1 forall j in J * sum (f in F) y[f] <= 2 * y[f] >= x[f,j] forall f in F, j in J * x[f,j] >= 0 forall f in F, j in J * y[f] in { 0, 1 } forall f in F * where y[f] = 1 if factory f is opened and 0 otherwise and * x[f,j] is the fraction of demand serviced from factory f to customer j. * F[f] is the fixed charge cost for opening factory f and C[f,j] is the * cost for servicing customer j from f. * * The model is decomposed in a master block involving the y binary variables * only, and in |J| blocks B[j], one for each customer j in J, that are used * to separate Bender's cuts. * * The master block is solved on a local machine, by adding Benders' cuts * through a lazyconstraint callback, while the blocks B[j] (j in J) are * solved in parallel on different remote machines, and are used to separate * violated Benders' cuts to be added to the current master. * * The MILP master block is: * minimize sum(j in J) eta[j] + sum(f in F) F[f]*y[f] * such that * sum (f in F) y[f] <= 2 * y[f] in { 0, 1 } forall f in F * eta[j] >= 0 for all j in J * where, for each j in J, the variable eta[j] = sum(f in F) C[f,j]*x[f,j] * takes into account the objective function associated with variables * x[f,j] (f in F) * * The LP block B[j] associated with each fixed customer j in J is * minimize sum(f in F) C[f,j]*x[f,j] * such that * sum(f in F) x[f,j] >= 1 * x[f,j] <= y[f] forall f in F * x[f,j] >= 0 forall f in F * where the binary variables y are fixed and their value is provided * by the current solution of the master block. * * Given the current solution (y[F], eta[j]) of the master, for each customer * j in J a Bender's cut is separated by solving the dual of B[j], that is, * the following LP D[j]: * maximize beta - sum(f in F) y[f]*alpha[f] * such that * beta - alpha[f] <= C[f,j] forall f in F * alpha[f] >= 0 forall f in F * beta >= 0 * * An unbounded ray (beta, alpha[f]) of D[j] gives raise to the ray cut * (feasibility cut) * beta - sum(f in F) alpha[f]*y[f] <= 0 * in the master problem. * A vertex (beta, alpha[f]) of D[j] give raises to the point cut * (optimality cut) * eta[j] >= beta - sum(f in F) alpha[f]*y[f] * in the master problem. */ import ilog.cplex.*; import ilog.concert.*; import java.util.HashMap; import java.util.Vector; /* ********************************************************************** * * * * M a s t e r s i d e i m p l e m e n t a t i o n * * * * ********************************************************************** */ /** A class that solves problems by means of parallel distributed Benders * decomposition. The public API of this class consists of only two things: * - An interface Problem that describes problems that * can be solved by this class. * - A function solve() that solves instances of Problem. */ public final class RemoteParBenders { // ---------------------------------------------------------------------- private static final class RowSet extends java.util.HashSet<IloRange> {} /** Interface to problems that can be solved by the {@link RemoteParBenders} class. */ public interface Problem { /** Get the number of blocks in this problem. */ abstract int getNBlocks(); /** Get the model for this problem. */ abstract IloCplex getModel(); /** Get the variables in this problem. */ abstract IloNumVar[] getVariables(); /** Get the linear constraints in this problem. */ abstract IloRange[] getRows(); /** Get the block number for variable <code>x</code>. * @return The block number (in [0,getNBlocks()-1]) for <code>x</code> * or -1 if <code>x</code> is in the master. */ abstract int getBlock(IloNumVar x); /** Get the set of rows that intersect <code>x</code>. */ abstract RowSet getIntersectedRows(IloNumVar x); /** Get the objective function coefficient for <code>x</code>. */ abstract double getObjCoef(IloNumVar x); /** Get the objective function sense in this model. */ abstract IloObjectiveSense getObjSense(); } /** A block (either master or Benders) in a Benders decomposition. */ private static final class Block { final int number; /**< Serial number of this block. */ final IloNumVar[] vars; /**< Variables in this block's model. */ final IloRange[] rows; /**< Rows in this block's model. */ final IloCplex cplex; /**< The solver that (re)solves this block's model. */ /** Description of variables that are fixed by master solves. */ public static final class FixData { public int row; public int col; public double val; public FixData(int row, int col, double val) { this.row = row; this.col = col; this.val = val; } } final Vector<FixData> fixed; final IloObjective obj; /**< Objective function in this block. */ final HashMap<IloNumVar,Double> objMap; /**< Objective coefficient for each variable. */ final HashMap<IloNumVar,IloNumVar> varMap; /**< Map variables in this block to variables * in original model. */ /** Extract sub block number <code>n</code> from <code>problem</code>. * The constructor creates a representation of block number <code>n</code> * as described in <code>problem</code>. * The constructor will also connect the newly created block to a remote * object solver instance. * @param problem The problem from which the block is to be extracted. * @param n Index of the block to be extracted.