  


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 Lagrangeanlike 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  