2961. Optimizing Integer Programming Problems using Branch-Line-and-Search Algorithm
Invited abstract in session MB-20: Integer Programming and Combinatorial Optimization: Complexity Questions and Algorithms, stream Combinatorial Optimization.
Monday, 10:30-12:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | MD SHAHRUKH ANJUM
|
| AMSOM, Ahmedabad University | |
| 2. | Jitamitra Desai
|
| Decision Sciences, Indian Institute of Management Bangalore |
Abstract
It is well recognized that finding a feasible solution to a mixed-integer program is a computationally difficult problem in practice. While there have been several attempts to improve the bound resulting from the relaxations at a given node within a branch-and-bound algorithm, there has been relatively scant attention paid to generating good quality feasible solutions relatively early in the branch-and-bound process. In this article, we develop a mechanism to quickly generate good quality feasible (incumbent) solutions by utilizing a line-search method to explore parts of the search space without relying on computationally intensive LP relaxations. The proposed algorithm, which we coin as the Branch-Line-and-Search (BLS) algorithm, is built on the principle of tracing collinear feasible integer points along the line segment formed by joining two (in)feasible integer solutions, possibly obtained at different nodes of the search tree. The BLS algorithm enhances the Branch and Bound method by integrating integer lattice properties to find improved integer feasible solutions. This novel approach reduces computational effort and leverages both feasible and infeasible points. In this work all the cases related to the position of the selected base integer points relative to the convex polytope and their impact on the solution complexity is studied.
Keywords
- Programming, Mixed-Integer
- Branch and Cut
- Polyhedral Combinatorics
Status: accepted
Back to the list of papers