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.