Originally posted by: SystemAdmin

[cplex_ma said:]

Hi,

I was reading about the "branch and cut" algorithm which is also used in CPLEX to solve Binary Linear and Integer Linear programs.

This is what I was reading about "branxh and cut algorithm":

"The method solves the linear program without the integer constraint using the regular simplex algorithm. When an optimal solution is obtained, and this solution has a non-integer value for a variable that is supposed to be integer, a cutting plane algorithm is used to find further linear constraints which are satisfied by all feasible integer points but violated by the current fractional solution. If such an inequality is found, it is added to the linear program, such that resolving it will yield a different solution which is hopefully "less fractional". This process is repeated until either an integer solution is found (which is then known to be optimal) or until no more cutting planes are found.

At this point, the branch and bound part of the algorithm is started. The problem is split into two versions, one with the additional constraint that the variable is greater than or equal to the next integer greater than the intermediate result, and one where this variable is less than or equal to the next lesser integer. In this way new variables are introduced in the basis according to the number of basic variables that are non-integers in the intermediate solution but which are integers according to the original constraints. The new linear programs are then solved using the simplex method and the process repeats until a solution satisfying all the integer constraints is found. "

It describes the algorithm for Integer Programming but I wonder if it the same algorithm can be used for Binary Programs too. Because this part "The problem is split into two versions, one with the additional constraint that the variable is greater than or equal to the next integer greater than the intermediate result, and one where this variable is less than or equal to the next lesser integer." does make sense for Integer programs but for Binary programs, are the nodes splitted based on 1 and zero value?

Also, One more question: when it says that " When an optimal solution is obtained, and this solution has a non-integer value for a variable that is supposed to be integer, a cutting plane algorithm is used to find further linear constraints which are satisfied by all feasible integer points but violated by the current fractional solution. If such an inequality is found, it is added to the linear program, such that resolving it will yield a different solution which is hopefully "less fractional". " waht inequlaity constraints are added for Binary Programs?

Thanks

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

[quote author=cplex_ma link=topic=783.msg2377#msg2377 date=1230068125]
It describes the algorithm for Integer Programming but I wonder if it the same algorithm can be used for Binary Programs too. Because this part "The problem is split into two versions, one with the additional constraint that the variable is greater than or equal to the next integer greater than the intermediate result, and one where this variable is less than or equal to the next lesser integer." does make sense for Integer programs but for Binary programs, are the nodes splitted based on 1 and zero value?

Yes.  A binary variable is just a special case of an integer variable.  Where a general integer variable x would be separated into x <= a or x >= a+1 for some integer a, a binary variable y will always be separated into y = 0 or y = 1.

[quote author=cplex_ma link=topic=783.msg2377#msg2377 date=1230068125]
Also, One more question: when it says that " When an optimal solution is obtained, and this solution has a non-integer value for a variable that is supposed to be integer, a cutting plane algorithm is used to find further linear constraints which are satisfied by all feasible integer points but violated by the current fractional solution. If such an inequality is found, it is added to the linear program, such that resolving it will yield a different solution which is hopefully "less fractional". " waht inequlaity constraints are added for Binary Programs?


There are a variety of possible cuts, and which ones will be added depends on the individual problem, what CPLEX finds at a specific node of the problem (i.e., you likely will get different cuts at different nodes), what your CPLEX parameter settings are and quite possibly how the planets are aligning.  AFAIK, the various classes of cuts built into CPLEX are all applicable for binary problems, but I'm by no means an expert on cuts, so I can't be sure.

/Paul
#CPLEXOptimizers
#DecisionOptimization