Browsing by Subject "Integer programming"
Now showing 1 - 12 of 12
Results Per Page
Sort Options
Item A computer algorithm for improving the day-to-day well field operation for energy conservation(Texas Tech University, 1990-05) Lee, TehfangNot availableItem A constructive primal-dual cutting-plane algorithm for all-integer programming(Texas Tech University, 1980-12) Ghandforoush, ParvizNot availableItem A group theoretic partial enumeration algorithm for all-integer programming(Texas Tech University, 1985-08) Zaatari, Abbas TNot availableItem An all-integer cutting plane algorithm with an advanced start(Texas Tech University, 1981-08) Hanna, Michael EdwardNot availableItem Branch-and-cut for piecewise linear optimization(2012-05) Rajat, Gupta; Farias, Ismael R. d.; Simonton, James L.; Matis, Timothy I.; Smith, Phillip; Zhang, YuanlinIn this research we report and analyze the results of our extensive testing of branch-and- cut for piecewise linear optimization using the cutting planes. We tested large instances for transshipment problem using MIP, LOG and SOS2 formulations. Besides analysis of the performance of the cuts, we also analyze the effect of formulation of the performance of branch-and-cut. These tests were conducted using callable libraries of CPLEX and GUROBI. Finally, we also analyzed the results of piecewise linear optimization problems with semi- continuous constraints.Item A column generation approach for stochastic optimization problems(2006) Wang, Yong Min; Bard, Jonathan F.; Morton, David P.Item Flight Gate Assignment and Proactive Flight Gate Reassignment Optimization for Hub and Spoke Airline Operations(2010-12) Maharjan, B; Matis, Timothy I.; Kobza, John E.; Smith, Milton L.; Simonton, James L.; Bremer, Ronald H.The flight gate assignment problem is encountered by gate managers at an airport on a periodic basis. This assignment should be made in such as way so as to balance the perspectives of the airline and customer simultaneously, while providing buffers for disrupting unexpected events. In this dissertation, a binary integer multicommodity gate flow network model is presented for finding the optimum flight-gate assignment with the objective of both minimizing the fuel burn cost of aircraft taxi by type and the expected walking distance of connecting passengers magnified by time windows. While this network formulation is efficient, a heuristic approach of grouping gates into zones and sub-zones is developed for large-problem instances in which non-polynomial complexity becomes prohibitive. This formulation and heuristic application is demonstrated for the gating of scheduled flights of Continental Airlines at George W. Bush Intercontinental Airport in Houston (IAH). Reassignments of flights occur when scheduled flight gate assignments are disrupted, causing flight gate conflicts due to flight delays. Flight delays are caused by a host of problems, such as inclement weather, tardy crews, mechanical problems, tardy passengers, airport security issues, airport congestion, delay propagation between airports, etc. In this dissertation, a Binary Integer Program is formulated for the optimal reassignment of planes to gates in response to day-of flight delays. This program minimizes the total walking distance of those connecting and originating passengers whose boarding passes for reassigned flights were issued prior to the gate reassignments, which can cause passenger disruption at the airport. A numerical illustration is shown for actual operations of Continental Airlines at George W. Bush Intercontinental Airport to exhibit the speed and efficiency of the model.Item Multi-vehicle Mobility Allowance Shuttle Transit (MAST) System - An Analytical Model to Select the Fleet Size and a Scheduling Heuristic(2012-10-19) Lu, WeiThe mobility allowance shuttle transit (MAST) system is a hybrid transit system in which vehicles are allowed to deviate from a fixed route to serve flexible demand. A mixed integer programming (MIP) formulation for the static scheduling problem of a multi-vehicle Mobility Allowance Shuttle Transit (MAST) system is proposed in this thesis. Based on the MIP formulation, we analyze the impacts of time headways between consecutive transit vehicles on the performance of a two-vehicle MAST system. An analytical framework is then developed to model the performance of both one-vehicle and two-vehicle MAST systems, which is used to identify the critical demand level at which an increase of the fleet size from one to two vehicles would be appropriate. Finally, a sensitivity analysis is conducted to find out the impact of a key modeling parameter, w1, the weight of operations cost on the critical demand. In this paper, we develop an insertion heuristic for a multi-vehicle MAST system, which has never been addressed in the literature. The proposed heuristic is validated and evaluated by a set of simulations performed at different demand levels and with different control parameters. By comparing its performance versus the optimal solutions, the effectiveness of the heuristic is confirmed. Compared to its single-vehicle counterpart, the multiple-vehicle MAST prevails in terms of rejection rate, passenger waiting time and overall objective function, among other performance indices.Item Multicommodity network flow models with FIFO transshipment handling policies(2011-08) Mohapatra, Chinmoy; Balakrishnan, Anantaram; Morton, David P.Integer multicommodity network flow (MCNF) models have applications in various areas like logistics, freight transportation, telecommunication and manufacturing. In this thesis we study an extension of the integer MCNF problem (MCNF-FIFO) where commodities are handled (processed) in a first-in-first-out (FIFO) order at each transshipment location and resource capacities are shared across arcs in the network. The objective of the MCNF-FIFO model is to find feasible routes for all commodities from their origins to destinations while minimizing the total transportation and holding cost or the sum of delivery times. We formulate the MCNF-FIFO problem on a time-space network and develop three different integer-programming (IP) formulations for the FIFO constraints, and two IP formulations for the flow conservations requirements. Since these formulations have a very large number of variables and constraints, we develop various algorithmic strategies to obtain good quality solutions quickly. The first strategy is to reduce the problem size by using properties of the optimal solution. We develop novel problem reduction and decomposition techniques that eliminate variables and constraints, and decompose the problem into smaller components. To further reduce the problem size, we classify the FIFO constraints into different categories by utilizing the relationships between different commodities, and provide specialized formulations for each of these categories so as to reduce the number of FIFO constraints significantly. The second strategy is to develop heuristic algorithms that provide near-optimal solutions to the MCNF-FIFO problem. Our first algorithm is an optimization-based heuristic that solves a relaxed MCNF-FIFO model with a limited number of FIFO constraints. Then, it removes the remaining infeasibilities in the solution of the relaxed MCNF-FIFO model using a repair heuristic to obtain a feasible solution. We develop two other heuristic algorithms that are stand-alone construction heuristics that build a feasible solution from scratch. To assess the effectiveness of the modeling and algorithmic enhancements, we implement the methods and apply them to three real life test instances. Our tests show that the problem reduction techniques are very effective in reducing the solution times. Among the heuristic algorithms, the optimization-based heuristic performs the best to find near-optimal solutions quickly.Item OQGRG: a multi-start algorithm for global solution of nonlinear and mixed integer programs(2001) Ugray, Zsolt Gyula; Lasdon, Leon S.Economical, managerial, engineering, and natural systems are often represented by nonlinear equations and inequalities, using discrete and continuous variables. Global Optimization provides methodologies to find the global solutions for the prescriptive models that attempt to describe, predict, and optimize their behavior. OQGRG, the algorithm presented in this dissertation, was developed to solve problems in this large target class of mixed integer, nonlinear, constrained optimization models that often have multiple local optima. OQGRG is a multi-start, 2-stage, global optimization algorithm that combines the efficiency of the Scatter Search meta-heuristic and the power of a reduced gradient nonlinear solver. It uses OptQuest as the implementation of Scatter Search and Lsgrg2 as a nonlinear local solver. OQGRG is written in standard ANSI C, and a GAMS interface provides access to many test problems available in the literature. The effectiveness of the algorithm is demonstrated by solving 155 of 159 test problems within 1% of their best known solutions.Item The bounded enumeration algorithm for all-integer programming(Texas Tech University, 1983-08) Ruparel, Bharat CNot availableItem The vehicle routing problem on tree networks : exact and heuristic methods(2011-12) Kumar, Roshan; Waller, S. Travis; Machemehl, Randy B.The Vehicle Routing Problem (VRP) is a classical problem in logistics that has been well studied by the operations research and transportation science communities. VRPs are defined as follows. Given a transportation network with a depot, a set of pickup or delivery locations, and a set of vehicles to service these locations: find a collection of routes starting and ending at the depot, such that (i) the customer's demand at a node is satisfied by exactly one vehicle, (ii) the total demand satisfied by a vehicle does not exceed its capacity, and (iii) the total distance traveled by the vehicles is minimized. This problem is especially hard to solve because of the presence of sub--tours, which can be exponential in number. In this dissertation, a special case of the VRP is considered -- where the underlying network has a tree structure (TVRP). Such tree structures are found in rural areas, river networks, assembly lines of manufacturing systems, and in networks where the customer service locations are all located off a main highway. Solution techniques for TVRPs that explicitly consider their tree structure are discussed in this dissertation. For example, TVRPs do not contain any sub-tours, thereby making it possible to develop faster solution methods. The variants that are studied in this dissertation include TVRPs with Backhauls, TVRPs with Heterogeneous Fleets, TVRPs with Duration Constraints, and TVRPs with Time Windows. Various properties and observations that hold true at optimality for these problems are discussed. Integer programming formulations and solution techniques are proposed. Additionally, heuristic methods and conditions for lower bounds are also detailed. Based on the proposed methodology, extensive computational analysis are conducted on networks of different sizes and demand distributions.