Orientador: Alexandre César Rodrigues da Silva / Banca: Luis Antonio F. de Oliveira / Banca: Marcos Aurélio Batista / Resumo: A geração eficiente de implicantes primos é um fator importante na fase de cobertura dos mintermos em métodos de minimização de funções booleanas. Este trabalho apresenta uma versão aprimorada do método denominado de Clause-Column Table, utilizado na geração de implicantes primos. Neste novo algoritmo adicionou-se o teorema da adjacência e um novo critério de parada. Estas modificações evitaram a geração de termos nulos e iterações desnecessárias que ocorriam no algoritmo original. O algoritmo original e o aprimorado foram implementados em linguagem C e comparados. O método Clause-Column Table Aprimorado também foi comparado com o método Quine-McCluskey e Expander. Os resultados comprovaram que a versão aprimorada gera menos iterações que a versão original, e que na maioria das funções analisadas evitou-se a geração de termos nulos. Ao comparar com o método de Quine-McCluskey e o Expander comprovou-se que o método Clause-Column Table Aprimorado é superior na geração dos implicantes primos, pois em alguns casos elimina aqueles que não são necessários para a cobertura da função. De posse dos implicantes primos o problema de cobertura dos mintermos foi formulado como um problema de programação linear inteira 0 e 1, em que a solução se abre a todos os avanços ocorridos na área de programação linear visando a obtenção de uma solução mínima / Abstract: Efficient generation of prime implicants is an important factor in the coverage phase of minterms in minimization's methods of Boolean functions. This research presents an improved version of the method called Clause-Column Table, used to generate prime implicants. In this new algorithm was added to the adjacency theorem and a new stopping criterion. These modifications prevented the generation of null terms and unnecessary iterations that occurred in the original algorithm. The original and improved algorithms were implemented in C language and compared. The Clause-Column Table Improved method was compared with the Expander and Quine-McCluskey method. The results proved that the improved version generates fewer iterations than the original version, and that in most functions analyzed it was avoided the generation of null terms. Comparing Quine-McCluskey method and the Expander it was proved that the Clause-Column Table Enhanced method is superior in the generation of prime implicants, since in some cases eliminates those who are not required to cover the function. In ownership of the prime implicants the cover problem of minterms was formulated as an integer linear programming problem of 0 and 1, where the solution is open to all advances in the area of linear programming in order to obtain a minimal solution / Mestre

Crew schedules on the South African Transport Services are done by roster compilers at depots. A method that uses heuristic and mathematical programming algorithms was developed to replace existing hand methods. It is a two stage method that will use a microcomputer to assist roster compilers to draw up crew schedules. Initially timetables are subdivided into shifts and then they are combined into crew schedules. The solution, which produces a significant improvement compared with an existing crew schedule and an existing method, has been accepted in principle and computer programming has begun. In Appendix E another heuristic for the scheduling of league matches is described.

In this work we propose a flexible numerical approach to deal with models of dynamic moral hazard with simultaneous learning about the production function. Because of the complexity of the problem, analytical solutions have so far been limited in scope. The contribution is methodological: through computation, the problem can be studied under few assumptions about functional forms. We depart from a general mechanism, reformulate it as an incentive compatible mechanism, and show how it can be solved by backward induction through a sequence of linear programs. We apply our method to a few cases of interest, and confirm that uncertainty about the production function increases the volatility of the agent\'s utility in order to prevent belief manipulation, as found in the literature. / Neste trabalho, propomos uma estratégia numérica para lidar com modelos de risco moral dinâmico com aprendizado sobre a função de produção. Pela complexidade do problema, soluções analíticas na literatura têm sido limitadas em seu escopo. Nossa contribuição é metodológica: através de métodos computacionais, o problema pode ser estudado sob poucas hipóteses a respeito de formas funcionais. Partindo de um mecanismo geral, reformulamos o problema como um mecanismo compatível em incentivos, e então mostramos como este pode ser resolvido por indução retroativa por meio de uma sequência de programas lineares. Aplicamos o método a alguns casos de interesse, e confirmamos a conclusão da literatura de que a incerteza sobre a função de produção aumenta a volatilidade da utilidade do agente para prevenir manipulação de crenças.

Para uma empresa de navegação, manter uma frota grande de contêineres próprios poderia gerar custos desnecessários para manutenção dos estoques destes contêineres; contudo, se a frota de contêineres próprios for pequena, poderia resultar em um número grande de contêineres arrendados a curto prazo. Assim, nesta dissertação desenvolve-se um modelo de programação linear capaz de estimar a frota ótima de contêineres próprios e alugados, que envolve a dificuldade da tomada de decisão em um comércio extremamente desequilibrado. A revisão bibliográfica apresenta poucas publicações que tratam do tema proposto. O trabalho desenvolvido por Imai e Rivera (2001) é examinado por ser mais semelhante ao tema proposto para esta dissertação. Por tratarem do dimensionamento de frota de contêineres para dois portos e não admitirem aleatoriedades nos tempos de movimentação terrestre de contêineres outros procedimentos foram examinados. Para tentar solucionar o problema de dimensionamento de frota de contêineres próprios para a empresa de navegação dois métodos são analisados: modelo de simulação probabilística e modelo de programação linear. O modelo de simulação é desenvolvido para um problema pequeno. Conforme a ampliação deste modelo e o aumento do número de variáveis, o modelo de simulação passou a ser difícil de ser controlado, pois a mudança dos valores destas variáveis se tornaria muito difícil. O modelo de programação linear é desenvolvido com base nas características e definições adotadas para o modelo de simulação. Este modelo matemático incorpora as aleatoriedades existentes nos processos terrestres, de acordo com as hipóteses adotadas. Este modelo permite auxiliar o planejador a tomar decisões estratégicas, com relação ao tamanho da frota de contêineres necessários para atender a demanda de transporte ao longo do horizonte de planejamento, e operacionais, por apresentar o fluxo de transporte de contêineres vazios entre portos, bem como a quantidade de contêineres alugados, se necessários, para realizar as operações emergenciais associadas a picos de demanda ao longo do período de planejamento. Para testar a consistência do modelo, cenários hipotéticos foram gerados. Por meio dos resultados obtidos para estes cenários, mostra-se a relação do custo dos contêineres alugados e do custo do transporte de contêineres próprios vazios sobre o tamanho da frota de contêineres próprios. / For a carrier, provide a large fleet of owned containers could generate unnecessary costs for maintenance of their inventories; however, if the fleet of owned containers is small, it might result in a large number of short-term leased containers. Thus, it is developed a linear programming model capable to determine the optimal fleet size of owned and leased containers that involves the difficulty of decision-making in an extremely unbalanced trade. The literature survey presents few publications that deal with the considered subject. The work developed for Imai and Rivera (2001) is examined by being more similar to the subject considered in this project. For dealing with the container fleet sizing for two ports and not admitting stochastic travel times inland of containers other procedures are examined. To solve the problem of own container fleet sizing for the carriers two methods are analyzed: probabilistic simulation model and linear programming model. The simulation model is developed for a small problem. As the growing of this model and the increase of the number of variables, the simulation model becomes difficult to control, because the change of the values of these variables would become very hard. The linear programming model is developed on the basis of the characteristics and definitions adopted for the simulation model. This mathematical model incorporates the existing stochastic inland times, in accordance with the adopted hypotheses. This model allows to assist the planner to make strategical decisions, with regard to the size of the fleet of containers necessary to attempt the demand of transport throughout the planning horizon, and operational, for presenting the flow of empty cont ainers between ports, as well as the amount of leased containers, if necessary, to carry through the special operations associated the peaks of demand throughout the period of planning. To test the consistency of the model, hypothetical scenes had been generated. By the results gotten for these scenes, it is showed the relation of the cost of leases containers and the cost of the transport of empty owned containers above the owned container fleet size.

Determinar probabilidades para eventos no qual temos poucas informações ou intervalos para probabilidades não é tão simples. Para isso desenvolveremos conceitos de programação linear, que nos permite resolver de certo modo, o problema de determinar uma probabilidade para um evento de interesse, porém nem sempre de maneira única. Apresentaremos alguns exemplos clássicos da estatística, sendo eles: O Problema de Monty Hall e o Problema da Probabilidade do Testemunho. Além disso, discutiremos o problema de precificação de uma opção de compra, o quais utilizaremos programação linear para resolvê-los. / Determine probabilities for events where we have few information or intervals for probabilities is not so simple. For this we will develop concepts of linear programming, which allows us to solve, in a certain way, the problem of determine a probability for an event of interest, but not always in a unique way. We will present some classic examples of statistics, such as: The Monty Hall Problem and De La Probabilité Des Témoignages. In addition, we will discuss the problem of pricing a call option, where we will use linear programming to solve them.

Cheung, Sin Shuen. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (leaves 55-59). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Preliminaries --- p.5 / Chapter 2.1 --- Heuristics by Hoeffding and Janson --- p.5 / Chapter 2.2 --- Facts in Matrix Theory --- p.10 / Chapter 2.3 --- Facts in Probability --- p.11 / Chapter 3 --- General Chance-Constrained LMIs --- p.18 / Chapter 3.1 --- Probability Inequalities --- p.18 / Chapter 3.2 --- Safe Tractable Approximations --- p.22 / Chapter 4 --- Chance-Constrained Quadratically Perturbed LMIs --- p.27 / Chapter 4.1 --- Exact Proper Fractional Covers --- p.27 / Chapter 4.2 --- Bounding the Matrix Moment Generating Functions --- p.32 / Chapter 5 --- Computational Study --- p.39 / Chapter 5.1 --- Update Procedures for Safe Tractable Approximations --- p.39 / Chapter 5.2 --- A Numerical Example and Comparisons --- p.44 / Chapter 6 --- Conclusion --- p.54 / Bibliography --- p.55

Wong Siu Ham. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 131-138). / Abstracts in English and Chinese. / Abstract --- p.ii / Acknowledgments --- p.vi / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Motivation for Integration --- p.2 / Chapter 1.2 --- Thesis Overview --- p.4 / Chapter 2 --- Preliminaries --- p.5 / Chapter 2.1 --- Constraint Programming --- p.5 / Chapter 2.1.1 --- Constraint Satisfaction Problems (CSP's) --- p.6 / Chapter 2.1.2 --- Satisfiability (SAT) Problems --- p.10 / Chapter 2.1.3 --- Systematic Search --- p.11 / Chapter 2.1.4 --- Local Search --- p.13 / Chapter 2.2 --- Linear Programming --- p.17 / Chapter 2.2.1 --- Linear Programming Problems --- p.17 / Chapter 2.2.2 --- Simplex Method --- p.19 / Chapter 2.2.3 --- Mixed Integer Programming Problems --- p.27 / Chapter 3 --- Integration of Constraint Programming and Linear Program- ming --- p.29 / Chapter 3.1 --- Problem Definition --- p.29 / Chapter 3.2 --- Related works --- p.30 / Chapter 3.2.1 --- Illustrating the Performances --- p.30 / Chapter 3.2.2 --- Improving the Searching --- p.33 / Chapter 3.2.3 --- Improving the representation --- p.36 / Chapter 4 --- A Scheme of Integration for Solving Constraint Satisfaction Prob- lem --- p.37 / Chapter 4.1 --- Integrated Algorithm --- p.38 / Chapter 4.1.1 --- Overview of the Integrated Solver --- p.38 / Chapter 4.1.2 --- The LP Engine --- p.44 / Chapter 4.1.3 --- The CP Solver --- p.45 / Chapter 4.1.4 --- Proof of Soundness and Completeness --- p.46 / Chapter 4.1.5 --- Compared with Previous Work --- p.46 / Chapter 4.2 --- Benchmarking Results --- p.48 / Chapter 4.2.1 --- Comparison with CLP solvers --- p.48 / Chapter 4.2.2 --- Magic Squares --- p.51 / Chapter 4.2.3 --- Random CSP's --- p.52 / Chapter 5 --- A Scheme of Integration for Solving General Constrained Opti- mization Problem --- p.68 / Chapter 5.1 --- Integrated Optimization Algorithm --- p.69 / Chapter 5.1.1 --- Overview of the Integrated Optimizer --- p.69 / Chapter 5.1.2 --- The CP Solver --- p.74 / Chapter 5.1.3 --- The LP Engine --- p.75 / Chapter 5.1.4 --- Proof of the Optimization --- p.77 / Chapter 5.2 --- Benchmarking Results --- p.77 / Chapter 5.2.1 --- Weighted Magic Square --- p.77 / Chapter 5.2.2 --- Template design problem --- p.78 / Chapter 5.2.3 --- Random GCOP's --- p.79 / Chapter 6 --- Conclusions and Future Work --- p.97 / Chapter 6.1 --- Conclusions --- p.97 / Chapter 6.2 --- Future work --- p.98 / Chapter 6.2.1 --- Detection of implicit equalities --- p.98 / Chapter 6.2.2 --- Dynamical variable selection --- p.99 / Chapter 6.2.3 --- Analysis on help of linear constraints --- p.99 / Chapter 6.2.4 --- Local Search and Linear Programming --- p.99 / Appendix --- p.101 / Proof of Soundness and Completeness --- p.101 / Proof of the optimization --- p.126 / Bibliography --- p.130

In global energy and industrial market, petroleum refining industry accounts for a major share. Through proper planning and the use of adequate mathematical models for the different processing units, many profit improving opportunities can be realized. The increasing crude oil price has also made refining of crude oil blends to be a common practice. This thesis aims to provide useful insight for planning of the integrated refinery subsystems. The main subsystems referred to are (1) The crude oil unloading subsystem (2) The production and product blending subsystem and (3) The product distribution subsystem. Aspen HYSYS® was first used to develop a rigorous model for crude distillation unit (CDU) and vacuum distillation unit (VDU). The rigorous model was validated with pilot plant data from literature. The information obtained from the rigorous model is further used to develop a model for planning of the CDU and VDU. This was combined with models (obtained from empirical correlations) for fluid catalytic cracker (FCC) and hydrotreater (HDT) units to form a mathematical programming planning model used for refinery production and product blending subsystem planning. Since two different types of crude were considered, the optimum volumetric mixing ratio, the sulphur content at that mixing ratio and the CDU flow rate were determined. The yields fraction obtained from the rigorous model were then used to generate regression model using least square method. The sulphur composition of the crude oil was used as independent variable in the regression model. The generated regression models were then used to replace the regular fixed yield approach in a refinery planning model and the results compared. From the results obtained, the proposed method provided an alternative and convenient means for estimating yields from CDU and VDU than the regular fixed yield approach. The proposed aggregate model for the production and products blending subsystem was integrated with the modified scheduling model for the crude unloading subsystem developed by Lee et al. (1996) and products distribution model developed by Alabi and Castro (2009) for refinery planning. It was found that the regression model could be integrated in a refinery planning model and that the CDU flow rate was maximised as compared to the non- integrated system.

Ranking is a popular machine learning problem that has been studied extensively for more then a decade. Typical machine learning algorithms are generally built to optimize predictive performance (usually measured in accuracy) by minimizing classification error. However, there are many real world problems where correct ordering of instances is of equal or greater importance than correct classification. Learning algorithms that are built to minimize classification error are often not effective when ordering within or among classes. This gap in research created a necessity to alter the objective of such algorithms to focus on correct ranking rather then classification. Area Under the ROC Curve (AUC), which is equivalent to the Wicoxon-Mann-Whitney (WMW) statistic, is a widely accepted performance measure for evaluating ranking performance in binary classification problems. In this work we present a linear programming approach (LPR), similar to 1-norm Support Vector Machines (SVM), for ranking instances with binary outputs by maximizing an approximation to the WMW statistic. Our formulation handles non-linear problems by making use of kernel functions. The results on several well-known benchmark datasets show that our approach ranks better than 2-norm SVM and faster than the support vector ranker (SVR). The number of constraints in the linear programming formulation increases quadratically with the number of data points considered for the training of the algorithm. We tackle this problem by implementing a number of exact and approximate speed-up approaches inspired by well-known methods such as chunking, clustering and subgradient methods. The subgradient method is the most promising because of its solution quality and its fast convergence to the optimal solution. We adopted LPR formulation to survival analysis. With this approach it is possible to order subjects by risk for experiencing an event. Such an ordering enables determination of high-risk and low-risk groups among the subjects that can be helpful not only in medical studies but also in engineering, business and social sciences. Our results show that our algorithm is superior in time-to-event prediction to the most popular survival analysis tool, Cox's proportional hazard regression.

The study was initiated to determine how sheep ranches were physically and economically organized in 1964 and to select range and livestock management alternatives which would be profitable to sheep ranches. With data collected from the ranches three model ranches, representing the three most prominent strata, were constructed. These strata were determined by number of breeding ewes that were on the ranch and by the season of grazing on government land, i.e., winter, summer, or year around. After the building of these three ranches, each of them was linear programmed to find the profit maximizing combination of resources both before and following the addition of private and public capital. Capital was added in small increments, and the internal rate of return was calculated for each increment to determine the profitability of each investment. As an added tool, the capitalized value of the ranch resources was obtained showing the value of one more unit of each resource to the ranch concerned.