Generation and strengthening methods of Chvatal-Gomory cuts for the knapsack problem with generalized upper bounds

Abstract

This research aims to develop efficient methods for generating and strengthening rank-1 Chva tal-Gomory (CG) cuts for the knapsack set with generalized upper bounds, applicable to solving general integer programs. The study hypothesizes that these cuts, combined with efficient generation and strengthening methods, will tighten the linear relaxations and improve overall computational performance of the branch-and-cut method for general integer programs. The research objectives are to- (1) develop efficient solution methods for the separation problem to generate effective rank-1 CG cuts, and (2) develop efficient methods to further strengthen these cuts. The approach involves theoretical analysis of effective rank-1 CG cuts and the computational complexity of the separation problem, development of exact and heuristic separation algorithms, strengthening methods by adjusting the variable coefficients, computational evaluation of the proposed methods, and comparative analysis with existing cuts. This two-year project will focus on cut generation methods in the �rst year and strengthening methods in the second. The study will contribute to the advancement of integer optimization theory, deepening our understanding of rank-1 CG cuts and their applications. The results may extend to more general knapsack sets, including those with individual variable upper bounds or mixed-integer sets. Preliminary tests indicate the potential for these cuts to outperform existing ones, suggesting the developed methods could enhance the computational performance of current state-of-the-art branch-and-cut methods, thereby improving the solvability of general integer programs.

Document Details

Document Type
DoD Grant Award
Publication Date
Feb 06, 2025
Source ID
FA23862514009

Entities

People

  • Kyungsik Lee

Organizations

  • Air Force Office of Scientific Research
  • Seoul National University
  • United States Air Force

Tags

Readers

  • Operations Research