Optimization Online


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

Monique Guignard (monique_guignard***at***yahoo.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society