Structural and algorithmic aspects of linear inequality systems

Linear inequality systems play a foundational role in Operations Research, but many fundamental structural and algorithmic questions about linear inequality systems remain unanswered. This thesis considers and addresses some of these questions. In the first chapter, we reconsider the ellipsoid algorithm applied to solving a system of linear inequalities. Unlike the simplex method and interior point methods, the ellipsoid algorithm has no mechanism for proving that a system is infeasible (in the real model of computation). Motivated by this, we develop an ellipsoid algorithm that produces a solution to a system or provides a simple proof that no solution exists. Depending on the dimensions and on other natural condition measures, the computational complexity of our algorithm may be worse than, the same as, or better than that of the standard ellipsoid algorithm.. In the second chapter, we reduce the problem of solving a homogeneous linear inequality system to the problem of finding the unique sink of a unique sink orientation (USO) in the vertex evaluation model of computation. We show the USOs of interest satisfy a local property that is not satisfied by all USOs that satisfy the Holt-Klee property. This addresses an open question that is motivated by the idea that such local structure could be leveraged algorithmically to develop faster algorithms or a strongly polynomial algorithm. In the third chapter, we make progress on a conjecture about a particular class of linear inequality systems that have balanced constraint matrices. A balanced matrix is a 0-1 matrix that does not contain a square submatrix of odd order with two ones per row and column. The conjecture asserts that every nonzero balanced matrix contains an entry equal to 1, which upon setting to 0, leaves the matrix balanced.

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Operations Research Center

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2020

Author dc:creator

• Lamperski, Jourdain Bernard.

Advisor dc:contributor.advisor

• Robert M. Freund.

• Operations Research Center.

Statement dc:rights

• MIT theses may be protected by copyright. Please reuse MIT thesis content according to the MIT Libraries Permissions Policy, which is available through the URL provided.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/128971

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/128971