Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths

This paper deals with the classical one-dimensional integer cutting stock problem, which consists of cutting a set of available stock lengths in order to produce smaller ordered items. This process is carried out in order to optimize a given objective function (e.g., minimizing waste). Our study deals with a case in which there are several stock lengths available in limited quantities. Moreover, we have focused on problems of low demand. Some heuristic methods are proposed in order to obtain an integer solution and compared with others. The heuristic methods are empirically analyzed by solving a set of randomly generated instances and a set of instances from the literature. Concerning the latter. most of the optimal solutions of these instances are known, therefore it was possible to compare the solutions. The proposed methods presented very small objective function value gaps. (C) 2008 Elsevier Ltd. All rights reserved.

Computational study of the step size parameter of the subgradient optimization method

The subgradient optimization method is a simple and flexible linear programming iterative algorithm. It is much simpler than Newton's method and can be applied to a wider variety of problems. It also converges when the objective function is non-differentiable. Since an efficient algorithm will not only produce a good solution but also take less computing time, we always prefer a simpler algorithm with high quality. In this study a series of step size parameters in the subgradient equation is studied. The performance is compared for a general piecewise function and a specific p-median problem. We examine how the quality of solution changes by setting five forms of step size parameter.

On statistical bounds of heuristic solutions to location problems

Solutions to combinatorial optimization problems, such as problems of locating facilities, frequently rely on heuristics to minimize the objective function. The optimum is sought iteratively and a criterion is needed to decide when the procedure (almost) attains it. Pre-setting the number of iterations dominates in OR applications, which implies that the quality of the solution cannot be ascertained. A small, almost dormant, branch of the literature suggests using statistical principles to estimate the minimum and its bounds as a tool to decide upon stopping and evaluating the quality of the solution. In this paper we examine the functioning of statistical bounds obtained from four different estimators by using simulated annealing on p-median test problems taken from Beasley’s OR-library. We find the Weibull estimator and the 2nd order Jackknife estimator preferable and the requirement of sample size to be about 10 being much less than the current recommendation. However, reliable statistical bounds are found to depend critically on a sample of heuristic solutions of high quality and we give a simple statistic useful for checking the quality. We end the paper with an illustration on using statistical bounds in a problem of locating some 70 distribution centers of the Swedish Post in one Swedish region. 

A stopping rule while searching for optimal solution of facility-location

Solutions to combinatorial optimization, such as p-median problems of locating facilities, frequently rely on heuristics to minimize the objective function. The minimum is sought iteratively and a criterion is needed to decide when the procedure (almost) attains it. However, pre-setting the number of iterations dominates in OR applications, which implies that the quality of the solution cannot be ascertained. A small branch of the literature suggests using statistical principles to estimate the minimum and use the estimate for either stopping or evaluating the quality of the solution. In this paper we use test-problems taken from Baesley's OR-library and apply Simulated Annealing on these p-median problems. We do this for the purpose of comparing suggested methods of minimum estimation and, eventually, provide a recommendation for practioners. An illustration ends the paper being a problem of locating some 70 distribution centers of the Swedish Post in a region.

Confidence in heuristic solutions?

Solutions to combinatorial optimization problems frequently rely on heuristics to minimize an objective function. The optimum is sought iteratively and pre-setting the number of iterations dominates in operations research applications, which implies that the quality of the solution cannot be ascertained. Deterministic bounds offer a mean of ascertaining the quality, but such bounds are available for only a limited number of heuristics and the length of the interval may be difficult to control in an application. A small, almost dormant, branch of the literature suggests using statistical principles to derive statistical bounds for the optimum. We discuss alternative approaches to derive statistical bounds. We also assess their performance by testing them on 40 test p-median problems on facility location, taken from Beasley’s OR-library, for which the optimum is known. We consider three popular heuristics for solving such location problems; simulated annealing, vertex substitution, and Lagrangian relaxation where only the last offers deterministic bounds. Moreover, we illustrate statistical bounds in the location of 71 regional delivery points of the Swedish Post. We find statistical bounds reliable and much more efficient than deterministic bounds provided that the heuristic solutions are sampled close to the optimum. Statistical bounds are also found computationally affordable.

A pharmacokinetic-pharmacodynamic model for duodenal levodopa infusion

Objective Levodopa in presence of decarboxylase inhibitors is following two-compartment kinetics and its effect is typically modelled using sigmoid Emax models. Pharmacokinetic modelling of the absorption phase of oral distributions is problematic because of irregular gastric emptying. The purpose of this work was to identify and estimate a population pharmacokinetic- pharmacodynamic model for duodenal infusion of levodopa/carbidopa (Duodopa®) that can be used for in numero simulation of treatment strategies. Methods The modelling involved pooling data from two studies and fixing some parameters to values found in literature (Chan et al. J Pharmacokinet Pharmacodyn. 2005 Aug;32(3-4):307-31). The first study involved 12 patients on 3 occasions and is described in Nyholm et al. Clinical Neuropharmacology 2003:26:156-63. The second study, PEDAL, involved 3 patients on 2 occasions. A bolus dose (normal morning dose plus 50%) was given after a washout during night. Plasma samples and motor ratings (clinical assessment of motor function from video recordings on a treatment response scale between -3 and 3, where -3 represents severe parkinsonism and 3 represents severe dyskinesia.) were repeatedly collected until the clinical effect was back at baseline. At this point, the usual infusion rate was started and sampling continued for another two hours. Different structural absorption models and effect models were evaluated using the value of the objective function in the NONMEM package. Population mean parameter values, standard error of estimates (SE) and if possible, interindividual/interoccasion variability (IIV/IOV) were estimated. Results Our results indicate that Duodopa absorption can be modelled with an absorption compartment with an added bioavailability fraction and a lag time. The most successful effect model was of sigmoid Emax type with a steep Hill coefficient and an effect compartment delay. Estimated parameter values are presented in the table. Conclusions The absorption and effect models were reasonably successful in fitting observed data and can be used in simulation experiments.

An empirical test of the gravity p-median model

A customer is presumed to gravitate to a facility by the distance to it and the attractiveness of it. However regarding the location of the facility, the presumption is that the customer opts for the shortest route to the nearest facility.This paradox was recently solved by the introduction of the gravity p-median model. The model is yet to be implemented and tested empirically. We implemented the model in an empirical problem of locating locksmiths, vehicle inspections, and retail stores ofv ehicle spare-parts, and we compared the solutions with those of the p-median model. We found the gravity p-median model to be of limited use for the problem of locating facilities as it either gives solutions similar to the p-median model, or it gives unstable solutions due to a non-concave objective function.

Testing the gravity p-median model empirically

Regarding the location of a facility, the presumption in the widely used p-median model is that the customer opts for the shortest route to the nearest facility. However, this assumption is problematic on free markets since the customer is presumed to gravitate to a facility by the distance to and the attractiveness of it. The recently introduced gravity p-median model offers an extension to the p-median model that account for this. The model is therefore potentially interesting, although it has not yet been implemented and tested empirically. In this paper, we have implemented the model in an empirical problem of locating vehicle inspections, locksmiths, and retail stores of vehicle spare-parts for the purpose of investigating its superiority to the p-median model. We found, however, the gravity p-median model to be of limited use for the problem of locating facilities as it either gives solutions similar to the p-median model, or it gives unstable solutions due to a non-concave objective function.

The polictical economy informed lobbies

We analize a discrete type version of a common agency model with informed principals of Martimort and Moreira (2005) in the context of lobby games. We begin discussing issues related to the common values nature of the model, i.e.the agent cares directly about the principal’s utility function. With this feature the equilibrium of Martimort and Moreira (2005) is not valid. We argue in favor of one solution, although we are not able to fully characterize the equilibrium in this context. We then turn to an application: a modification of the Grossman and Helpman (1994) model of lobbying for tariff protection to incoporate assimetric information (but disconsidering the problem of common values) in the lobbies objective function. We show that the main results of the original model do not hold and that lobbies may behave less agressively towards the police maker when there is private information in the lobbies valuation for the tariffs.

Essays on asymmetric information problems without the single-crossing property: applications to corporate finance

The objective of this dissertation is to re-examine classical issues in corporate finance, applying a new analytical tool. The single-crossing property, also called Spence-irrlees condition, is not required in the models developed here. This property has been a standard assumption in adverse selection and signaling models developed so far. The classical papers by Guesnerie and Laffont (1984) and Riley (1979) assume it. In the simplest case, for a consumer with a privately known taste, the single-crossing property states that the marginal utility of a good is monotone with respect to the taste. This assumption has an important consequence to the result of the model: the relationship between the private parameter and the quantity of the good assigned to the agent is monotone. While single crossing is a reasonable property for the utility of an ordinary consumer, this property is frequently absent in the objective function of the agents for more elaborate models. The lack of a characterization for the non-single crossing context has hindered the exploration of models that generate objective functions without this property. The first work that characterizes the optimal contract without the single-crossing property is Araújo and Moreira (2001a) and, for the competitive case, Araújo and Moreira (2001b). The main implication is that a partial separation of types may be observed. Two sets of disconnected types of agents may choose the same contract, in adverse selection problems, or signal with the same levei of signal, in signaling models.

Dinâmica monetária eficiente sob encontros aleatórios: uma classe de métodos numéricos que exploram concavidade

A dificuldade em se caracterizar alocações ou equilíbrios não estacionários é uma das principais explicações para a utilização de conceitos e hipóteses que trivializam a dinâmica da economia. Tal dificuldade é especialmente crítica em Teoria Monetária, em que a dimensionalidade do problema é alta mesmo para modelos muito simples. Neste contexto, o presente trabalho relata a estratégia computacional de implementação do método recursivo proposto por Monteiro e Cavalcanti (2006), o qual permite calcular a sequência ótima (possivelmente não estacionária) de distribuições de moeda em uma extensão do modelo proposto por Kiyotaki e Wright (1989). Três aspectos deste cálculo são enfatizados: (i) a implementação computacional do problema do planejador envolve a escolha de variáveis contínuas e discretas que maximizem uma função não linear e satisfaçam restrições não lineares; (ii) a função objetivo deste problema não é côncava e as restrições não são convexas; e (iii) o conjunto de escolhas admissíveis não é conhecido a priori. O objetivo é documentar as dificuldades envolvidas, as soluções propostas e os métodos e recursos disponíveis para a implementação numérica da caracterização da dinâmica monetária eficiente sob a hipótese de encontros aleatórios.

Regras monetárias e dinâmica macroeconômica no Brasil: uma abordagem de expectativas racionais

Neste artigo estimamos e simulamos um modelo macroeconômico aberto de expectativas racionais (Batini e Haldane [4]) para a economia brasileira, com o objetivo de identificar as características das regras monetárias ótimas e a dinâmica de curto prazo gerada por elas. Trabalhamos com uma versão forward-Iooking e uma versão backward-Iooking a fim de comparar o desempenho de três parametrizações de regras monetárias, que diferem em relação à variável de inflação: a tradicional regra de Taylor, que se baseia na inflação passada; uma regra que combina inflação e taxa de câmbio real (ver Ball [5]) e uma regra que utiliza previsões de inflação (ver Bank af England [3]). Resolvemos o modelo numericamente e contruímos fronteiras eficientes em relação às variâncias do produto e da infiação por simulações estocásticas, para choques i.i.d. ou correlacionados. Os conjuntos de regras ótimas para as duas versões são qualitativamente distintos. Devido à incerteza quanto ao grau de forward-Iookingness sugerimos a escolha das regras pela soma das funções objetivos nas duas versões. Concluímos que as regras escolhidas com base neste critério têm perdas moderadas em relação às regras ótimas, mas previnem perdas maiores que resultariam da escolha da regra com base na versão errada. Finalmente calculamos funções de resposta a impulso dos dois modelos para algumas regras selecionadas, a fim de avaliar como diferentes regras monetárias alteram a dinâmica de curto prazo dos dois modelos.

Otimização de alavancagem e gestão de risco em estratégias long-short

Alavancagem em hedge funds tem preocupado investidores e estudiosos nos últimos anos. Exemplos recentes de estratégias desse tipo se mostraram vantajosos em períodos de pouca incerteza na economia, porém desastrosos em épocas de crise. No campo das finanças quantitativas, tem-se procurado encontrar o nível de alavancagem que otimize o retorno de um investimento dado o risco que se corre. Na literatura, os estudos têm se mostrado mais qualitativos do que quantitativos e pouco se tem usado de métodos computacionais para encontrar uma solução. Uma forma de avaliar se alguma estratégia de alavancagem aufere ganhos superiores do que outra é definir uma função objetivo que relacione risco e retorno para cada estratégia, encontrar as restrições do problema e resolvê-lo numericamente por meio de simulações de Monte Carlo. A presente dissertação adotou esta abordagem para tratar o investimento em uma estratégia long-short em um fundo de investimento de ações em diferentes cenários: diferentes formas de alavancagem, dinâmicas de preço das ações e níveis de correlação entre esses preços. Foram feitas simulações da dinâmica do capital investido em função das mudanças dos preços das ações ao longo do tempo. Considerou-se alguns critérios de garantia de crédito, assim como a possibilidade de compra e venda de ações durante o período de investimento e o perfil de risco do investidor. Finalmente, estudou-se a distribuição do retorno do investimento para diferentes níveis de alavancagem e foi possível quantificar qual desses níveis é mais vantajoso para a estratégia de investimento dadas as restrições de risco.

Does liquidity constraints matter for Ricardian equivalence?

The paper analysis a general equilibrium model with two periods, several households and a government that has to finance some expenditures in the first period. Households may have some private information either about their type (adverse selection) or about some action levei chosen in the first period that affects the probability of certain states of nature in the second period (moral hazard). Trade of financiai assets are intermediated by a finite collection of banks. Banks objective functions are determined in equilibrium by shareholders. Due to private information it may be optimal for the banks to introduce constraints in the set of available portfolios for each household as wellas household specific asset prices. In particular, households may face distinct interest rates for holding the risk-free asset. The government finances its expenditures either by taxing households in the first period or by issuing bonds in the first period and taxing households in the second period. Taxes may be state-dependent. Suppose government policies are neutml: i) government policies do not affect the distribution of wealth across households; and ii) if the government decides to tax a household in the second period there is a portfolio available for the banks that generates the Mme payoff in each state of nature as the household taxes. Tben, Ricardian equivalence holds if and only if an appropriate boundary condition is satisfied. Moreover, at every free-entry equilibrium the boundary condition is satisfied and thus Ricardian equivalence holds. These results do not require any particular assumption on the banks' objective function. In particular, we do not assume banks to be risk neutral.

Ensaios sobre mercados artificiais com dois ativos utilizando algoritmos genéticos

A abordagem de Modelos Baseados em Agentes é utilizada para trabalhar problemas complexos, em que se busca obter resultados partindo da análise e construção de componentes e das interações entre si. Os resultados observados a partir das simulações são agregados da combinação entre ações e interferências que ocorrem no nível microscópico do modelo. Conduzindo, desta forma, a uma simulação do micro para o macro. Os mercados financeiros são sistemas perfeitos para o uso destes modelos por preencherem a todos os seus requisitos. Este trabalho implementa um Modelo de Mercado Financeiro Baseado em Agentes constituído por diversos agentes que interagem entre si através de um Núcleo de Negociação que atua com dois ativos e conta com o auxílio de formadores de mercado para promover a liquidez dos mercados, conforme se verifica em mercados reais. Para operação deste modelo, foram desenvolvidos dois tipos de agentes que administram, simultaneamente, carteiras com os dois ativos. O primeiro tipo usa o modelo de Markowitz, enquanto o segundo usa técnicas de análise de spread entre ativos. Outra contribuição deste modelo é a análise sobre o uso de função objetivo sobre os retornos dos ativos, no lugar das análises sobre os preços.