Two Combinatorial Optimization Problems at the Interface of Computer Science and Operations Research

Kao, Gio K.

Permalink

https://hdl.handle.net/2142/11480 Copy

Description

Title

Two Combinatorial Optimization Problems at the Interface of Computer Science and Operations Research

Author(s)

Kao, Gio K.

Issue Date

2008-08

Keyword(s)

computer science

Abstract

Solving large combinatorial optimization problems is a ubiquitous task across multiple disciplines. Developing efficient procedures for solving these problems has been of great interest to both researchers and practitioners. Over the last half century, vast amounts of research have been devoted to studying various methods in tackling these problems. These methods can be divided into two categories, heuristic methods and exact algorithms. Heuristic methods can often lead to near optimal solutions in a relatively time efficient manner, but provide no guarantees on optimality. Exact algorithms guarantee optimality, but are often very time consuming. This dissertation focuses on designing efficient exact algorithms that can solve larger problem instances with faster computational time. A general framework for an exact algorithm, called the Branch, Bound, and Remember algorithm, is proposed in this dissertation. Three variations of single machine scheduling problems are presented and used to evaluate the efficiency of the Branch, Bound, and Remember algorithm. The computational results show that the Branch, Bound, and Remember algorithms outperforms the best known algorithms in the literature. While the Branch, Bound, and Remember algorithm can be used for solving combinatorial optimization problems, it does not address the subject of post-optimality selection after the combinatorial optimization problem is solved. Post-optimality selection is a common problem in multi-objective combinatorial optimization problems where there exists a set of optimal solutions called Pareto optimal (non-dominated) solutions. Post-optimality selection is the process of selecting the best solutions within the Pareto optimal solution set. In many real-world applications, a Pareto solution set (either optimal or near-optimal) can be extremely large, and can be very challenging for a decision maker to evaluate and select the best solution. To address the post-optimality selection problem, this dissertation also proposes a new discrete optimization problem to help the decision-maker to obtain an optimal preferred subset of Pareto optimal solutions. This discrete optimization problem is proven to be NP-hard. To solve this problem, exact algorithms and heuristic methods are presented. Different multi-objective problems with various numbers of objectives and constraints are used to compare the performances of the proposed algorithms and heuristics.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11480

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections