This paper describes a new primal relaxation for nonlinear integer programming problems with linear constraints. This relaxation, contrary to the standard Lagrangean relaxation, can be solved efficiently. It requires the solution of a nonlinear penalized problem whose linear constraint set is known only implicitly, but whose solution is made possible by the use of a linearization method (see for instance Gunn and Rai [1987]). It can be solved iteratively by a sequence of linear integer programming problems and nonlinear problems over a simplex. The relaxation should be designed so that the linear integer programming problems are relatively easy to solve. These subproblems yield Lagrangean-like integer solutions that can be used as starting points for Lagrangean heuristics. We also describe a primal decomposition, similar in spirit to Lagrangean decomposition, for problems with several structured subsets of constraints. A small example is solved explicitly in each case by an extension of the linearization method of Frank and Wolfe [1956], similar in spirit to Simplicial Decomposition (von Hohenbalken, [1977]). The primal relaxation was introduced in Guignard [1994], and described briefly in Guignard [2003]. Improved solution methods are studied in Contesse and Guignard [1995] and [2007], and successful implementations are described in Ahn[1997], Ahn et al.[1996], Ahn et al.[2006] and Ahlatcioglu and Guignard [2007]. This paper by contrast concentrates on the concept of primal relaxation and its properties. In the linear case, the primal relaxation is equivalent to Lagrangean relaxation.
Citation
Research Report, OPIM Department, Wharton School, University of Pennsylvania, October 2007.