Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programs (IP) are used in companies and organizations across the world to
reach financial and time-related goals most often through optimal resource allocation and
scheduling. Unfortunately, integer programs are computationally difficult to solve and
in some cases the optimal solutions are unknown even with today’s advanced computing
machines.
Lifting is a technique that is often used to decrease the time required to solve an IP
to optimality. Lifting begins with a valid inequality and strengthens it by changing the
coefficients of variables in the inequality. Often times, this technique can result in facet
defining inequalities, which are the theoretically strongest inequalities.
This thesis introduces a new type of lifting called synchronized simultaneous lifting
(SSL). SSL allows for multiple sets of simultaneously lifted variables to be simultaneously
lifted which generates a new class of inequalities that previously would have required
an oracle to be found. Additionally, this thesis describes an algorithm to perform synchronized
simultaneous lifting for a binary knapsack inequality called the Synchronized
Simultaneous Lifting Algorithm (SSLA). SSLA is a quadratic time algorithm that will
exactly simultaneously lift two sets of simultaneously lifted variables.
Short computational studies show SSLA can sometimes solve IPs to optimality that
CPLEX, an advanced integer programming solver, alone cannot solve. Specifically, the
SSL cuts allowed a 76 percent improvement over CPLEX alone.
| Identifer | oai:union.ndltd.org:KSU/oai:krex.k-state.edu:2097/2304 |
| Date | January 1900 |
| Creators | Bolton, Jennifer Elaine |
| Publisher | Kansas State University |
| Source Sets | K-State Research Exchange |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0021 seconds