In the examples of method de decomposition of benders, the problem have two groups of variables, a group of binary variables and other of continuous variables, the problem is converted in two subproblems with the method of benders
But if the problem have only binary variables ¿is possible the utilization of the method of benders?
of course!! see the excellent discussion for example of the uncapicitated simple plant location problem in Prof KIPP-MARTIN's book
okey , thanks
but the example of Richard Kipp, in the chapter 10, the problem has two types of variables, a array of binary variables "y" and other array of continuos variables "x"
if I have for example , only a 2-dimensional array binary variables "x", in a packing problem of objects in a container , x represent if a object is localized (or not) in the node i of the container (the container is defined with a grid of points)
The tricky part is how to generate feasibility and optimality cuts when the "subproblem" has binary variables. But it can be done. See the paper "Combinatorial Benders' cuts for mixed-integer linear programming" by Codato and Fischetti.
perhaps the facility location example is a special case that is not a good match for your case, but .... what do you notice about the solutions? The y variables are integer (binary) even though we did not require this (y >=0)..
See also this discussion:
http://orinanobworld.blogspot.co.uk/2013/07/benders-decomposition-with-integer.html
- Badges
- Science topic
- Similar topics
- Filing