Optimization Online


A branch and cut algorithm for solving the linear and quadratic integer programming problems

Yan Zizong (zzyan***at***jznu.net)
Fei Pusheng (pshfei***at***whu.edu.cn)
Wan Zhongping (zpwan-whu***at***126.com)

Abstract: This paper first presents an improve cutting plane method for solving the linear programming problems, based on the primal simplex method with the current equivalent facet technique, in which the increment of objection function is allowed as a pivot variable to decide the search step size. We obtain a strong valid inequality from the objective increment model so as to find a better integer feasible solution in the discrete integral equivalent face. Then we propose a branch and cut for the quadratic integer programs. A example shows that it is superior to other approaches to solving $IQP$ problems.

Keywords: Integer programming, Quadratic programs, Valid inequality, Cutting plane, Dual gap

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Integer Programming ((Mixed) Integer Linear Programming )

Citation: School of Mathematics and Statistics, Wuhan university,China. 12/2004

Download: [Postscript]

Entry Submitted: 01/24/2005
Entry Accepted: 01/25/2005
Entry Last Modified: 02/02/2005

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