Spelling suggestions: "subject:"simultaneous gifting"" "subject:"simultaneous ifting""
1 |
Simultaneously lifting multiple sets in binary knapsack integer programsKubik, Lauren Ashley January 1900 (has links)
Master of Science / Department of Industrial & Manufacturing Systems
Engineering / Todd W. Easton / Integer programs (IPs) are mathematical models that can provide organizations with
the ability to optimally obtain their goals through appropriate utilization and allocation
of available resources. Unfortunately, IPs are NP-complete in the strong sense, and
many integer programs cannot be solved.
Introduced by Gomory, lifting is a technique that takes a valid inequality and strengthens
it. Lifting can result in facet defining inequalities, which are the theoretically
strongest inequalities; because of this, lifting techniques are commonly used in commercial
IP software to reduce the time required to solve an IP.
This thesis introduces two new algorithms for exact simultaneous up lifting multiple
sets into binary knapsack problems and introduces sequential simultaneous lifting.
The Dynamic Programming Multiple Lifting Set Algorithm (DPMLSA) is a pseudopolynomial
time algorithm bounded by O(nb) effort that can exactly uplift an arbitrary
number of sets. The Three Set Simultaneous Lifting Algorithm (TSSLA) is a polynomial
time algorithm bounded by O(n2) and can exact simultaneously up lift three sets.
The simultaneously lifted inequalities generated by the DPMLSA and the TSSLA can
be facet defining, and neither algorithm requires starting with a minimal cover.
A brief computational study shows that the DPMLSA is fast and required an average
of only 0.070 seconds. The computational study also shows these sequential simultaneously
lifted inequalities are useful, as the solution time decreased by an overall average
of 18.4%. Therefore, implementing the DPMLSA should be beneficial for large IPs.
|
2 |
The theory of simultaneous lifting: constellations in conflict hypergraphsPahwa, Samir January 1900 (has links)
Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programming (IP) is a powerful technique used by many companies and organizations to determine optimal strategies for making decisions and managing resources to achieve their goals. One class of IP problems is the multiple knapsack (MK) problem. However, MK and other IP problems, are extremely complicated since they are ${\cal NP}$-hard problems. Furthermore, there exist numerous instances that can not be solved.
One technique commonly used to reduce the solution time for IP problems is lifting. This method, introduced by Gomory, takes an existing valid inequality and strengthens it. Lifting has the potential to form facet defining inequalities, which are the strongest inequalities to solve an IP problem. As a result, lifting is frequently used in integer programming applications.
This research takes a broad approach to simultaneous lifting and provides its theoretical background for. The underlying hypergraphic structure for simultaneous lifting in an MK problem is identified and called a constellation. A constellation contains two hypercliques and multiple hyperstars from various conflict hypergraphs. Theoretical results demonstrate that a constellation induces valid inequalities that could be obtained by simultaneous lifting. Moreover, these constellation inequalities can be facet defining.
The primary advancements, constellations and the associated valid inequalities, of this thesis are theoretical in nature. By providing the theory behind simultaneous lifting, researchers should be able to apply this knowledge to develop new algorithms that enable simultaneous lifting to be performed faster and over more complex integer programs.
|
3 |
Simultaneously lifting sets of variables in binary Knapsack problemsSharma, Kamana January 1900 (has links)
Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programming (IP) has been and continues to be widely used by industries to minimize cost and effectively manage resources. Faster computers and innovative IP techniques have enabled the solution to many large-scale IPs. However, IPs are NP-hard and many IPs require exponential time to solve.
Lifting is one of the most widely used techniques that helps to reduce computational time and is widely applied in today's commercial IP software. Lifting was first introduced by Gomory for bounded integer programs and a theoretical and computationally intractible technique to simultaneously lift sets of variables was introduced by Zemel in 1978.
This thesis presents a new algorithm called the Maximal Simultaneous Lifting Algorithm (MSLA), to simultaneously uplift sets of binary integer variables into a cover inequality. These lifted inequalities result in strong inequalities that are facet defining under fairly moderate assumptions.
A computational study shows that this algorithm can find numerous strong inequalities for random Knapsack (KP) instances. The pre-processing time observed for these instances is less than 1/50th of a second, which is negligible. These simultaneously lifted inequalities are easy to find and incorporating these cuts to KP instances reduced the solution time by an average of 41%. Therefore, implementing MSLA should be highly beneficial for large real-world problems.
|
4 |
Cliqued holes and other graphic structures for the node packing polytopeConley, Clark Logan January 1900 (has links)
Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Graph Theory is a widely studied topic. A graph is defined by two important features:
nodes and edges. Nodes can represent people, cities, variables, resources, products, while
the edges represent a relationship between two nodes. Using graphs to solve problems
has played a major role in a diverse set of industries for many years.
Integer Programs (IPs) are mathematical models used to optimize a problem. Often
this involves maximizing the utilization of resources or minimizing waste. IPs are
most notably used when resources must be of integer value, or cannot be split. IPs
have been utilized by many companies for resource distribution, scheduling, and conflict
management.
The node packing or independent set problem is a common combinatorial optimization
problem. The objective is to select the maximum nodes in a graph such that no two
nodes are adjacent. Node packing has been used in a wide variety of problems, which
include routing of vehicles and scheduling machines.
This thesis introduces several new graph structures, cliqued hole, odd bipartite hole,
and odd k-partite hole, and their corresponding valid inequalities for the node packing
polyhedron. These valid inequalities are shown to be new valid inequalities and conditions
are provided for when they are facet defining, which are known to be the strongest
class of valid inequalities. These new valid inequalities can be used by practitioners to
help solve node packing instances and integer programs.
|
5 |
Synchronized simultaneous lifting in binary knapsack polyhedraBolton, Jennifer Elaine January 1900 (has links)
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.
|
Page generated in 0.0637 seconds