New approaches to integer programming

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/44814

Title: New approaches to integer programming
Author: Chandrasekaran, Karthekeyan
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.
Type: Dissertation
URI: http://hdl.handle.net/1853/44814
Date: 2012-06-28
Publisher: Georgia Institute of Technology
Subject: Random graphs
Feedback vertex set
Cutting plane method
Integer program
Discrepancy
Random
Matching
Integer programming
Programming (Mathematics)
Algorithms
Department: Algorithms, Combinatorics, and Optimization
Advisor: Committee Chair: Vempala, Santosh; Committee Member: Ahmed, Shabbir; Committee Member: Cook, William; Committee Member: Dey, Santanu; Committee Member: Karp, Richard; Committee Member: Nemhauser, George
Degree: PhD

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
chandrasekaran_karthekeyan_201208_phd.pdf 963.6Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record