Topic
• 3 replies
• Latest Post - ‏2013-04-06T00:28:26Z by SystemAdmin
7929 Posts

# Pinned topic auxiliary continuous variable in Master Problem in example ilobendersatsp

‏2013-04-04T02:14:47Z |
Dear Cplex folks
I was going through example ilobendersatsp.cpp. I know that traditional Benders decomposition splits the main problem into a master problem and a subproblem. The subproblem must be a linear program (LP), where master problem contains integer variable and an auxiliary continuous variable. While I was going through the example ilobendersatsp.cpp I can't see any auxiliary continuous variable in the master problem. Shouldn't be there an auxiliary continuous variable in the master problem? Can anyone please explain me the decomposition algorithm for this example?.I would appreciate if you could lead me some article for this problem.
I am also confused to see that dual subproblem in ilobendersatsp.cpp is a minimization problem where in traditional bender decomposition problem dual sub problem is a maximization problem.
Roni
Updated on 2013-04-06T00:28:26Z at 2013-04-06T00:28:26Z by SystemAdmin
7929 Posts

#### Re: auxiliary continuous variable in Master Problem in example ilobendersatsp

‏2013-04-04T12:13:35Z
Hi!

Hope this will help.

> Can anyone please explain me the decomposition algorithm for this example?

I will use the comments that are posted in the file ilobendersatsp.cpp and add some more details.

The model we want to solve is a flow MILP model for the Asymmetric Traveling Salesman Problem (ATSP), that is:

// ATSP instance defined on a directed graph G = (V, A)
// - V = {0, ..., n-1}, V0 = V \ {0}
// - A = {(i,j) : i in V, j in V, i != j }
// - forall i in V: delta+(i) = {(i,j) in A : j in V}
// - forall i in V: delta-(i) = {(j,i) in A : j in V}
// - c(i,j) = traveling cost associated with (i,j) in A

The MILP model is:

// Flow MILP model
//
// Modeling variables:
// forall (i,j) in A:
// x(i,j) = 1, if arc (i,j) is selected
// = 0, otherwise
// forall k in V0, forall (i,j) in A:
// y(k,i,j) = flow of the commodity k through arc (i,j)
//
// Objective:
// minimize sum((i,j) in A) c(i,j) * x(i,j)
//
// Degree constraints:
// forall i in V: sum((i,j) in delta+(i)) x(i,j) = 1
// forall i in V: sum((j,i) in delta-(i)) x(j,i) = 1
//
// Binary constraints on arc variables:
// forall (i,j) in A: x(i,j) in {0, 1}
//
// Flow constraints:
// forall k in V0, forall i in V:
// sum((i,j) in delta+(i)) y(k,i,j) - sum((j,i) in delta-(i)) y(k,j,i) = q(k,i)
// where q(k,i) = 1, if i = 0
// = -1, if k == i
// = 0, otherwise
//
// Capacity constraints:
// forall k in V0, for all (i,j) in A: y(k,i,j) <= x(i,j)
//
// Nonnegativity of flow variables:
// forall k in V0, for all (i,j) in A: y(k,i,j) >= 0

Then you decompose the model into the master problem and the Benders' subproblem.

The master problem is obtained by just "removing" all the flow and capacity constraints:

// Master ILP
//
// Modeling variables:
// forall (i,j) in A:
// x(i,j) = 1, if arc (i,j) is selected
// = 0, otherwise
//
// Objective:
// minimize sum((i,j) in A) c(i,j) * x(i,j)
//
// Degree constraints:
// forall i in V: sum((i,j) in delta+(i)) x(i,j) = 1
// forall i in V: sum((j,i) in delta-(i)) x(j,i) = 1
//
// Binary constraints on arc variables:
// forall (i,j) in A: x(i,j) in {0, 1}

Of course, you will have to add to the master the Bender's cuts that will be separated on the fly through callbacks.
The subproblem is the remaining part of the model (i.e., flow and capacity constraints):

// Subproblem:
//
// minimize 0
//
// Flow constraints:
// forall k in V0, forall i in V:
// sum((i,j) in delta+(i)) y(k,i,j) - sum((j,i) in delta-(i)) y(k,j,i) = q(k,i)
// where q(k,i) = 1, if i = 0
// = -1, if k == i
// = 0, otherwise
//
// Capacity constraints:
// forall k in V0, for all (i,j) in A: y(k,i,j) <= x(i,j)
//
// Nonnegativity of flow variables:
// forall k in V0, for all (i,j) in A: y(k,i,j) >= 0

This is a Linear Program, where y are the variables but x is fixed (at each separation step, x is the current solution provided by the master ILP). To separate cuts, you solve the dual model of the LP above (denoted as worker LP in the example):

// Worker LP
//
// 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

Note that, if you take the "row" dual, then you will have a maximization problem and non-positive variables v <= 0.
But you can adjust the sense of constraints and variables, in order to get a "more standard" form for the dual, like the workerLP above, where the objective function is in minimization form and variables v are non-negative. This is just for convenience.

Note that the workerLP is defined on a polyhedral cone: no vertices, only the apex (0, 0, ..., 0), and rays.
Thus, when you solve the workerLP, you have only two possibilities:
1) Optimal solution has value 0 --> no violated cut exists
2) Optimal solutio is unbounded --> you can get a so called "feasibility" Benders' cut from one of the unbounded rays:
// Compute the cut from the unbounded ray. The cut is:
// sum((i,j) in A) (sum(k in V0) v(k,i,j)) * x(i,j) >=
// sum(k in V0) u(k,0) - u(k,k)

In the general case, the workerLP may be a polyhedron (with both rays and vertices).
A violated Benders'cut associated with a vertex of the workerLP is a so called "optimality" Benders' cut.

> While I was going through the example ilobendersatsp.cpp
> I can't see any auxiliary continuous variable in the master problem.
> Shouldn't be there an auxiliary continuous variable in the master problem?

Not necessarily. You can have two situations in the original model that you want to decompose:

1) The variables that you decompose appear in the objective function.
Then you will end up with a master problem that contains an auxiliary continuous variable. This variable is precisely introduced to take into account the contribution to the objective function given by the variables you are decomposing.

2) The variables that you decompose do not appear in the objective function (like in this example).
Then you do not have any auxiliary variable in the master.

Note also that, in case 1) above, the subproblem you decompose will have a non-empty objective function.
This means that the workerLP will be defined on a polyhedron with both vertices and rays.
In the case 2), instead (again, the one of this example), the subproblem has an empty objective function, and thus the workerLP is defined by construction on a cone with rays only.

> I would appreciate if you could lead me some article for this problem.

On my opinion, the basics of Benders' decomposition (and something more) are well explained in the paper
"Minimal Infeasible Subsystems and Benders' cuts", by Fischetti, Salvagning and Zanette (see http://www.dei.unipd.it/~fisch/papers/Benders_mis_extended_draft.pdf).
So I suggest you to have a look at this paper.
In particular, the basics are illustrated in Section 2, where you will find also an example that is precisely the ATSP, that is, the one used in in ilobendersatsp.cpp.

> I am also confused to see that dual subproblem in ilobendersatsp.cpp
> is a minimization problem where in traditional bender decomposition problem
> dual sub problem is a maximization problem.

As I said before, the workerLP is translated to a minimization problem just for convenience.
7929 Posts

#### Re: auxiliary continuous variable in Master Problem in example ilobendersatsp

‏2013-04-04T17:00:37Z
Hi!

Hope this will help.

> Can anyone please explain me the decomposition algorithm for this example?

I will use the comments that are posted in the file ilobendersatsp.cpp and add some more details.

The model we want to solve is a flow MILP model for the Asymmetric Traveling Salesman Problem (ATSP), that is:

// ATSP instance defined on a directed graph G = (V, A)
// - V = {0, ..., n-1}, V0 = V \ {0}
// - A = {(i,j) : i in V, j in V, i != j }
// - forall i in V: delta+(i) = {(i,j) in A : j in V}
// - forall i in V: delta-(i) = {(j,i) in A : j in V}
// - c(i,j) = traveling cost associated with (i,j) in A

The MILP model is:

// Flow MILP model
//
// Modeling variables:
// forall (i,j) in A:
// x(i,j) = 1, if arc (i,j) is selected
// = 0, otherwise
// forall k in V0, forall (i,j) in A:
// y(k,i,j) = flow of the commodity k through arc (i,j)
//
// Objective:
// minimize sum((i,j) in A) c(i,j) * x(i,j)
//
// Degree constraints:
// forall i in V: sum((i,j) in delta+(i)) x(i,j) = 1
// forall i in V: sum((j,i) in delta-(i)) x(j,i) = 1
//
// Binary constraints on arc variables:
// forall (i,j) in A: x(i,j) in {0, 1}
//
// Flow constraints:
// forall k in V0, forall i in V:
// sum((i,j) in delta+(i)) y(k,i,j) - sum((j,i) in delta-(i)) y(k,j,i) = q(k,i)
// where q(k,i) = 1, if i = 0
// = -1, if k == i
// = 0, otherwise
//
// Capacity constraints:
// forall k in V0, for all (i,j) in A: y(k,i,j) <= x(i,j)
//
// Nonnegativity of flow variables:
// forall k in V0, for all (i,j) in A: y(k,i,j) >= 0

Then you decompose the model into the master problem and the Benders' subproblem.

The master problem is obtained by just "removing" all the flow and capacity constraints:

// Master ILP
//
// Modeling variables:
// forall (i,j) in A:
// x(i,j) = 1, if arc (i,j) is selected
// = 0, otherwise
//
// Objective:
// minimize sum((i,j) in A) c(i,j) * x(i,j)
//
// Degree constraints:
// forall i in V: sum((i,j) in delta+(i)) x(i,j) = 1
// forall i in V: sum((j,i) in delta-(i)) x(j,i) = 1
//
// Binary constraints on arc variables:
// forall (i,j) in A: x(i,j) in {0, 1}

Of course, you will have to add to the master the Bender's cuts that will be separated on the fly through callbacks.
The subproblem is the remaining part of the model (i.e., flow and capacity constraints):

// Subproblem:
//
// minimize 0
//
// Flow constraints:
// forall k in V0, forall i in V:
// sum((i,j) in delta+(i)) y(k,i,j) - sum((j,i) in delta-(i)) y(k,j,i) = q(k,i)
// where q(k,i) = 1, if i = 0
// = -1, if k == i
// = 0, otherwise
//
// Capacity constraints:
// forall k in V0, for all (i,j) in A: y(k,i,j) <= x(i,j)
//
// Nonnegativity of flow variables:
// forall k in V0, for all (i,j) in A: y(k,i,j) >= 0

This is a Linear Program, where y are the variables but x is fixed (at each separation step, x is the current solution provided by the master ILP). To separate cuts, you solve the dual model of the LP above (denoted as worker LP in the example):

// Worker LP
//
// 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

Note that, if you take the "row" dual, then you will have a maximization problem and non-positive variables v <= 0.
But you can adjust the sense of constraints and variables, in order to get a "more standard" form for the dual, like the workerLP above, where the objective function is in minimization form and variables v are non-negative. This is just for convenience.

Note that the workerLP is defined on a polyhedral cone: no vertices, only the apex (0, 0, ..., 0), and rays.
Thus, when you solve the workerLP, you have only two possibilities:
1) Optimal solution has value 0 --> no violated cut exists
2) Optimal solutio is unbounded --> you can get a so called "feasibility" Benders' cut from one of the unbounded rays:
// Compute the cut from the unbounded ray. The cut is:
// sum((i,j) in A) (sum(k in V0) v(k,i,j)) * x(i,j) >=
// sum(k in V0) u(k,0) - u(k,k)

In the general case, the workerLP may be a polyhedron (with both rays and vertices).
A violated Benders'cut associated with a vertex of the workerLP is a so called "optimality" Benders' cut.

> While I was going through the example ilobendersatsp.cpp
> I can't see any auxiliary continuous variable in the master problem.
> Shouldn't be there an auxiliary continuous variable in the master problem?

Not necessarily. You can have two situations in the original model that you want to decompose:

1) The variables that you decompose appear in the objective function.
Then you will end up with a master problem that contains an auxiliary continuous variable. This variable is precisely introduced to take into account the contribution to the objective function given by the variables you are decomposing.

2) The variables that you decompose do not appear in the objective function (like in this example).
Then you do not have any auxiliary variable in the master.

Note also that, in case 1) above, the subproblem you decompose will have a non-empty objective function.
This means that the workerLP will be defined on a polyhedron with both vertices and rays.
In the case 2), instead (again, the one of this example), the subproblem has an empty objective function, and thus the workerLP is defined by construction on a cone with rays only.

> I would appreciate if you could lead me some article for this problem.

On my opinion, the basics of Benders' decomposition (and something more) are well explained in the paper
"Minimal Infeasible Subsystems and Benders' cuts", by Fischetti, Salvagning and Zanette (see http://www.dei.unipd.it/~fisch/papers/Benders_mis_extended_draft.pdf).
So I suggest you to have a look at this paper.
In particular, the basics are illustrated in Section 2, where you will find also an example that is precisely the ATSP, that is, the one used in in ilobendersatsp.cpp.

> I am also confused to see that dual subproblem in ilobendersatsp.cpp
> is a minimization problem where in traditional bender decomposition problem
> dual sub problem is a maximization problem.

As I said before, the workerLP is translated to a minimization problem just for convenience.
Hi Andrea
Thank you very much. Your explanation was very helpful. One more question.
If I take the "row" dual, then construct a maximization problem for non-positive variables v <= 0. Is it supposed to produce the same result where the objective function is in minimization form and variables v are non-negative?
Thanks again
Roni
7929 Posts

#### Re: auxiliary continuous variable in Master Problem in example ilobendersatsp

‏2013-04-06T00:28:26Z
Hi Andrea
Thank you very much. Your explanation was very helpful. One more question.
If I take the "row" dual, then construct a maximization problem for non-positive variables v <= 0. Is it supposed to produce the same result where the objective function is in minimization form and variables v are non-negative?
Thanks again
Roni
Yes, it will produce the same result.
Namely, optimal solution value equal to 0, if no violated cut exists, optimal solution value unbounded, if you have a violated cut. In this case, you can get an unbounded extreme ray as it is done in the example and construct the cut.
Of course, you have to apply a bit of algebra to understand which is exactly the form of the cut (for this, I suggest you again to look at the paper that I mentioned in my previous comment), but the result is the same.

Andrea