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 ). 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 , similar in spirit to Simplicial Decomposition (von Hohenbalken, ). The primal relaxation was introduced in Guignard , and described briefly in Guignard . Improved solution methods are studied in Contesse and Guignard  and , and successful implementations are described in Ahn, Ahn et al., Ahn et al. and Ahlatcioglu and Guignard . 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.
Entry Submitted: 10/28/2007
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|