Browsing by Subject "Mixed integer programming"

Now showing 1 - 5 of 5

A comparative analysis of flight crew vacation allocation models
(2019-05) Liang, Zhaowei; Kutanoglu, Erhan
The airline industry has a long lasting history of using operations research for complex problems like crew scheduling, crew pairing, and aircraft tail assignment. However, the use of the optimization and operations research on crew vacation planning is not widespread. One of the most popular ways of assigning vacations currently is to let crew members bid for vacations using a heuristic preferential bidding system (PBS). This report will overview the existing problems in the crew vacation allocation domain. Then, it will introduce and compare an optimization based vacation allocation algorithm, an improved heuristic PBS model, and the original heuristic PBS model. Models will be compared using three performance measures as the number of unassigned vacation blocks, the number of crew members without any assigned vacation blocks, and the rank order of the preferences that are awarded to the crew members. This report also conducts a sensitivity analysis for the improved PBS model using the same performance measures
Amusement park visitor routes design and optimization
(2012-05) Shen, Yue, master of science in engineering; Hasenbein, John J.; Kutanoglu, Erhan
Amusement parks are a huge business. Guest experiences determine the success or failure for an amusement park. This report suggests an approach to improve guest experience by managing guest flow. The guest happiness optimization problem is formulated into a visitor routing management model. The constraints for this model include attraction attributes and guest behavior. To build the attraction constraints, their information is first gathered from internet, field studies and surveys, and then input into simulation software. Constraints on guest behavior are set up with a literature study and a guest survey. A two phase heuristic is developed to solve this problem with constraints. Candidate routes are generated with a route construction algorithm in the first phase. Visitor distribution and selection on these candidate routes are determined in the second phase using a mixed integer programming solver. Visitor routes are then recommended to the park’s operator side, for them to distribute to guests visiting on their vacations. Data from Disney Epcot are collected and applied in the case study to implement the methodology in this report. Attraction operations capability is maintained at the current level with no additional cost for the project, while guest satisfaction is improved by ensuring the number and type of attractions they visit. In addition, average waiting time for visitors is reduced by at least 70% in the recommended operation strategy.
Decomposition and variance reduction techniques for stochastic mixed integer programs
(2018-08) Zolan, Alexander Joseph; Hasenbein, John J.; Morton, David P.; Bard, Jonathan F; Hanasusanto, Grani A; Newman, Alexandra M
Obtaining upper and lower bounds on the optimal value of a stochastic integer program can require solution of multiple-scenario problems, which are computationally expensive or intractable using off-the-shelf integer-programming software. Additionally, optimal solutions to a two-stage problem whose second stage spans long time horizons may be optimistic, due to the model's inappropriate ability to plan for future periods which are not known in practice. To that end, we present a framework for optimizing system design in the face of a restricted class of policies governing system operation, which aim to model realistic operation. This leads to a natural decomposition of the problem yielding upper and lower bounds which we can compute quickly. We illustrate these ideas using a model that seeks to design and operate a microgrid to support a forward operating base. Here, designing the microgrid includes specifying the number and type of diesel generators, PV systems, and batteries while operating the grid involves dispatching these assets to satisfy load at minimum cost. We extend our approach to solve the same problem under load and photovoltaic uncertainty, and propose a method to generate appropriately correlated scenarios by simulating building occupancy via a bottom-up approach, then using the occupancy levels to inform environmental control unit loads on the base. Finally, in a separate line of work, we optimize the design of the strata for a stratified sampling estimator to reduce variance. We extend this method to the multivariate setting by optimizing the strata for a nonuniform Latin hypercube estimator. We then present empirical results that show that our method reduces the variance of the estimator, compared to one using equal-probability strata.
Home therapist network modeling
(2011-12) Shao, Yufen; Bard, Jonathan F.; Jarrah, Ahmad I.; Lasdon, Leon; Morton, David P.; Kutanoglu, Erhan
Home healthcare has been a growing sector of the economy over the last three decades with roughly 23,000 companies now doing business in the U.S. producing over $56 billion in combined annual revenue. As a highly fragmented market, profitability of individual companies depends on effective management and efficient operations. This dissertation aims at reducing costs and improving productivity for home healthcare companies. The first part of the research involves the development of a new formulation for the therapist routing and scheduling problem as a mixed integer program. Given the time horizon, a set of therapists and a group of geographically dispersed patients, the objective of the model is to minimize the total cost of providing service by assigning patients to therapists while satisfying a host of constraints concerning time windows, labor regulations and contractual agreements. This problem is NP-hard and proved to be beyond the capability of commercial solvers like CPLEX. To obtain good solutions quickly, three approaches have been developed that include two heuristics and a decomposition algorithm. The first approach is a parallel GRASP that assigns patients to multiple routes in a series of rounds. During the first round, the procedure optimizes the patient distribution among the available therapists, thus trying to reach a local optimum with respect to the combined cost of the routes. Computational results show that the parallel GRASP can reduce costs by 14.54% on average for real datasets, and works efficiently on randomly generated datasets. The second approach is a sequential GRASP that constructs one route at a time. When building a route, the procedure tracks the amount of time used by the therapists each day, giving it tight control over the treatment time distribution within a route. Computational results show that the sequential GRASP provides a cost savings of 18.09% on average for the same real datasets, but gets much better solutions with significantly less CPU for the same randomly generated datasets. The third approach is a branch and price algorithm, which is designed to find exact optima within an acceptable amount of time. By decomposing the full problem by therapist, we obtain a series of constrained shortest path problems, which, by comparison are relatively easy to solve. Computational results show that, this approach is not efficient here because: 1) convergence of Dantzig-Wolfe decomposition is not fast enough; and 2) subproblem is strongly NP-hard and cannot be solved efficiently. The last part of this research studies a simpler case in which all patients have fixed appointment times. The model takes the form of a large-scale mixed-integer program, and has different computational complexity when different features are considered. With the piece-wise linear cost structure, the problem is strongly NP-hard and not solvable with CPLEX for instances of realistic size. Subsequently, a rolling horizon algorithm, two relaxed mixed-integer models and a branch-and-price algorithm were developed. Computational results show that, both the rolling horizon algorithm and two relaxed mixed-integer models can solve the problem efficiently; the branch-and-price algorithm, however, is not practical again because the convergence of Dantzig-Wolfe decomposition is slow even when stabilization techniques are applied.
Transmission Expansion Planning : computational challenges toward real-size networks
(2017-09-14) Majidi-Qadikolai, Mohammad; Baldick, Ross; Santoso, Surya; Arapostathis, Ari; Bickel, James Eric; Caramanis, Constantine
The importance of the transmission network for supplying electricity demand is undeniable, and Transmission Expansion Planning (TEP) studies is key for a reliable power system. Due to increasing sources of uncertainty such as more intermittent energy resources, mobile and controllable demands, and fast technology improvements for PVs and energy storage devices, the need for using systematic ways for solving this complex problem is increased. One of the main barriers for deploying optimization-based TEP studies is computationally intractability, which is the main motivation for this research. The aim of this work is to investigate the computational challenges associated with systematic TEP studies for large-scale problems, and develop algorithms to improve computational performance. In the first step, we investigate the impact of adding security constraints (as NERC standard requirement) into TEP optimization problem, and develop the Variable Contingency List (VCL) algorithm to pre-screen security constraints to only add those that may affect the feasible region. It significantly decreases the size of the problem compared to considering all security constraints. Then, we evaluate the impact of the size of candidate lines list (number of binary variables) on TEP, and developed a heuristic algorithm to decrease the size of this list. In the next step, we integrate uncertainties into the TEP optimization problem and formulate the problem as a two-stage stochastic program. Adding uncertainties increases the size of the problem significantly. It leads us to develop a three-level filter that introduces important scenario identification index (ISII) and similar scenario elimination (SSE) technique to decrease the number of security constraints in stochastic TEP in a systematic and tractable way. We then investigate the scalability of the stochastic TEP formulation. We develop a configurable decomposition framework that allows us to decompose the original problem into subproblems that can be solved independently and in parallel. This framework can benefit from using both progressive hedging (PH) and Benders decomposition (BD) algorithms to decompose and parallelize a large-scale problem both vertically and horizontally. We have also developed a bundling algorithm that improves the performance of PH algorithm and the overall performance of the framework. We have implemented our work on a reduced ERCOT network with more than 3000 buses to demonstrate the practicality of the proposed method in this work for large-scale problems.