Exploiting network substructures and persistency in solving 0-1 and general nonconvex optimization problems

Although the optimization of a discrete mathematical program can be a formidable computational task, the exploitation of special structures often serves to significantly reduce the required effort. This research identifies two such structures that arise in various discrete programs; the first is a hidden network structure that is found in special 0-1 linear and quadratic programs within a transformed-variable space, and the second is a "persistency" structure that permits the certification of variables realizing predetermined values in the optimal solution to a linear programming relaxation to persist in retaining those same values in some optimal solution to the discrete problem.; The network structure arises in the relaxations of certain 0-1 linear packing and covering problems, as well as in linear reformulations of quadratic 0-1 programs. The procedure begins by removing certain constraints that can be deemed redundant at optimality. A transformation of variables is then performed, followed by a decomposition of constraints. The dual to the resulting transformed problem is a maximum cost network flow that is readily convertible to a maximum flow network.; To test the computational merits of the transformations, an exact solution strategy that uses the network formulations to compute bounds within an enumerative framework is devised for the quadratic 0-1 knapsack problem. It employs a known reformulation-linearization technique wherein the majority of constraints in this linear representation possess the desired dual-network structure. The computational results are encouraging.; The notion of persistency is defined in the literature relative to mixed 0-1 linear programs as follows. "An optimal solution to the continuous relaxation of a mixed 0-1 linear programming problem is defined to be persistent if all 0-1 variables realizing binary values retain those same binary values in some integer optimum." This effort presents a novel viewpoint that naturally extends the concept of persistency from the realm of mixed 0-1 linear programs to that of nonconvex problems whose variables have designated lower and upper bounds.