An approximation algorithm for quadratic cost 0–1 mixed integer programming problems

✍ Scribed by Kumiko Mukai; Keiji Tatsumi; Masao Fukushima

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 586 KB
• Volume: 82
• Category: Article
• ISSN: 1042-0967
• DOI: 10.1002/(sici)1520-6440(199906)82:6<9::aid-ecjc2>3.0.co;2-7

✦ Synopsis

In this paper, we focus on the quadratic cost 01 mixed integer programming problem. First, we formulate the problem as a two-level programming problem that consists of a lower-level continuous quadratic programming problem with 01 variables fixed and an upper-level nonlinear 01 programming problem. We propose an approximation algorithm for solving the upper-level 01 programming problem. This algorithm approximately solves a subproblem obtained by linearizing the objective function at a current point. To guarantee the descent property of the generated sequence, we use a trust region technique that adaptively controls a penalty constant in the objective function of the subproblem. To solve subproblems, we apply a Hopfield network with a new transition rule that allows a temporary state transition based on the variable depth method. Some numerical experiments for a location-transportation problem with quadratic costs indicate that the proposed algorithm is practically effective.