Hi,

I am new to using advanced Operations Research techniques. I was learning Benders Decomposition and trying to understand the BendersATSP example. 

Most of the resources available on the web describe benders decomposition with a master problem and a sub-problem. The sub-problem is the dual form of the variables not considered in the master problem. Solving the sub - problem helps in generating cuts which are added to the master problem iteratively. 

However, when I look into the example problem, the model included in the Worker LP class is not dual. 

Can anyone please explain the intuition based on which the Worker LP class is built?

Thank you.
#DecisionOptimization

I am not clear what makes you think the worker problem is not a dual. In the code for BendersATSP.java (I assume that is what you are referring to, the code for the other programming languages is similar) you have this:

      // The constructor sets up the IloCplex instance to solve the worker LP, 
      // and creates the worker LP (i.e., the dual of flow constraints and
      // capacity constraints of the flow MILP)
      //
      // Modeling variables:
      // forall k in V0, i in V:
      //    u(k,i) = dual variable associated with flow constraint (k,i)
      //
      // forall k in V0, forall (i,j) in A:
      //    v(k,i,j) = dual variable associated with capacity constraint (k,i,j)
      //
      // Objective:
      // minimize sum(k in V0) sum((i,j) in A) x(i,j) * v(k,i,j)
      //          - sum(k in V0) u(k,0) + sum(k in V0) u(k,k)
      //
      // Constraints:
      // forall k in V0, forall (i,j) in A: u(k,i) - u(k,j) <= v(k,i,j)
      //
      // Nonnegativity on variables v(k,i,j)
      // forall k in V0, forall (i,j) in A: v(k,i,j) >= 0
      //
      WorkerLP(int numNodes) throws IloException {​

The comments clearly state that what is constructed is the dual of the flow and capacity constraints.

------------------------------
Daniel Junglas
------------------------------