Back to search

McMaster University

Computational and Geometric Aspects of Linear Optimization

Abstract

dc:description.abstract

Linear optimization is concerned with maximizing, or minimizing, a linear objective function over a feasible region defined as the intersection of a finite number of hyperplanes. Pivot-based simplex methods and central-path following interior point methods are the computationally most efficient algorithms to solve linear optimization instances. Discrete optimization further assumes that some of the variables are integer-valued. This dissertation focuses on the geometric properties of the feasible region under some structural assumptions. In the first part, we consider lattice (d,k)-polytopes; that is, the convex hull of a set of points drawn from {0,1,...,k}^d, and study the largest possible diameter, delta(d,k), that a lattice (d,k)- polytope can achieve. We present novel properties and an enumeration algorithm to determine previously unknown values of delta(d,k). In particular, we determine the values for delta(3,6) and delta(5,3), and enumerate all the lattice (3,3)-polytopes achieving delta(3,3). In the second part, we consider the convex hull of all the 2^(2^d - 1) subsums of the 2^d - 1 nonzero {0,1}-valued vectors of length d, and denote by a(d) the number of its vertices. The value of a(d) has been determined until d =8 as well as asymptotically tight lower and upper bounds for loga(d). This convex hull forms a so-called primitive zonotope that is dual to the resonance hyperplane arrangement and belongs to a family that is conjectured to include lattice polytopes achieving the largest possible diameter over all lattice (d,k)-polytopes. We propose an algorithm exploiting the combinatorial and geometric properties of the input and present preliminary computational results.

Degree

thesis:*
Department dc:contributor.department
Computing and Software
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Guan, Zhongyan
Advisors dc:contributor.advisor
  • Deza, Antoine
  • Franek, Frantisek

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/11375/27062

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Guan, Zhongyan. Computational and Geometric Aspects of Linear Optimization. 2021. http://hdl.handle.net/11375/27062