Dissertations / Theses on the topic 'Mathematical programming formulation'

Thesis (Ph. D.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2006.
Prausnitz, Mark, Committee Member ; Vidakovic, Brani, Committee Member ; Lee, Eva, Committee Chair ; Nemhauser, George, Committee Member ; Johnson, Ellis, Committee Member. Includes bibliographical references.

Doutoramento em Engenharia Eletrotécnica
Network virtualisation is seen as a promising approach to overcome the so-called “Internet impasse” and bring innovation back into the Internet, by allowing easier migration towards novel networking approaches as well as the coexistence of complementary network architectures on a shared infrastructure in a commercial context. Recently, the interest from the operators and mainstream industry in network virtualisation has grown quite significantly, as the potential benefits of virtualisation became clearer, both from an economical and an operational point of view. In the beginning, the concept has been mainly a research topic and has been materialized in small-scale testbeds and research network environments. This PhD Thesis aims to provide the network operator with a set of mechanisms and algorithms capable of managing and controlling virtual networks. To this end, we propose a framework that aims to allocate, monitor and control virtual resources in a centralized and efficient manner. In order to analyse the performance of the framework, we performed the implementation and evaluation on a small-scale testbed. To enable the operator to make an efficient allocation, in real-time, and on-demand, of virtual networks onto the substrate network, it is proposed a heuristic algorithm to perform the virtual network mapping. For the network operator to obtain the highest profit of the physical network, it is also proposed a mathematical formulation that aims to maximize the number of allocated virtual networks onto the physical network. Since the power consumption of the physical network is very significant in the operating costs, it is important to make the allocation of virtual networks in fewer physical resources and onto physical resources already active. To address this challenge, we propose a mathematical formulation that aims to minimize the energy consumption of the physical network without affecting the efficiency of the allocation of virtual networks. To minimize fragmentation of the physical network while increasing the revenue of the operator, it is extended the initial formulation to contemplate the re-optimization of previously mapped virtual networks, so that the operator has a better use of its physical infrastructure. It is also necessary to address the migration of virtual networks, either for reasons of load balancing or for reasons of imminent failure of physical resources, without affecting the proper functioning of the virtual network. To this end, we propose a method based on cloning techniques to perform the migration of virtual networks across the physical infrastructure, transparently, and without affecting the virtual network. In order to assess the resilience of virtual networks to physical network failures, while obtaining the optimal solution for the migration of virtual networks in case of imminent failure of physical resources, the mathematical formulation is extended to minimize the number of nodes migrated and the relocation of virtual links. In comparison with our optimization proposals, we found out that existing heuristics for mapping virtual networks have a poor performance. We also found that it is possible to minimize the energy consumption without penalizing the efficient allocation. By applying the re-optimization on the virtual networks, it has been shown that it is possible to obtain more free resources as well as having the physical resources better balanced. Finally, it was shown that virtual networks are quite resilient to failures on the physical network.
A virtualização de rede é vista como uma abordagem promissora para ultrapassar o “Impasse da Internet” e permitir inovação na Internet, possibilitando assim uma migração fácil para novas abordagens de redes, bem como a coexistência de arquiteturas de redes complementares numa infraestrutura compartilhada e em ambiente comercial. Recentemente tem crescido de forma bastante significativa o interesse pela virtualização de rede por parte dos operadores e dos grandes fabricantes, desde que os potenciais benefícios da virtualização se tornaram claros, tanto de ponto de vista económico como operacional. No início, o conceito foi versado pelo meio académico, onde foram realizadas provas de conceito de pequena escala, e em que a virtualização de rede foi considerada como forma de investigação de novos protocolos. Esta Tese de Doutoramento tem como objetivo geral dotar uma rede de operador de um conjunto de mecanismos e algoritmos capazes de gerir e controlar redes virtuais. Para este fim, é proposta uma framework que visa alocar, monitorizar e controlar recursos virtuais de uma forma centralizada e eficiente. De forma a analisar o desempenho da framework, procedeu-se à sua implementação e avaliação numa rede de pequena dimensão. De forma a permitir que se possa efetuar uma alocação eficiente, em tempo real, e a pedido, de redes virtuais numa rede física, é proposta uma heurística para efetuar o mapeamento na rede física. Para que o operador de rede possa rentabilizar ao máximo a sua infraestrutura de rede, é ainda proposta uma formulação matemática que, através de programação linear, visa maximizar o número de redes alocadas na infraestrutura de rede. Dado que o consumo energético de uma infraestrutura de rede começa a ter significância nos custos de operação, é importante que se faça a alocação das redes virtuais no menor número de recursos físicos e também em recursos físicos ativos. Para endereçar este desafio é proposta uma formulação matemática que visa minimizar o consumo energético da rede física sem afetar a eficiência da alocação de redes virtuais. Para minimizar a fragmentação da infraestrutura de rede e ao mesmo tempo aumentar as receitas do operador, é também estendida a formulação inicial para contemplar a re-otimização de redes virtuais previamente mapeadas, fazendo com que o operador tenha um melhor aproveitamento da sua infraestrutura física. Será ainda necessário endereçar a migração de redes virtuais, quer por motivos de balanceamento de carga, quer por motivos de falha iminente de recursos físicos, sem afetar o bom funcionamento da rede virtual. Para este fim, é proposto um método baseado em técnicas de clonagem, para efetuar a migração de redes virtuais entre recursos da infraestrutura física de forma transparente e sem impacto para a rede virtual. De forma a avaliar a resiliência das redes virtuais a falhas na rede física, e ao mesmo tempo obter a solução ótima de migração de redes virtuais em caso de falha iminente dos recursos físicos, a formulação matemática é estendida para minimizar o número de nós migrados em simultâneo com a realocação de ligações virtuais. Em comparação com as nossas propostas de otimização verificou-se que as heurísticas existentes para mapeamento de redes virtuais têm um desempenho muito baixo. Verificou-se ainda que é possível efetuar a redução do consumo energético sem a penalização da alocação eficiente. Com a re-otimização das redes virtuais mostrou-se que é possível obter mais recursos livres, assim como obter uma melhor distribuição dos recursos. Por último, demonstrou-se que as redes virtuais são bastante resilientes a falhas na rede física.

Using concepts of the socio-technical systems theory, this dissertation defines mathematically the problems of cooperative teams formation considering social and technical constraints separately, and then presents their computational complexity. Mainly, it is defined and studied the central problem in this work, which jointly considers social and technical requirements for creating teams of cooperative work, to be called FEST (Socio-Technical Teams Formation Problem). Two mathematical formulations and a meta-heuristic are proposed for FEST. One formulation uses a cubic number of variables and constraints, whereas the second one has a quadratic number of variables but an exponential number of constraints. The proposed heuristic is based on the Non-monotonic Simulated Annealing meta-heuristic with local search using swap-like operators. The correctness of both formulations is proved. A polynomial algorithm to separate the constraints of the second formulation is presented. It is proved that the two formulations provide the same linear programming bound, and valid inequalities to strengthen it are proposed. For the compact formulation, some classes of valid inequalities are shown to be facet-inducing under suitable hypotheses. Finally, it is statistically analyzed the performance of the presented formulations and meta-heuristic. Real and random generated instances are used in the computational experiments.
Utilizando conceitos da Teoria dos Sistemas SociotÃcnicos, este trabalho define matematicamente os problemas de formaÃÃo de equipes cooperativas considerando separadamente restriÃÃes sociais e tÃcnicas e apresenta a complexidade computacional dos mesmos. Sobretudo, à definido e estudado o problema central deste trabalho, que considera conjuntamente requisitos sociais e tÃcnicos para criaÃÃo de equipes de trabalho cooperativo, denominado FEST (Problema de FormaÃÃo de Equipes SociotÃcnicas). Duas formulaÃÃes matemÃticas e uma meta-heurÃstica para o FEST sÃo propostas. Uma formulaÃÃo utiliza um nÃmero cÃbico de variÃveis e restriÃÃes, enquanto a segunda formulaÃÃo possui um nÃmero quadrÃtico de variÃveis, mas um nÃmero exponencial de restriÃÃes. A meta-heurÃstica proposta à baseada no Simulated Annealing NÃo-MonotÃnico com busca local que usa operadores tipo swap. A corretude de ambas as formulaÃÃes à provada. Um algoritmo polinomial para separar as restriÃÃes da segunda formulaÃÃo à apresentado. Mostra-se que as duas formulaÃÃes fornecem o mesmo limite de programaÃÃo linear, e desigualdades vÃlidas para fortalecÃ-lo sÃo propostas. Para a formulaÃÃo compacta, algumas classes de desigualdades vÃlidas sÃo demonstradas indutoras de facetas sob hipÃteses apropriadas. Por fim, foi analisado estatisticamente o desempenho das formulaÃÃes e da meta-heurÃstica apresentadas. InstÃncias reais e geradas aleatoriamente sÃo usadas nos experimentos computacionais.

We consider two classes of stochastic programming models which are motivated by two applications related to the field of aviation. The first problem we consider is the network capacity planning problem, which arises in capacity planning of systems with network structures, such as transportation terminals, roadways and telecommunication networks. We study this problem in the context of airport terminal capacity planning. In this problem, the objective is to determine the optimal design and expansion capacities for different areas of the terminal in the presence of uncertainty in future demand levels and expansion costs, such that overall passenger delay is minimized. We model this problem as a nonlinear multistage stochastic integer program with a multicommodity network flow structure. The formulation requires the use of time functions for maximum delays in passageways and processing stations, for which we derive approximations that account for the transient behavior of flow. The deterministic equivalent of the developed model is solved via a branch and bound procedure, in which a bounding heuristic is used at the nodes of the branch and bound tree to obtain integer solutions. In the second study, we consider the project portfolio optimization problem. This problem falls in the class of stochastic programs in which times of uncertainty realizations are dependent on the decisions made. The project portfolio optimization problem deals with the selection of research and development (R&D) projects and determination of optimal resource allocations for the current planning period such that the expected total discounted return or a function of this expectation for all projects over an infinite time horizon is maximized, given the uncertainties and resource limitations over a planning horizon. Accounting for endogeneity in some parameters, we propose efficient modeling and solution approaches for the resulting multistage stochastic integer programming model. We first develop a formulation that is amenable to scenario decomposition, and is applicable to the general class of stochastic problems with endogenous uncertainty. We then demonstrate the use of the sample average approximation method in solving large scale problems of this class, where the sample problems are solved through Lagrangian relaxation and lower bounding heuristics.

In formulating discrete optimization problems, it is not only important to have a correct mathematical model, but to have a well structured model that can be solved effectively. Two important characteristics of a general integer or mixed-integer program are its size (the number of constraints and variables in the problem), and its strength or tightness (a measure of how well it approximates the convex hull of feasible solutions). In designing model formulations, it is critical to ensure a proper balance between compactness of the representation and the tightness of its linear relaxation, in order to enhance its solvability. In this dissertation, we consider these issues pertaining to the modeling of mixed-integer 0-1 programming problems in general, as well as in the context of several specific real-world applications, including a telecommunications network design problem and an airspace management problem. We first consider the Reformulation-Linearization Technique (RLT) of Sherali and Adams and explore the generation of reduced first-level representations for mixed-integer 0-1 programs that tend to retain the strength of the full first-level linear programming relaxation. The motivation for this study is provided by the computational success of the first-level RLT representation (in full or partial form) experienced by several researchers working on various classes of problems. We show that there exists a first-level representation having only about half the RLT constraints that yields the same lower bound value via its relaxation. Accordingly, we attempt to a priori predict the form of this representation and identify many special cases for which this prediction is accurate. However, using various counter-examples, we show that this prediction as well as several variants of it are not accurate in general, even for the case of a single binary variable. Since the full first-level relaxation produces the convex hull representation for the case of a single binary variable, we investigate whether this is the case with respect to the reduced first-level relaxation as well, and show similarly that it holds true only for some special cases. Empirical results on the prediction capability of the reduced, versus the full, first-level representation demonstrate a high level of prediction accuracy on a set of random as well as practical, standard test problems. Next, we focus on a useful modeling concept that is frequently ignored while formulating discrete optimization problems. Very often, there exists a natural symmetry inherent in the problem itself that, if propagated to the model, can hopelessly mire a branch-and-bound solver by burdening it to explore and eliminate such alternative symmetric solutions. We discuss three applications where such a symmetry arises. For each case, we identify the indistinguishable objects in the model which create the problem symmetry, and show how imposing certain decision hierarchies within the model significantly enhances its solvability. These hierarchies render an otherwise virtually intractable formulation computationally viable using commercial software. For the first problem, we consider a problem of minimizing the maximum dosage of noise to which workers are exposed while working on a set of machines. We next examine a problem of minimizing the cost of acquiring and utilizing machines designed to cool large facilities or buildings, subject to minimum operational requirements. For each of these applications, we generate realistic test beds of problems. The decision hierarchies allow all previously intractable problems to be solved relatively quickly, and dramatically decrease the required computational time for all other problems. For the third problem, we investigate a network design problem arising in the context of deploying synchronous optical networks (SONET) using a unidirectional path switched ring architecture, a standard of transmission using optical fiber technology. Given several rings of this type, the problem is to find a placement of nodes to possibly multiple rings, and to determine what portion of demand traffic between node pairs spanned by each ring should be allocated to that ring. The constraints require that the demand traffic between each node pair should be satisfiable given the ring capacities, and that no more than a specified maximum number of nodes should be assigned to each ring. The objective function is to minimize the total number of node-to-ring assignments, and hence, the capital investment in add-drop multiplexer equipments. We formulate the problem as a mixed-integer programming model, and propose several alternative modeling techniques designed to improve the mathematical representation of this problem. We then develop various classes of valid inequalities for the problem along with suitable separation procedures for tightening the representation of the model, and accordingly, prescribe an algorithmic approach that coordinates tailored routines with a commercial solver (CPLEX). We also propose a heuristic procedure which enhances the solvability of the problem and provides bounds within 5-13% of the optimal solution. Promising computational results that exhibit the viability of the overall approach and that lend insights into various modeling and algorithmic constructs are presented. Following this we turn our attention to the modeling and analysis of several issues related to airspace management. Currently, commercial aircraft are routed along certain defined airspace corridors, where safe minimum separation distances between aircraft may be routinely enforced. However, this mode of operation does not fully utilize the available airspace resources, and may prove to be inadequate under future National Airspace (NAS) scenarios involving new concepts such as Free-Flight. This mode of operation is further compounded by the projected significant increase in commercial air traffic. (Free-Flight is a paradigm of aircraft operations which permits the selection of more cost-effective routes for flights rather than simple traversals between designated way-points, from various origins to different destinations.) We begin our study of Air Traffic Management (ATM) by first developing an Airspace Sector Occupancy Model (AOM) that identifies the occupancies of flights within three dimensional (possibly nonconvex) regions of space called sectors. The proposed iterative procedure effectively traces each flight's progress through nonconvex sector modules which comprise the sectors. Next, we develop an Aircraft Encounter Model (AEM), which uses the information obtained from AOM to efficiently characterize the number and nature of blind-conflicts (i.e., conflicts under no avoidance or resolution maneuvers) resulting from a selected mix of flight-plans. Besides identifying the existence of a conflict, AEM also provides useful information on the severity of the conflict, and its geometry, such as the faces across which an intruder enters and exits the protective shell or envelope of another aircraft, the duration of intrusion, its relative heading, and the point of closest approach. For purposes of evaluation and assessment, we also develop an aggregate metric that provides an overall assessment of the conflicts in terms of their individual severity and resolution difficulty. We apply these models to real data provided by the Federal Aviation Administration (FAA) for evaluating several Free-Flight scenarios under wind-optimized and cruise-climb conditions. We digress at this point to consider a more general collision detection problem that frequently arises in the field of robotics. Given a set of bodies with their initial positions and trajectories, we wish to identify the first collision that occurs between any two bodies, or to determine that none exists. For the case of bodies having linear trajectories, we construct a convex hull representation of the integer programming model of Selim and Almohamad, and exhibit the relative effectiveness of solving this problem via the resultant linear program. We also extend this analysis to model a situation in which bodies move along piecewise linear trajectories, possibly rotating at the end of each linear translation. For this case, we again compare an integer programming approach with its linear programming convex hull representation, and exhibit the relative effectiveness of solving a sequence of problems based on applying the latter construct to each time segment. Returning to Air Traffic Management, another future difficulty in airspace resource utilization stems from a projected increase in commercial space traffic, due to the advent of Reusable Launch Vehicle (RLV) technology. Currently, each shuttle launch cordons off a large region of Special Use Airspace (SUA) in which no commercial aircraft are permitted to enter for the specified duration. Of concern to airspace planners is the expense of routinely disrupting air traffic, resulting in circuitous diversions and delays, while enforcing such SUA restrictions. To provide a tool for tactical and planning purposes in such a context within the framework of a coordinated decision making process between the FAA and commercial airlines, we develop an Airspace Planning Model (APM). Given a set of flights for a particular time horizon, along with (possibly several) alternative flight-plans for each flight that are based on delays and diversions due to special-use airspace (SUA) restrictions prompted by launches at spaceports or weather considerations, this model prescribes a set of flight-plans to be implemented. The model formulation seeks to minimize a delay and fuel cost based objective function, subject to the constraints that each flight is assigned one of the designated flight-plans, and that the resulting set of flight-plans satisfies certain specified workload, safety, and equity criteria. These requirements ensure that the workload for air-traffic controllers in each sector is held under a permissible limit, that any potential conflicts which may occur are routinely resolvable, and that the various airlines involved derive equitable levels of benefits from the overall implemented schedule. In order to solve the resulting 0-1 mixed-integer programming problem more effectively using commercial software (CPLEX-MIP), we explore the use of various facetial cutting planes and reformulation techniques designed to more closely approximate the convex hull of feasible solutions to the problem. We also prescribe a heuristic procedure which is demonstrated to provide solutions to the problem that are either optimal or are within 0.01% of optimality. Computational results are reported on several scenarios based on actual flight data obtained from the Federal Aviation Administration (FAA) in order to demonstrate the efficacy of the proposed approach for air traffic management (ATM) purposes. In addition to the evaluation of these various models, we exhibit the usefulness of this airspace planning model as a strategic planning tool for the FAA by exploring the sensitivity of the solution provided by the model to changes both in the radius of the SUA formulated around the spaceport, and in the duration of the launch-window during which the SUA is activated.
Ph. D.

This thesis compares different mixed integer programming (MIP) formulations for sequencing of tasks in the context of avionics scheduling. Sequencing is a key concern in many discrete optimisation problems, and there are numerous ways of accomplishing sequencing with different MIP formulations. A scheduling tool for avionic systems has previously been developed in a collaboration between Saab and Linköping University. This tool includes a MIP formulation of the scheduling problem where one of the model components has the purpose to sequence tasks. In this thesis, this sequencing component is replaced with other MIP formulations in order to study whether the computational performance of the scheduling tool can be improved. Different scheduling instances and objective functions have been used when performing the tests aiming to evaluate the performances, with the computational times of the entire avionic scheduling model determining the success of the different MIP formulations for sequencing. The results show that the choice of MIP formulation makes a considerable impact on the computational performance and that a significant improvement can be achieved by choosing the most suitable one.

The growth in the interdependence and complexity of socio-technical systems requires the development of tools and techniques to aid in the formulation of better policies. The efforts of this research focus towards developing methodologies and support tools for better policy design and formulation. In this thesis, a new framework and a systematic approach for the formulation of policies are proposed. Focus has been directed to the interactions between policy measures, inspired by concepts in process design and network analysis. Furthermore, we have developed an agent-based approach to create a virtual environment for the exploration and analysis of different configurations of policy measures in order to build policy packages and test the effects of changes and uncertainties while formulating policies. By developing systematic approaches for the formulation and analysis of policies it is possible to analyse different configuration alternatives in greater depth, examine more alternatives and decrease the time required for the overall analysis. Moreover, it is possible to provide real-time assessment and feedback to the domain experts on the effect of changes in the configurations. These efforts ultimately help in forming more effective policies with synergistic and reinforcing attributes while avoiding internal contradictions. This research constitutes the first step towards the development of a general family of computer-based systems that support the design of policies. The results from this research also demonstrate the usefulness of computational approaches in addressing the complexity inherent in the formulation of policies. As a proof of concept, the proposed framework and methodologies have been applied to the formulation of policies that deal with transportation issues and emission reduction, but can be extended to other domains.

by Wan-Lung Ng.
Thesis submitted in: November 1997.
On added t.p.: January 19, 1998.
Thesis (M.Phil.)--Chinese University of Hong Kong, 1998.
Includes bibliographical references (leaves 114-119).
Abstract also in Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Overview --- p.1
Chapter 1.2 --- Organization Outline --- p.5
Chapter 2 --- Literature Review --- p.7
Chapter 2.1 --- Modern Portfolio Theory --- p.7
Chapter 2.1.1 --- Mean-Variance Model --- p.9
Chapter 2.1.2 --- Setting-up the relationship between the portfolio and its component securities --- p.11
Chapter 2.1.3 --- Identifying the efficient frontier --- p.12
Chapter 2.1.4 --- Selecting the best compromised portfolio --- p.13
Chapter 2.2 --- Stochastic Optimal Control --- p.17
Chapter 2.2.1 --- Dynamic Programming --- p.18
Chapter 2.2.2 --- Dynamic Programming Decomposition --- p.21
Chapter 3 --- Multiple Period Portfolio Analysis --- p.23
Chapter 3.1 --- Maximization of Multi-period Consumptions --- p.24
Chapter 3.2 --- Maximization of Utility of Terminal Wealth --- p.29
Chapter 3.3 --- Maximization of Expected Average Compounded Return --- p.33
Chapter 3.4 --- Minimization of Time to Reach Target --- p.35
Chapter 3.5 --- Goal-Seeking Investment Model --- p.37
Chapter 4 --- Multi-period Mean-Variance Analysis with a Riskless Asset --- p.40
Chapter 4.1 --- Motivation --- p.40
Chapter 4.2 --- Dynamic Mean-Variance Analysis Formulation --- p.43
Chapter 4.3 --- Auxiliary Problem Formulation --- p.45
Chapter 4.4 --- Efficient Frontier in Multi-period Portfolio Selection --- p.53
Chapter 4.5 --- Obseravtions --- p.58
Chapter 4.6 --- Solution Algorithm for Problem E (w) --- p.62
Chapter 4.7 --- Illstrative Examples --- p.63
Chapter 4.8 --- Verification with Single-period Efficient Frontier --- p.72
Chapter 4.9 --- Generalization to Cases with Nonlinear Utility Function of E (xT) and Var (xT) --- p.75
Chapter 5 --- Dynamic Portfolio Selection without Risk-less Assets --- p.84
Chapter 5.1 --- Construction of Auxiliuary Problem --- p.88
Chapter 5.2 --- Analytical Solution for Efficient Frontier --- p.89
Chapter 5.3 --- Reduction to Investment Situations with One Risk-free Asset --- p.101
Chapter 5.4 --- "Multi-period Portfolio Selection via Maximizing Utility function U(E {xT),Var (xT))" --- p.103
Chapter 6 --- Conclusions and Recommendations --- p.108
Chapter 6.1 --- Summaries and Achievements --- p.108
Chapter 6.2 --- Future Studies --- p.110
Chapter 6.2.1 --- Constrained Investment Situations --- p.110
Chapter 6.2.2 --- Including Higher Moments --- p.111

Ng Cho Yiu.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2005.
Includes bibliographical references (leaves 70-74).
Abstracts in English and Chinese.
Abstract --- p.i
Acknowledgement --- p.iii
Preface --- p.x
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Multiple Access --- p.1
Chapter 1.1.1 --- Time Division Multiple Access --- p.2
Chapter 1.1.2 --- Frequency Division Multiple Access --- p.3
Chapter 1.1.3 --- Code Division Multiple Access --- p.3
Chapter 1.1.4 --- Hybrid Multiple Access Scheme --- p.4
Chapter 1.2 --- Goal Programming --- p.5
Chapter 2 --- Previous Works in Channel Assignment --- p.10
Chapter 2.1 --- Voice Service Network --- p.10
Chapter 2.2 --- Data Network --- p.11
Chapter 2.2.1 --- Throughput Optimization --- p.13
Chapter 2.2.2 --- Channel Assignment Schemes with QoS Consideration --- p.14
Chapter 3 --- General Channel Assignment Scheme --- p.16
Chapter 3.1 --- Baseline Model --- p.17
Chapter 3.2 --- Goal Ranking --- p.22
Chapter 3.3 --- Model Transformation --- p.22
Chapter 3.4 --- Proposed Algorithms --- p.23
Chapter 3.4.1 --- Channel Swapping Algorithm --- p.24
Chapter 3.4.2 --- Best-First-Assign Algorithm --- p.26
Chapter 4 --- Special Case Algorithms --- p.28
Chapter 4.1 --- Single Order of Selection Diversity --- p.28
Chapter 4.1.1 --- System Model --- p.29
Chapter 4.1.2 --- Proposed Algorithm --- p.30
Chapter 4.1.3 --- Extension of Algorithm --- p.31
Chapter 4.2 --- Single Channel Assignment --- p.32
Chapter 4.2.1 --- System Model --- p.33
Chapter 4.2.2 --- Proposed Algorithms --- p.34
Chapter 5 --- Performance Evaluation --- p.37
Chapter 5.1 --- General Channel Assignment and Single Channel Assignment --- p.37
Chapter 5.1.1 --- System Model --- p.38
Chapter 5.1.2 --- Lower Bound of Weighted Sum of Unsatisfactory Function --- p.40
Chapter 5.1.3 --- Performance Evaluation I --- p.41
Chapter 5.1.4 --- Discussion --- p.44
Chapter 5.1.5 --- Performance Evaluation II --- p.44
Chapter 5.2 --- Single Order of Selection Diversity Algorithm --- p.47
Chapter 5.2.1 --- System Model --- p.47
Chapter 5.2.2 --- Performance Evaluation I --- p.49
Chapter 5.2.3 --- Performance Evaluation II --- p.53
Chapter 6 --- Conclusion and Future Works --- p.58
Chapter 6.1 --- Conclusion --- p.58
Chapter 6.2 --- Future Works --- p.60
Chapter 6.2.1 --- Multi-cell Channel Assignment --- p.60
Chapter 6.2.2 --- Theoretical Studies --- p.62
Chapter 6.2.3 --- Adaptive Algorithms --- p.62
Chapter 6.2.4 --- Assignment of Non-orthogonal Channels --- p.63
Chapter A --- Proof of Proposition 3.1 --- p.64
Chapter B --- Proof of Proposition 4.1 --- p.66
Chapter C --- Assignment Problem --- p.68
Bibliography --- p.74

The facility location problem is the task of optimally placing a given number of facilities in a certain subset of the plane. In this thesis, we present various mathematical programming formulations of the planar facility location problem, where potential facility locations are not specified. We first consider mixed-integer programming formulations of the planar facility locations problems with squared Euclidean and rectangular distance metrics to solve this problem to provable optimality. We also investigate a heuristic approach to solving the problem by extending the $K$-means clustering algorithm and formulating the facility location problem as a variant of a semidefinite programming problem, leading to a relaxation algorithm. We present computational results for the mixed-integer formulations, as well as compare the objective values resulting from the relaxation algorithm and the modified $K$-means heuristic. In addition, we briefly discuss some of the practical issues related to the facility location model under the continuous customer distribution.

碩士
國立成功大學
工業與資訊管理學系
105
Regression analysis is one of the most widely used decision making tools. It allows decision makers to determine the relationship between input variables and output variables. In a statistical regression analysis, data is always precise figures, which are called crisp values. However, in the complex real-world environment, data may be uncertain, written in linguistic terms, or based on personal subjective attitudes. Therefore, fuzzy set theory was developed to deal with these data. In order to express the essence of uncertainty better, scholars proposed the concept of intuitionistic fuzzy sets (IFS) as a generalization of the fuzzy set theory. In addition to including positive information, it also includes negative information. There have been few studies of intuitionistic fuzzy regression (IFR) models. The direction of these studies was decided by three elements: data-type and parameter-type, solution approaches, and computation of the estimation error. In this study, the available data for both input variables and output variables are assumed to be intuitionistic fuzzy numbers (IFN), and the model parameters are crisp numbers. The parameters are crisp values rather than IFN because IFN multiplied with each other will bring about an over-increase in the spread of the IFN. In other words, the fuzziness of numbers will be over-increased. Different from the traditional solution methods such as the least-squares method, this study uses mathematical programming methods. The concept of decomposition rules and IFN-cuts are also used to build models. Two different approaches are proposed in this study. The predictive ability of the obtained models is evaluated by using similarity and distance measures. The results indicate that the models proposed in this study are better than their counterparts.

Classical mechanics is deceptively simple. It is surprisingly easy to get the right answer with fallacious reasoning or without real understanding. To address this problem we use computational techniques to communicate a deeper understanding of Classical Mechanics. Computational algorithms are used to express the methods used in the analysis of dynamical phenomena. Expressing the methods in a computer language forces them to be unambiguous and computationally effective. The task of formulating a method as a computer-executable program and debugging that program is a powerful exercise in the learning process. Also, once formalized procedurally, a mathematical idea becomes a tool that can be used directly to compute results.

In this thesis we investigate how intelligent techniques, such as Evolutionary Algorithms, can be applied to finding solutions to discrete optimal control problems. Also, a detailed investigation is carried out into the design and development of a superior execution environment for Evolutionary Algorithms.

An overview of the basic processes of an Evolutionary Algorithm is given, as well as detailed descriptions for several genetic operators. Several additional operators that may be applied in conjunction with an Evolutionary Algorithm are also studied. These operators include several versions of the simplex method, as well as 3 distinct hill -climbers, each designed for a specific purpose. The hill -climbing routines have been designed for purposes that include local search, escaping local minima, and a hill -climbing routine designed for self -adaptation to a broad range of problems.

The mathematical programming formulation of discrete optimal control problems is used to generate a class of highly constrained problems. Techniques are developed to accurately and rapidly solve these problems, whilst satisfying the equality constraints to machine accuracy.

The improved execution environment for Evolutionary Algorithms proposes the use of a Graphical User Interface for data visualisation, algorithm control and monitoring, as well as a Client/Server network interface for connecting the GUI to remotely run algorithms.

abstract: This research by studies the computational performance of four different mixed integer programming (MIP) formulations for single machine scheduling problems with varying complexity. These formulations are based on (1) start and completion time variables, (2) time index variables, (3) linear ordering variables and (4) assignment and positional date variables. The objective functions that are studied in this paper are total weighted completion time, maximum lateness, number of tardy jobs and total weighted tardiness. Based on the computational results, discussion and recommendations are made on which MIP formulation might work best for these problems. The performances of these formulations very much depend on the objective function, number of jobs and the sum of the processing times of all the jobs. Two sets of inequalities are presented that can be used to improve the performance of the formulation with assignment and positional date variables. Further, this research is extend to single machine bicriteria scheduling problems in which jobs belong to either of two different disjoint sets, each set having its own performance measure. These problems have been referred to as interfering job sets in the scheduling literature and also been called multi-agent scheduling where each agent's objective function is to be minimized. In the first single machine interfering problem (P1), the criteria of minimizing total completion time and number of tardy jobs for the two sets of jobs is studied. A Forward SPT-EDD heuristic is presented that attempts to generate set of non-dominated solutions. The complexity of this specific problem is NP-hard. The computational efficiency of the heuristic is compared against the pseudo-polynomial algorithm proposed by Ng et al. [2006]. In the second single machine interfering job sets problem (P2), the criteria of minimizing total weighted completion time and maximum lateness is studied. This is an established NP-hard problem for which a Forward WSPT-EDD heuristic is presented that attempts to generate set of supported points and the solution quality is compared with MIP formulations. For both of these problems, all jobs are available at time zero and the jobs are not allowed to be preempted.
Dissertation/Thesis
Ph.D. Industrial Engineering 2012