Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Model of Residential Mail Delivery by Drones Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Exact Optimal Solution to Nonseparable Concave Quadratic Integer Programming Problems

Author : Fenlan Wang

Published in: Modeling and Optimization: Theory and Applications

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Nonseparable quadratic integer programming problems have extensive applications in real world and have received considerable attentions. In this paper, a new exact algorithm is presented for nonseparable concave quadratic integer programming problems. This algorithm is of a branch and bound frame, where the lower bound is obtained by solving a quadratic convex programming problem and the branches are partitioned via a special domain cut technique by which the optimality gap is reduced gradually. The optimal solution to the primal problem can be found in a finite number of iterations. Numerical results are also reported to illustrate the efficiency of our algorithm.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
previous chapter TopSpin: TOPic Discovery via Sparse Principal Component INterference
Literature
1.
Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonlinear Programming: Theory and Algorithms. Wiley, New York (1993)MATH
2.
Beck, A., Teboulle, M.: Global optimality conditions for quadratic optimization problems with binary constraints. SIAM J. Optimiz. 11, 179–188 (2000)MathSciNetCrossRef
3.
Benson, H.P., Erengue, S.S.: An algorithm for concave integer minimization over a polyhedron. Nav. Res. Log. 37, 515–525 (1990)MathSciNetCrossRef
4.
5.
Bretthauer, K.M., Shetty, B.: The nonlinear knapsack problem-algorithms and applications. Eur. J. Oper. Res. 138, 459–472 (2002a)MathSciNetCrossRef
6.
Bretthauer, K.M., Shetty, B.: A pegging algorithm for the nonlinear resource allocation problem. Comput. Oper. Res. 29, 505–527 (2002b)MathSciNetCrossRef
7.
Cabot, A.V., Erengue, S.S.: A branch and bound algorithm for solving a class of nonlinear integer programming problems. Nav. Res. Log. 33, 559–567 (1986)MathSciNetCrossRef
8.
Guignard, M., Kim, S.: Lagrangian decomposition: a model yielding stronger lagrangian relaxation bounds. Math. Program. 33, 262–273 (1987)
9.
10.
Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches. Springer, Heidelberg (1993)CrossRef
11.
Ibaraki, T., Katoh, N.: Resource Allocation Problems: Algorithmic Approaches. MIT Press, Cambridge, Mass (1988)
12.
Kodialam, M.S., Luss, H.: Algorithm for separable nonlinear resource allocation problems. Oper. Res. 46, 272–284 (1998)MathSciNetCrossRef
13.
Lasserre, J.B.: An explicit equivalent positive semidefinite program for nonlinear 0–1 programs. SIAM J. Optimiz. 12, 756–769 (2002)MathSciNetCrossRef
14.
Li, D., Sun, X.L., Wang, F.L.: Convergent Lagrangian and contour cut method for nonlinear integer programming with a quadratic objective function. SIAM J. Optimiz. 17, 372–400 (2006)MathSciNetCrossRef
15.
Li, D., Sun, X.L., Wang, J., McKinnon, K.: Convergent Lagrangian and domain cut method for nonlinear knapsack problems. Comput. Optim. Appl. 42, 67–104 (2009)MathSciNetCrossRef
16.
Marsten, R.E., Morin, T.L.: A hybrid approach to discrete mathematical programming. Math. Program. 14, 21–40 (1978)MathSciNetCrossRef
17.
Mathur, K., Salkin, H.M., Morito, S.: A branch and search algorithm for a class of nonlinear knapsack problems. Oper. Res. Lett. 2, 55–60 (1983)MathSciNetCrossRef
18.
Michelon, P., Maculan, N.: Lagrangian decomposition for integer nonlinear programming with linear constraints. Math. Program. 52, 303–313 (1991)CrossRef
19.
Michelon, P., Maculan, N.: Lagrangian methods for 0–1 quadratic programming. Discre. Appl. Math. 42, 257–269 (1993)CrossRef
20.
Pardalos, P.M., Rosen, J.B.: Reduction of nonlinear integer separable programming problems. Int. J. Comput. Math. 24, 55–64 (1988)CrossRef
21.
Sun, X.L., Li, D.: Optimality condition and branch and bound algorithm for constrained redundancy optimization in series systems. Optim. Eng. 3, 53–65 (2002)MathSciNetCrossRef
22.
Sun, X.L., Wang, F.L., Li, D.: Exact algorithm for concave knapsack problems: Linear underestination and partition method. J. Global Optim. 33, 15–30 (2005)MathSciNetCrossRef
23.
Wang, F.L., Sun, X.L.: A Lagrangian decomposition and domain cut algorithm for nonseparable convex knapsack problems. Oper. Res. Trans. 8, 45–53 (2004)
Metadata
Title
Exact Optimal Solution to Nonseparable Concave Quadratic Integer Programming Problems
Author
Fenlan Wang
Copyright Year
2019
Book
Modeling and Optimization: Theory and Applications

Print ISBN: 978-3-030-12118-1

Electronic ISBN: 978-3-030-12119-8

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-12119-8_9