Back to search

Georgia Institute of Technology

New approaches to integer programming

Abstract

dc:description.abstract

Integer Programming (IP) is a powerful and widely-used formulation for combinatorial problems. The study of IP over the past several decades has led to fascinating theoretical developments, and has improved our ability to solve discrete optimization problems arising in practice. This thesis makes progress on algorithmic solutions for IP by building on combinatorial, geometric and Linear Programming (LP) approaches. We use a combinatorial approach to give an approximation algorithm for the feedback vertex set problem (FVS) in a recently developed Implicit Hitting Set framework. Our algorithm is a simple online algorithm which finds a nearly optimal FVS in random graphs. We also propose a planted model for FVS and show that an optimal hitting set for a polynomial number of subsets is sufficient to recover the planted subset. Next, we present an unexplored geometric connection between integer feasibility and the classical notion of discrepancy of matrices. We exploit this connection to show a phase transition from infeasibility to feasibility in random IP instances. A recent algorithm for small discrepancy solutions leads to an efficient algorithm to find an integer point for random IP instances that are feasible with high probability. Finally, we give a provably efficient implementation of a cutting-plane algorithm for perfect matchings. In our algorithm, cuts separating the current optimum are easy to derive while a small LP is solved to identify the cuts that are to be retained for later iterations. Our result gives a rigorous theoretical explanation for the practical efficiency of the cutting plane approach for perfect matching evident from implementations. In summary, this thesis contributes to new models and connections, new algorithms and rigorous analysis of well-known approaches for IP.

Degree

thesis:*
Department dc:contributor.department
Algorithms, Combinatorics, and Optimization
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Chandrasekaran, Karthekeyan
Advisor dc:contributor.advisor
  • Vempala, Santosh S.
Committee members dc:contributor.committeemember
  • Bruckman, Amy
  • Czerwinski, Mary
  • Foley, James
  • Mynatt, Elizabeth D.
  • Sengers, Phoebe

Subjects

dc:subject × 10

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/44814

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Chandrasekaran, Karthekeyan. New approaches to integer programming. Georgia Institute of Technology, 2012. http://hdl.handle.net/1853/44814