Back to search

Georgia Institute of Technology

Integer Programming Approaches for Some Non-convex and Stochastic Optimization Problems

Abstract

dc:description.abstract

In this dissertation we study several non-convex and stochastic optimization problems. The common theme is the use of mixed-integer programming (MIP) techniques including valid inequalities and reformulation to solve these problems. We first study a strategic capacity planning model which captures the trade-off between the incentive to delay capacity installation to wait for improved technology and the need for some capacity to be installed to meet current demands. This problem is naturally formulated as a MIP with a bilinear objective. We develop several linear MIP formulations, along with classes of strong valid inequalities. We also present a specialized branch-and-cut algorithm to solve a compact concave formulation. Computational results indicate that these formulations can be used to solve large-scale instances. We next study methods for optimization with joint probabilistic constraints. These problems are challenging because evaluating solution feasibility requires multidimensional integration and the feasible region is not convex. We propose and analyze a Monte Carlo sampling scheme to simplify the probabilistic structure of such problems. Computational tests of the approach indicate that it can yield good feasible solutions and reasonable bounds on their quality. Next, we study a MIP formulation of the non-convex sample approximation problem. We obtain two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. Computational results indicate that large-scale instances can be solved using the strengthened formulations. Finally, we study optimization problems with stochastic dominance constraints. A stochastic dominance constraint states that a random outcome which depends on the decision variables should stochastically dominate a given random variable. We present new formulations for both first and second order stochastic dominance which are significantly more compact than existing formulations. Computational tests illustrate the benefits of the new formulations.

Degree

thesis:*
Department dc:contributor.department
Industrial and Systems Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2007

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Luedtke, James
Advisors dc:contributor.advisor
  • Ahmed, Shabbir
  • Nemhauser, George L.
Committee members dc:contributor.committeemember
  • Cook, William J.
  • Gu, Zonghao
  • Parker, R. Gary

Subjects

dc:subject × 9

Identifiers

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

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

Luedtke, James. Integer Programming Approaches for Some Non-convex and Stochastic Optimization Problems. Georgia Institute of Technology, 2007. http://hdl.handle.net/1853/19711