A new, solvable, primal relaxation for nonlinear integer programming problems with linear constraints

Monique Guignard (monique_guignardyahoo.com)

Abstract: 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.

Keywords: integer programming, relaxation, primal relaxation, simplicial decomposition, penalty function.

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Combinatorial Optimization (Other )

Citation: Research Report, OPIM Department, Wharton School, University of Pennsylvania, October 2007.

Download: [PDF]

Entry Submitted: 10/28/2007
Entry Accepted: 10/28/2007
Entry Last Modified: 10/28/2007

Modify/Update this entry