Groupe d’études et de recherche en analyse des décisions

Branch-and-cut for combinatorial optimization problems without auxiliary binary variables

Ismael Regis De Farias Jr.

A large number of optimization applications consists in determining the values of continuous decision variables that are subject to combinatorial constraints. An example of a combinatorial constraint is that no more than a given number of variables is allowed to be nonzero. Typically, such models are formulated with auxiliary binary variables in order to enforce the combinatorial constraints. However, the addition of such variables can have severe consequences, including increasing the size of the model prohibitively and loosing structure. We investigate an alternative approach, branch-and-cut for combinatorial optimization problems without auxiliary binary variables, in which one dispenses with the introduction of the auxiliary binary variables and enforces the combinatorial constraints algorithmically, directly in the branch-and-cut scheme. We discuss the use of this approach in several general contexts and we demonstrate its effectiveness with an extensive set of computational results.