Submodularity is a well-known concept in integer programming and combinatorial optimization. Submodular set functions capture the diminishing returns phenomenon, which has wide-ranging applications in various domains. Typically, a submodular set function models the utility of homogenous items selected from a single ground set. Selecting an item or not is naturally represented by one or zero. Therefore, optimizing submodular set functions is a class of interesting mixed-integer programming (MIP) problems with binary variables. In practice, many problem contexts call for extensions of submodularity--we may select multiple copies of homogenous items or choose heterogenous items from distinct ground sets. We refer to the optimization problems arising from such extensions of submodularity as Generalized Submodular Optimization (GSO). In GSO, the objective function is usually highly nonlinear, and the decision space is mixed-integer. These challenges make GSO a broad subclass of mixed-integer nonlinear programming (MINLP) problems. In this dissertation, we present theory, algorithms, and applications of GSO. Specifically, we explore the optimization problems with classical submodular set functions and two classes of generalized submodular functions, under constraints. We provide polyhedral theory for the underlying mixed-integer structures in these problems. Our theoretical results lead to efficient and versatile exact solution methods, which have demonstrated their effectiveness in practical problems using real-world datasets.

Creator

• Yu, Qimeng

DOI

• https://doi.org/10.21985/n2-4ksz-9d55

Subject

• Operations research

Language

• en

Alternate Identifier

• etdadmin_upload_1013578
• http://dissertations.umi.com/northwestern:16754

Keyword

• mixed-integer programming
• polyhedral
• convex hull
• nonlinear optimization

Date created

• 2023-01-01

Resource type

• Dissertation

Rights statement

• In Copyright