Fractional aircraft ownership programs offer companies and individuals all the benefits of owning private jet, such as safety, consistency, and guaranteed availability, at a fraction of the cost of owning an aircraft. In the fractional ownership model, the partial owners of an aircraft are entitled to certain number of hours per year, and the management company is responsible for all the operational considerations and making sure an aircraft is available to the owners at the requested time and location. This thesis research proposes advance optimization techniques to help the management company to optimally operate its available resources and provides tools for strategic decision making. The contributions of this thesis are: (i) The development of optimization methodologies to assign and schedule aircraft and crews so that all flight requests are covered at the lowest possible cost. First, a simple model is developed to solve the crew pairing and aircraft routing problem with column generation assuming that a crew stays with one specific aircraft during its duty period. Secondly, this assumption is partially relaxed to improve resource utilization by revising the simple model to allow a crew to use another aircraft when its original aircraft goes under long maintenance. Thirdly, a new comprehensive model utilizing Benders decomposition technique and a fleet-station time line is proposed to completely relax the assumption that crew stays with one specific aircraft. It combines the fleet assignment, aircraft routing, and crew pairing problems. In the proposed methodologies, real world details are taken into consideration, such as crew transportation and overtime costs, scheduled and unscheduled maintenance effects, crew rules, and the presence of non-crew-compatible fleets. Scheduling with time windows is also discussed. (ii) The analysis of operational strategies to provide decision making support. Scenario analyses are performed to provide insights on improving business profitability and aircraft availability, such as impact of aircraft maintenance, crew swapping, effect of increasing demand by Jet-card and geographical business expansion, size of company owned aircraft, and strategies to deal with the stochastic feature of unscheduled maintenance and demand.

In this thesis we develop integer programming approaches for solving network flow problems with equal-split restrictions. Such problems arise in traffic engineering of internet protocol networks. Equal-split structure is used in protocols like OSPF and IS-IS that allow flow to be split among the multiple shortest paths. Equal-split assumptions also arise in peer-to-peer networks and road optimization problems. All the previous work on this problem has been focused on developing heuristic methods for the specific applications. We are the first ones to study the problem as a general network flow problem and provide a polyhedral study. First we consider a general multi-commodity network flow problem with equal split restrictions. This problem is NP-hard in general. We perform a polyhedral study on mixed integer linear programming formulation for this problem. Valid inequalities are obtained, and are incorporated within a branch-and-cut framework to solve the problem. We provide fast separation schemes for most of the families of valid inequalities. Computational results are presented to show the effectiveness of cutting plane families. Next, we consider the OSPF weight setting problem. We propose an integer programming formulation for this problem. A decomposition based approach to solve the problem is presented next. Valid inequalities, exploiting the structure, are obtained for this problem. We also propose heuristic methods to get good starting solutions for the problem. The proposed cutting planes and heuristic methods are integrated within a branch-and-cut framework to solve the problem. We present computational experiments that demonstrate the effectiveness of our approach to obtain solutions with tight optimality gaps as compared with default CPLEX. Finally, we consider an equal split flow problem on bipartite graphs. We present an integer programming formulation for this problem that models the equal-split in a different way than the multi-commodity network flow problem discussed before. Valid inequalities and heuristic methods for this problem are proposed, and are integrated within the branch-and-cut framework. We present computational experiments demonstrating the effectiveness of our solution strategy. We present an alternate formulation for the problem with some favorable polyhedral properties. Lastly, a computational comparison between the two formulations is presented.

In this thesis, we consider multiobjective combinatorial optimization problems. We address two main topics. We first address the polynomially solvable cases of the Traveling Salesperson Problem and the Bottleneck Traveling Salesperson Problem. We consider multiobjective versions of these problems with different combinations of objective functions, analyze their computational complexities and develop exact algorithms where possible. We next consider generating extreme supported nondominated points of multiobjective integer programming problems for any number of objective functions. We develop two algorithms for this purpose. The first one is an exact algorithm and finds all such points. The second algorithm finds only a subset of extreme supported nondominated points providing a worst case approximation for the remaining points.

In this study, weight optimization of two dimensional steel frames is carried out in which the flexibility of beam-to-column connections and the soil-structure interaction are considered. In the analysis and design of steel frames, beam-tocolumn connections are assumed to be either fully rigid or perfectly pinned. However, the real behavior of beam-to-column connections is actually between these extremes. Namely, even the simple connections used in practice possess some stiffness falling between these two cases mentioned above. Moreover, it is found that there exists a nonlinear relationship between the moment and beam-to-column rotation when a moment is applied to a flexible connection. These partially restrained connections influence the drift (P- effect) of whole structure as well as the moment distribution in beams and columns. Use of a direct nonlinear inelastic analysis is one way to account for all these effects in frame design. To be able to implement such analysis, beam-to-column connections should be assumed and modeled as semi-rigid connections. In the present study, beam-to-column connections are modeled as &ldquo / end plate without column stiffeners&rdquo / and &ldquo / top and seat angle with web angles&rdquo / . Soil-structure interaction is also included in the analysis. Frames are assumed to be resting on nonlinear soil, which is represented by a set of axial elements. Particle swarm optimization method is used to develop the optimum design algorithm. The Particle Swarm method is a numerical optimization technique that simulates the social behavior of birds, fishes and bugs. In nature fish school, birds flock and bugs swarm not only for reproduction but for other reasons such as finding food and escaping predators. Similar to birds seek to find food, the optimum design process seeks to find the optimum solution. In the particle swarm optimization each particle in the swarm represents a candidate solution of the optimum design problem. The design algorithm presented selects sections for the members of steel frame from the complete list of sections given in LRFD- AISC (Load and Resistance Factor Design, American Institute of Steel Construction). Besides, the design constraints are implemented from the specifications of the same code which covers serviceability and strength limitations. The optimum design algorithm developed is used to design number of rigid and semi-rigid steel frames.

Steel space frames having irregular shapes when subjected to lateral loads caused by wind or earthquakes undergo twisting as a result of their unsymmetrical topology. As a result, torsional moment comes out which is required to be resisted by the three dimensional frame system. The members of such frame are generally made out of steel I sections which are thin walled open sections. The simple beam theory is not adequate to predict behavior of such thin-walled sections under torsional moments due to the fact that the large warping deformations occur in the cross section of the member. Therefore, it is necessary to consider the effect of warping in the design of the steel space frames having members of thin walled steel sections is significant. In this study the optimum design problem of steel space frames is formulated according to the provisions of LRFD-AISC (Load and Resistance factor design of American Institute of Steel Construction) in which the effect of warping is also taken into account. Ant colony optimization and harmony search techniques two of the recent methods in stochastic search techniques are used to obtain the solution of the design problem. Number of space frame examples is designed by the algorithms developed in order to demonstrate the effect of warping in the optimum design.

In this thesis, the optimum design algorithm is presented for reinforced concrete special moment frames. The objective function is considered as the total cost of reinforced concrete frame which includes the cost of concrete, formwork and reinforcing steel bars. The cost of any component is inclusive of material, fabrication and labor. The design variables in beams are selected as the width and the depth of beams in each span, the diameter and the number of longitudinal reinforcement bars along the span and supports. In columns the width and the depth of the column section, the number and the diameter of bars in x and y directions are selected as design variables. The column section database is prepared which includes the width and height of column section, the diameter and the number of reinforcing bars in the column section is constructed. This database is used by the design algorithm to select appropriate sections for the columns of the frame under consideration. The design constraints are implemented from ACI 318-05 which covers the flexural and shear strength, serviceability, the minimum and maximum steel percentage for flexural and shear reinforcement, the spacing requirements for the reinforcing bars and the upper and lower bound requirements for the concrete sections. The optimum design problem formulated according to ACI 318-05 provisions with the design variables mentioned above turns out to be a combinatorial optimization problem. The solution of the design problem is obtained by using the harmony search algorithm (HS) which is one of the recent additions to meta-heuristic optimization techniques which are widely used in obtaining the solution of combinatorial optimization problems. The HS algorithm is quite simple and has few parameters to initialize and consists of simple steps which make it easy to implement. Number of design examples is presented to demonstrate the efficiency and robustness of the optimum design algorithm developed.

Finding the true nondominated points is typically hard for Multi-objective Combinatorial Optimization (MOCO) problems. Furthermore, it is not practical to generate all of them since the number of nondominated points may grow exponentially as the problem size increases. In this thesis, we develop an exact algorithm to find all nondominated points in a specified region. We combine this exact algorithm with a heuristic algorithm that approximates the possible locations of the nondominated points. Interacting with a decision maker (DM), the heuristic algorithm first approximately identifies the region that is of interest to the DM. Then, the exact algorithm is employed to generate all true nondominated points in this region. We conduct experiments on Multi-objective Assignment Problems (MOAP), Multi-objective Knapsack Problems (MOKP) and Multi-objective Shortest Path (MOSP) Problems / and the algorithms work well. Finding the worst possible value for each criterion among the set of efficient solutions has important uses in multi-criteria problems since the proper scaling of each criterion is required by many approaches. Such points are called nadir points. v It is not straightforward to find the nadir points, especially for large problems with more than two criteria. We develop an exact algorithm to find the nadir values for multi-objective integer programming problems. We also find bounds with performance guarantees. We demonstrate that our algorithms work well in our experiments on MOAP, MOKP and MOSP problems. Assuming that the DM&#039 / s preferences are consistent with a quasiconcave value function, we develop an interactive exact algorithm to solve MIP problems. Based on the convex cones derived from pairwise comparisons of the DM, we generate constraints to prevent points in the implied inferior regions. We guarantee finding the most preferred point and our computational experiments on MOAP, MOKP and MOSP problems show that a reasonable number of pairwise comparisons are required.

No description available.

Ο Ακέραιος Προγραμματισμός είναι κλάδος του Γραμμικού Μαθηματικού Προγραμματισμού, και αποτελεί τμήμα της συνδιαστικής βελτιστοποίησης. Στόχος της χρήσης του είναι η βελτιστοποίηση συστημάτων παραγωγής ή διοίκησης. Ο Ακέραιος Προγραμματισμός χρησιμοποιείται για την επίλυση πρακτικών προβλημάτων, όπως: • Χρονοδιαγράμματα (Scheduling) • Σχεδιασμός παραγωγής • Παράλληλη εκτέλεση εργασιών • Τηλεπικοινωνίες Μπορεί να φαίνεται ότι τα προβλήματα ακεραίου προγραμματισμού είναι εύκολο να λυθούν. Παρ’όλ’αυτά, κάτι τέτοιο δεν ισχύει, διότι οι αστρονομικά μεγάλοι ακέραιοι αριθμοί, καθώς επίσης και η στρογγυλοποίηση και αφαίρεση μη ακεραίων λύσεων από ένα πρόβλημα γραμμικού προγραμματισμού οδηγούν σε προβλήματα και λανθασμένα συμπεράσματα. Οι κυριότερες τεχνικές Ακεραίου Προγραμματισμού είναι οι εξής: • Μέθοδος κλάδου και φραγής (Branch and Bound) • Τεχνικές περιορισμού του εφικτού χώρου (Cutting Planes) • Μέθοδοι απαρίθμησης • Διαμεριστικοί αλγόριθμοι • Αλγόριθμοι βασισμένοι στη θεωρία ομάδων (Gomory) Η προπτυχιακή αυτή διπλωματική εργασία έχει στόχο να παρουσιάσει δύο από αυτές τις τεχνικές λεπτομερώς, την μέθοδο κλάδου και φραγής και τεχνικές περιορισμού του εφικτού χώρου, και να κάνει κατανοητή τη χρησιμότητα των αλγορίθμων αυτών μέσα από παραδείγματα που αφορούν προβλήματα ακέραιου προγραμματισμού. / Integer Programming is a branch of Linear Mathematical Programming, and is part of the combinatorial optimization. The purpose of using the system optimization of production or administration. The Integer Programming is used to solve practical problems, such as: • Timelines (Scheduling) • Production Design • Parallel execution of works • Telecommunications It may seem that the integer programming problems are easy to solve. However, this is not true, because the astronomically large integers, as well as rounding and removing non-integer solutions of a linear programming problem lead to problems and false conclusions. The main technical Integer Programming are: • branch and bound method (Branch and Bound) • Technical limitations of feasible region (Cutting Planes) • Methods of enumeration • Diameristikoi algorithms • Algorithms based on the theory of groups (Gomory) Undergraduate this thesis aims to present two of these techniques in detail, the branch and bound method and techniques to reduce the feasible region, and make understandable the usefulness of these algorithms through examples involving integer programming problems.

Indoor Positioning Systems (IPS) using the existing WLAN have won growing interest in the last years, it can be a perfect supplement to provide location information of users in indoor environments where other positioning techniques such as GPS, are not much effective. The thesis manuscript proposes a new approach to define a WLAN-based indoor positioning system (WLAN-IPS) as a combinatorial optimization problem to guarantee the requested communication quality while optimizing the positioning error. This approach is characterised by several difficult issues we tackled in three steps.At first, we designed a WLAN-IPS and implemented it as a test framework. Using this framework, we looked at the system performance under various experimental constraints. Through these experiments, we went as far as possible in analysing the relationships between the positioning error and the external environmental factors. These relationships were considered as evaluation indicators of the positioning error. Secondly, we proposed a model that defines all major parameters met in the WLAN-IPS from the literature. As the original purpose of the WLAN infrastructures is to provide radio communication access, we introduced an additional purpose which is to minimize the location error within IPS context. Two main indicators were defined in order to evaluate the network Quality of Service (QoS) and the positioning error for Location-Based Service (LBS). Thirdly, after defining the mathematical formulation of the optimisation problem and the key performance indicators, we proposed a mono-objective algorithm and a multi-objective algorithm which are based on Tabu Search metaheuristic to provide good solutions within a reasonable amount of time. The simulations demonstrate that these two algorithms are highly efficient for the indoor positioning optimization problem.