Low-Rank Nonconvex Structures

A common approach to many structured problems is partitioning in which the set of variables is split into two groups in such a way that the problem becomes remarkably easier when the values of the variables in the first group (which are called complicating variables) are temporarily fixed. Fundamental partitioning methods for mixed integer linear programming problems were developed in the 60’s (Benders (1962), Rosen (1964), Ritter (1967)) and ever since extended to nonlinear programming with many applications (Balas (1970), Geoffrion (1970), (1972)), Fleischmann (1973), Tind and Wolsey (1981), Burkard et al. (1985), Tuy (1987).