The paper describes a new primal relaxation (PR) for computing bounds on nonlinear integer programming (NLIP) problems. It is a natural extension to NLIP problems of the geometric interpretation of Lagrangean relaxation presented by Geoffrion (1974) for linear problems, and it is based on the same assumption that some constraints are complicating and are treated separately from the others. In the nonlinear case, however, this relaxation is not equivalent any more to Lagrangean relaxation, and it does not use Lagrangean multipliers. It consists in replacing the non-complicating constraint set by the convex hull of its integer points. It was introduced in Guignard [10], and described briefly in Guignard [11] for the case of linear constraints. Contrary to Outer Approximation ([18],[7]), it does not construct a superset of the continuous constraint set, but rather a subset of that set. After writing the complicating constraints as equality constraints, the relaxed problem can be shown to be asymptotically equivalent to a penalized nonlinear continuous problem as the penalty factor goes to infinity. Its constraint set is defined only implicitly, but is known to be a polytope. When the non-complicating constraints are linear, the penalized problem can be solved efficiently by using a linearization method. At each so-called major iteration until convergence has been achieved, the penalty coefficient is adjusted upward, and the corresponding penalized problem can be solved iteratively by simplicial decomposition, alternating between a priori much simpler linear integer programming problems and small continuous nonlinear problems over a simplex. Improved solution methods based on augmented Lagrangeans for the linear constraint case have been studied in [6], and successful implementations have been reported in [1], [2], [3] and [4] . The relaxation itself must be designed so as to yield linear integer programming problems that are relatively easy to solve. As in the linear MIP case, these subproblems yield Lagrangean-like integer solutions that are often only mildly infeasible in the complicating constraints, and can be used as starting points for Lagrangean heuristics. We also describe a primal decomposition (PD), similar in spirit to Lagrangean decomposition in the linear case [12], for problems with several structured subsets of constraints. To illustrate the concepts, and show that, like in Lagrangean relaxation for linear MIP problems, the PR bound can be anywhere between the continuous bound and the integer optimum, we solve several small examples explicitly, for both PR and PD, by a simplified version of Simplicial Decomposition. Maybe the most interesting aspect of this primal relaxation is the following very promising special case. When one keeps all constraints as non-complicating, and uses the entire convex hull of all integer feasible solutions of the problem, one obtains the convex hull relaxation, or CHR, (see Albornoz 1998, and Ahlatcioglu and Guignard 2007, 2010). In this case there is no need for a penalization, and the solution of the relaxed problem requires only one major iteration. This special relaxation shows great promise first as a tool for computing very efficiently strong bounds in the pseudoconvex case, and also as a powerful heuristic, even for nonconvex problems. Computational evidence is presented in (Ahlatcioglu and Guignard, 2010) for several variants of the very difficult QAP and GQAP problems.
Citation
Department of OPIM Research Report, Oct. 2010, the Wharton School, University of Pennsylvania
Article
View A new, solvable, primal relaxation for convex nonlinear integer programming problems