Spelling suggestions: "subject:"mixedinteger erogramming"" "subject:"mixedinteger cprogramming""
31 |
ROI: An extensible R Optimization InfrastructureTheußl, Stefan, Schwendinger, Florian, Hornik, Kurt 01 1900 (has links) (PDF)
Optimization plays an important role in many methods routinely used in statistics, machine learning and data science. Often, implementations of these methods rely on highly specialized optimization algorithms, designed to be only applicable within a specific application. However, in many instances recent advances, in particular in the field of convex optimization, make it possible to conveniently and straightforwardly use modern solvers instead with the advantage of enabling broader usage scenarios and thus promoting reusability.
This paper introduces the R Optimization Infrastructure which provides an extensible infrastructure to model linear, quadratic, conic and general nonlinear optimization problems in a consistent way.
Furthermore, the infrastructure administers many different solvers, reformulations, problem collections and functions to read and write optimization problems in various formats. / Series: Research Report Series / Department of Statistics and Mathematics
|
32 |
Formulações matemáticas e estratégias de resolução para o problema job shop clássico. / Integer programming formulations and resolutions strategies for the classic job shop problem.Gomez Morales, Sergio Wilson 11 May 2012 (has links)
O ambiente produtivo denominado job shop representa empresas manufatureiras com características como: alta variedade de produtos, volume baixo de produção e uma fábrica dividida em áreas funcionais. O problema abordado neste trabalho trata da determinação do programa de produção (scheduling) de cada lote de produtos no ambiente job shop, com a premissa de que cada produto a ser elaborado surge através de um pedido realizado pelo cliente com especificações e particularidades próprias. O objetivo do trabalho é apresentar e examinar de forma detalhada as formulações matemáticas do tipo linear inteira mista (PLIM), encontradas na literatura para o ambiente que consideram a função objetivo do makespan. Além disso, se estabelece uma nova formulação matemática que auxilia a simulação do ambiente. Todas as formulações foram comparadas através de suas dimensões e testes computacionais. Adicionalmente são apresentadas três diferentes estratégias de resolução que permitem a exploração de soluções obtidas através de diferentes metodologias. A primeira estratégia estabelece para cada instância uma solução inicial que promove uma redução do número de combinações a serem avaliadas pelo software, a segunda estratégia combina duas formulações tornando uma formulação unificada, e a terceira estratégia, estabelece um processo que utiliza duas formulações de forma consecutiva compondo um procedimento sistemático. Experimentos computacionais indicam que a formulação com melhor desempenho para o problema de job shop é a formulação de Manne (1960) por obter o melhor limitante superior (upper bound). A formulação proposta apresenta o melhor limitante inferior (lower bound). Todas as formulações melhoram seus resultados através do uso das estratégias propostas. / The operational job shop environment, represents manufacturing companies with high product variety, low volume production and an organization divided into functional areas. The problem addressed in this work determines the production schedule of each batch production, with the premise that each product results from a request made by the client with specifications and its own particularities. The main objective here is to present and to examine in detail the mathematical integer - linear program formulations (MILP) from the literature for the job shop classic environment, which considers the makespan objective. Furthermore, a new mathematical formulation is provided to help with the simulation of the environment. All the formulations were compared by mathematical dimensions and computational tests. In addition, three different strategies are presented to promote the exploration of solutions obtained from new methodologies. The first strategy defines an initial solution for each problem and promotes a reduction of the combination number to be evaluated by the software. The second strategy considers the combination of two mathematical formulations under one objective function. The third strategy establishes a procedure in which two mathematical formulations are used consecutively, creating a systematic procedure. Computational experiments demonstrate that the best formulation for the job shop problem is the Manne (1960) formulation, since it obtains the best upper bound. The proposal formulation obtains the best lower bound. All of the formulations improve their results through the use of the proposed strategies.
|
33 |
Planejamento de produção através do dimensionamento de lotes de itens únicos / Production planning by single item lot sizingOliveira, Pedro Henrique Simoes de 18 March 2011 (has links)
Este texto trata de um dos temas fundamentais no planejamento de produção, o problema de dimensionamento de lotes de um único item. Uma descrição sucinta e informal do problema segue abaixo. Considere um intervalo de tempo dividido em períodos e que a cada período de tempo está associada a demanda de um item. Dados os custos e as eventuais restrições na produção e no armazenamento, determine os períodos em que se produzirá e em que quantidade para que as demandas sejam atendidas com o menor custo possível, respeitando as restrições impostas. Apresentamos aqui resultados sobre a estrutura ótima do problema, sobre complexidade e algoritmos para os casos básicos do problema / This text studies one of the core subjects in production planning, the single-item lot-sizing problem. A brief and informal description of this problem follows below. Considering a time interval split into time periods and that there is a demand of an item associated with each time period. Given production and holding costs and possibly production and holding restrictions, determine in which periods the production must occur and in which quantity, in order to attend the demands with a minimum cost, without violate any restriction. Here, it will be shown some results about the optimal structure of the problem, about the complexity and algorithms for the simpler cases
|
34 |
Cost-Sensitive Selective Classification and its Applications to Online Fraud ManagementJanuary 2019 (has links)
abstract: Fraud is defined as the utilization of deception for illegal gain by hiding the true nature of the activity. While organizations lose around $3.7 trillion in revenue due to financial crimes and fraud worldwide, they can affect all levels of society significantly. In this dissertation, I focus on credit card fraud in online transactions. Every online transaction comes with a fraud risk and it is the merchant's liability to detect and stop fraudulent transactions. Merchants utilize various mechanisms to prevent and manage fraud such as automated fraud detection systems and manual transaction reviews by expert fraud analysts. Many proposed solutions mostly focus on fraud detection accuracy and ignore financial considerations. Also, the highly effective manual review process is overlooked. First, I propose Profit Optimizing Neural Risk Manager (PONRM), a selective classifier that (a) constitutes optimal collaboration between machine learning models and human expertise under industrial constraints, (b) is cost and profit sensitive. I suggest directions on how to characterize fraudulent behavior and assess the risk of a transaction. I show that my framework outperforms cost-sensitive and cost-insensitive baselines on three real-world merchant datasets. While PONRM is able to work with many supervised learners and obtain convincing results, utilizing probability outputs directly from the trained model itself can pose problems, especially in deep learning as softmax output is not a true uncertainty measure. This phenomenon, and the wide and rapid adoption of deep learning by practitioners brought unintended consequences in many situations such as in the infamous case of Google Photos' racist image recognition algorithm; thus, necessitated the utilization of the quantified uncertainty for each prediction. There have been recent efforts towards quantifying uncertainty in conventional deep learning methods (e.g., dropout as Bayesian approximation); however, their optimal use in decision making is often overlooked and understudied. Thus, I present a mixed-integer programming framework for selective classification called MIPSC, that investigates and combines model uncertainty and predictive mean to identify optimal classification and rejection regions. I also extend this framework to cost-sensitive settings (MIPCSC) and focus on the critical real-world problem, online fraud management and show that my approach outperforms industry standard methods significantly for online fraud management in real-world settings. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2019
|
35 |
Detecting Covert Members of Terrorist NetworksPaul, Alice 31 May 2012 (has links)
Terrorism threatens both international peace and security and is a national concern. It is believed that terrorist organizations rely heavily on a few key leaders and that destroying such an organization's leadership is essential to reducing its influence. Martonosi et al. (2011) argues that increasing the amount of communication through a key leader increases the likelihood of detection. If we model a covert organization as a social network where edges represent communication between members, we want to determine the subset of members to remove that maximizes the amount of communication through the key leader. A mixed-integer linear program representing this problem is presented as well as a decomposition for this optimization problem. As these approaches prove impractical for larger graphs, often running out of memory, the last section focuses on structural characteristics of vertices and subsets that increase communication. Future work should develop these structural properties as well as heuristics for solving this problem.
|
36 |
Performance optimization of wind turbinesZhang, Zijun 01 May 2012 (has links)
Improving performance of wind turbines through effective control strategies to reduce the power generation cost is highly desired by the wind industry. The majority of the literature on performance of wind turbines has focused on models derived from principles versed in physics. Physics-based models are usually complex and not accurate due to the fact that wind turbines involve mechanical, electrical, and software components. These components interact with each other and are subjected to variable loads introduced by the wind as well as the rotating elements of the wind turbine. Recent advances in data acquisition systems allow collection of large volumes of wind energy data. Although the prime purpose of data collection is monitoring conditions of wind turbines, the collected data offers a golden opportunity to address most challenging issues of wind turbine systems. In this dissertation, data mining is applied to construct accurate models based on the turbine collected data. To solve the data-driven models, evolutionary computation algorithms are applied. As data-driven based models are non-parametric, the evolutionary computation approach makes an ideal solution tool. Optimizing wind turbines with different objectives is studied to accomplish different research goals. Two research directions of wind turbines performance are pursued, optimizing a wind turbine performance and optimizing a wind farm performance. The goal of single wind turbine optimization is to improve wind turbine efficiency and its life-cycle. The performance optimization of a wind farm is to minimize the total cost of operating a wind farm based on the computed turbine scheduling strategies. The methodology presented in the dissertation is applicable to processes besides wind industry.
|
37 |
Network pricing problems: complexity, polyhedral study and solution approaches/Problèmes de tarification de réseaux: complexité, étude polyédrale et méthodes de résolutionHeilporn, Géraldine 14 October 2008 (has links)
Consider the problem of maximizing the revenue generated by tolls set on a subset
of arcs of a transportation network, where origin-destination flows (commodities) are assigned to shortest paths with respect to the sum of tolls and initial costs.
This thesis is concerned with a particular case of the above problem, in which all toll arcs are connected and constitute a path, as occurs on highways. Further, as toll levels are usually computed using the highway entry and exit points, a complete toll subgraph is considered, where each toll arc corresponds to a toll subpath. Two
variants of the problem are studied, with or without specific constraints linking together the tolls on the arcs.
The problem is modelled as a linear mixed integer program, and proved to be NP-hard. Next, several classes of valid inequalities are proposed, which strengthen important constraints of the initial model. Their efficiency is first shown theoretically, as these are facet defining for the restricted one and two commodity problems.
Also, we prove that some of the valid inequalities proposed, together with several
constraints of the linear program, provide a complete description of the convex hull
of feasible solutions for a single commodity problem. Numerical tests have also been conducted, and highlight the real efficiency of the valid inequalities for the multi-commodity case. Finally, we point out the links between the problem studied in the thesis and a more classical design and pricing problem in economics. /
Considérons le problème qui consiste à maximiser les profits issus de la tarification d’un sous-ensemble d’arcs d’un réseau de transport, où les flots origine-destination (produits) sont affectés aux plus courts chemins par rapport aux tarifs et aux coûts initiaux. Cette thèse porte sur une structure de réseau particulière du problème ci-dessus, dans laquelle tous les arcs tarifables sont connectés et forment un chemin,
comme c’est le cas sur une autoroute. Étant donné que les tarifs sont habituellement déterminés selon les points d’entrée et de sortie sur l’autoroute, nous considérons un sous-graphe tarifable complet, où chaque arc correspond en réalité à un sous-chemin. Deux variantes de ce problème sont étudiées, avec ou sans contraintes
spécifiques reliant les niveaux de tarifs sur les arcs.
Ce problème peut être modélisé comme un programme linéaire mixte entier. Nous prouvons qu’il est
NP-difficile. Plusieurs familles d’inégalités valides sont ensuite proposées, celles-ci renforçant certaines contraintes du modèle initial. Leur efficacité est d’abord démontrée de manière théorique, puisqu’il s’agit de facettes
des problèmes restreints à un ou deux produits. Certaines des inégalités valides proposées, ainsi que plusieurs contraintes du modèle initial, permettent aussi de donner une description complète de l’enveloppe convexe des solutions réalisables d’un problème restreint à un seul produit. Des tests numériques ont également
été menés, et mettent en évidence l’efficacité réelle des inégalités valides pour le problème général à plusieurs produits. Enfin, nous soulignons les liens entre le problème de tarification de réseau étudié dans cette thèse et un problème plus classique de tarification de produits en gestion.
|
38 |
On Models and Methods for Global Optimization of Structural TopologyStolpe, Mathias January 2003 (has links)
This thesis consists of an introduction and sevenindependent, but closely related, papers which all deal withproblems in structural optimization. In particular, we considermodels and methods for global optimization of problems intopology design of discrete and continuum structures. In the first four papers of the thesis the nonconvex problemof minimizing the weight of a truss structure subject to stressconstraints is considered. First itis shown that a certainsubclass of these problems can equivalently be cast as linearprograms and thus efficiently solved to global optimality.Thereafter, the behavior of a certain well-known perturbationtechnique is studied. It is concluded that, in practice, thistechnique can not guarantee that a global minimizer is found.Finally, a convergent continuous branch-and-bound method forglobal optimization of minimum weight problems with stress,displacement, and local buckling constraints is developed.Using this method, several problems taken from the literatureare solved with a proof of global optimality for the firsttime. The last three papers of the thesis deal with topologyoptimization of discretized continuum structures. Theseproblems are usually modeled as mixed or pure nonlinear 0-1programs. First, the behavior of certain often usedpenalization methods for minimum compliance problems isstudied. It is concluded that these methods may fail to producea zero-one solution to the considered problem. To remedy this,a material interpolation scheme based on a rational functionsuch that compli- ance becomes a concave function is proposed.Finally, it is shown that a broad range of nonlinear 0-1topology optimization problems, including stress- anddisplacement-constrained minimum weight problems, canequivalently be modeled as linear mixed 0-1 programs. Thisresult implies that any of the standard methods available forgeneral linear integer programming can now be used on topologyoptimization problems. <b>Keywords:</b>topology optimization, global optimization,stress constraints, linear programming, mixed integerprogramming, branch-and-bound.
|
39 |
Machine Learning Methods for Annual Influenza Vaccine UpdateTang, Lin 26 April 2013 (has links)
Influenza is a public health problem that causes serious illness and deaths all over the world. Vaccination has been shown to be the most effective mean to prevent infection. The primary component of influenza vaccine is the weakened strains. Vaccination triggers the immune system to develop antibodies against those strains whose viral surface glycoprotein hemagglutinin (HA) is similar to that of vaccine strains. However, influenza vaccine must be updated annually since the antigenic structure of HA is constantly mutation.
Hemagglutination inhibition (HI) assay is a laboratory procedure frequently applied to evaluate the antigenic relationships of the influenza viruses. It enables the World Health Organization (WHO) to recommend appropriate updates on strains that will most likely be protective against the circulating influenza strains. However, HI assay is labour intensive and time-consuming since it requires several controls for standardization. We use two machine-learning methods, i.e. Artificial Neural Network (ANN) and Logistic Regression, and a Mixed-Integer Optimization Model to predict antigenic variety. The ANN generalizes the input data to patterns inherent in the data, and then uses these patterns to make predictions. The logistic regression model identifies and selects the amino acid positions, which contribute most significantly to antigenic difference. The output of the logistic regression model will be used to predict the antigenic variants based on the predicted probability. The Mixed-Integer Optimization Model is formulated to find hyperplanes that enable binary classification. The performances of our models are evaluated by cross validation.
|
40 |
THREE ESSAYS ON VENDOR MANAGED INVENTORY IN SUPPLY CHAINSGumus, Mehmet January 2006 (has links)
Vendor Managed Inventory (VMI), Consignment Inventory (CI) and a combination of both (C&VMI) are supply-chain sourcing agreements between a vendor and customer. VMI allows the vendor to initiate orders on behalf of the customer. In CI, the customer pays for the goods supplied by the vendor only upon use. The vendor under C&VMI decides customer-replenishments, and owns the goods replenished until they are deployed by the customer. Our thesis studies these agreements in three essays. <br /><br /> The first essay considers a vendor <em>V</em> that manufactures a particular product at a unique location. That item is sold to a single retailer, the customer <em>C</em>. Three cases are treated in detail: Independent decision making (no agreement between the parties); VMI, whereby the supplier <em>V</em> initiates orders on behalf of <em>C</em>; and Central decision making (both Vendor and Customer are controlled by the same corporate entity). <br /><br /> Values of some cost parameters may vary between the three cases, and each case may cause a different actor to be responsible for particular expenses. Under a constant demand rate, optimal solutions are obtained analytically for the customer's order quantity, the vendor's production quantity, hence the parties' individual and total costs in the three cases. Inequalities are obtained to delineate those situations in which VMI is beneficial. <br /><br /> The problem setting in the second essay is the same with that of Essay 1, but the sourcing agreements investigated are now CI and C&VMI. In CI, as in the usual independent-sourcing approach, the customer has authority over the timing and quantity of replenishments. CI seems to favour the customer because, in addition, he pays for the goods only upon use. Under a C&VMI agreement, the vendor still owns the goods at the customer's premises, but at least can determine how much to store there. <br /><br /> The second essay thus contrasts the cases CI and C&VMI, and compares each of them to a no-agreement case. General conditions under which those cases create benefits for the vendor, the customer and the whole chain are determined. <br /><br /> Essay 3 investigates VMI and C&VMI separately for a vendor and multiple customers who face time-varying, but deterministic demand for a single product. In any of those agreements, the vendor seeks the best set of customers to achieve economies of scale. MIP models are developed to find that set of customers, and to determine the vendor's optimal production, transportation, and customer-replenishment quantities. The model for VMI is solved using a heuristic that produces two sub-models, and uses hierarchical solution approach for production, customer-replenishment and transportation decisions. C&VMI model is solved using Lagrangian relaxation. Various numerical examples are used to test the solution approaches used. <br /><br /> In the mean time, the customers can guarantee to be no worse off under VMI or C&VMI than the no-agreement case by setting the right levels of maximum inventory. A model to determine those levels and a solution algorithm are also proposed in Essay 3. <br /><br /> The first two essays can help a vendor or customer in a supply chain to determine the least costly sourcing option, which depends on the relative values of various cost parameters. A vendor with multiple customers can make use of the results in the third essay, which reveal the best possible economies of scale under VMI or C&VMI. Those customers can guarantee to be no worse of than traditional sourcing when they set the proposed levels of maximum inventory.
|
Page generated in 0.1104 seconds