Parallel algorithm for solving integer linear programs

Linear programs, or LPs, are often used in optimization problems, such as improving manufacturing efficiency of maximizing the yield from limited resources. The most common method for solving LPs is the Simplex Method, which will yield a solution, if one exists, but over the real numbers. From a purely numerical standpoint, it will be an optimal solution, but quite often we desire an optimal integer solution. A linear program in which the variables are also constrained to be integers is called an integer linear program or ILP. It is the focus of this report to present a parallel algorithm for solving ILPs. We discuss a serial algorithm using a breadth-first branch-and-bound search to check the feasible solution space, and then extend it into a parallel algorithm using a client-server model. In the parallel mode, the search may not be truly breadth-first, depending on the solution time for each node in the solution tree. Our search takes advantage of pruning, often resulting in super-linear improvements in solution time. Finally, we present results from sample ILPs, describe a few modifications to enhance the algorithm and improve solution time, and offer suggestions for future work.

Entwicklung eines Dispositionsleitstandes zur Bestimmung optimaler Torbelegungen in Stückgutspeditionsanlagen

Im operativen Betrieb einer Stückgutspeditionsanlage entscheidet der Betriebslenker bzw. der Disponent in einem ersten Schritt darüber, an welche Tore die Fahrzeuge zur Be- und Entladung andocken sollen. Darüber hinaus muss er für jede Tour ein Zeitfenster ausweisen innerhalb dessen sie das jeweilige Tor belegt. Durch die örtliche und zeitliche Fahrzeug-Tor-Zuordnung wird der für den innerbetrieblichen Umschlagprozess erforderliche Ressourcenaufwand in Form von zu fahrenden Wegstrecken oder aber Gabelstaplerstunden bestimmt. Ein Ziel der Planungsaufgabe ist somit, die Zuordnung der Fahrzeuge an die Tore so vorzunehmen, dass dabei minimale innerbetriebliche Wegstrecken entstehen. Dies führt zu einer minimalen Anzahl an benötigten Umschlagmittelressourcen. Darüber hinaus kann es aber auch zweckmäßig sein, die Fahrzeuge möglichst früh an die Tore anzudocken. Jede Tour verfügt über einen individuellen Fahrplan, der Auskunft über den Ankunftszeitpunkt sowie den Abfahrtszeitpunkt der jeweiligen Tour von der Anlage gibt. Nur innerhalb dieses Zeitfensters darf der Disponent die Tour einem der Tore zuweisen. Geschieht die Zuweisung nicht sofort nach Ankunft in der Anlage, so muss das Fahrzeug auf einer Parkfläche warten. Eine Minimierung der Wartezeiten ist wünschenswert, damit das Gelände der Anlage möglichst nicht durch zuviele Fahrzeuge gleichzeitig belastet wird. Es kann vor allem aber auch im Hinblick auf das Reservieren der Tore für zeitkritische Touren sinnvoll sein, Fahrzeuge möglichst früh abzufertigen. Am Lehrstuhl Verkehrssysteme und -logistik (VSL) der Universität Dortmund wurde die Entscheidungssituation im Rahmen eines Forschungsprojekts bei der Stiftung Industrieforschung in Anlehnung an ein zeitdiskretes Mehrgüterflussproblem mit unsplittable flow Bedingungen modelliert. Die beiden Zielsetzungen wurden dabei in einer eindimensionalen Zielfunktion integriert. Das resultierende Mixed Integer Linear Programm (MILP) wurde programmiert und für mittlere Szenarien durch Eingabe in den Optimization Solver CPlex mit dem dort implementierten exakten Branch-and-Cut Verfahren gelöst. Parallel wurde im Rahmen einer Kooperation zwischen dem Lehrstuhl VSL und dem Unternehmen hafa Docking Systems, einem der weltweit führenden Tor und Rampenhersteller, für die gleiche Planungsaufgabe ein heuristisches Scheduling Verfahren sowie ein Dispositionsleitstand namens LoadDock Navigation entwickelt. Der Dispositionsleitstand dient der optimalen Steuerung der Torbelegungen in logistischen Anlagen. In dem Leitstand wird planerische Intelligenz in Form des heuristischen Schedulingverfahrens, technische Neuerungen in der Rampentechnik in Form von Sensoren und das Expertenwissen des Disponenten in einem Tool verbunden. Das mathematische Modell sowie der Prototyp mit der integrierten Heuristik werden im Rahmen dieses Artikels vorgestellt.

GRASP with Hybrid Path Relinking for Bi-Objective Winner Determination in Combinatorial Transportation Auctions

The procurement of transportation services via large-scale combinatorial auctions involves a couple of complex decisions whose outcome highly influences the performance of the tender process. This paper examines the shipper's task of selecting a subset of the submitted bids which efficiently trades off total procurement cost against expected carrier performance. To solve this bi-objective winner determination problem, we propose a Pareto-based greedy randomized adaptive search procedure (GRASP). As a post-optimizer we use a path relinking procedure which is hybridized with branch-and-bound. Several variants of this algorithm are evaluated by means of artificial test instances which comply with important real-world characteristics. The two best variants prove superior to a previously published Pareto-based evolutionary algorithm.

A Column-Generation Approach for a Short-Term Production Planning Problem in Closed-Loop Supply Chains

We present a new model formulation for a multi-product lot-sizing problem with product returns and remanufacturing subject to a capacity constraint. The given external demand of the products has to be satisfied by remanufactured or newly produced goods. The objective is to determine a feasible production plan, which minimizes production, holding, and setup costs. As the LP relaxation of a model formulation based on the well-known CLSP leads to very poor lower bounds, we propose a column-generation approach to determine tighter bounds. The lower bound obtained by column generation can be easily transferred into a feasible solution by a truncated branch-and-bound approach using CPLEX. The results of an extensive numerical study show the high solution quality of the proposed solution approach.

Purchase decision-making is modulated by vestibular stimulation

Purchases are driven by consumers’ product preferences and price considerations. Using caloric vestibular stimulation (CVS), we investigated the role of vestibular-affective circuits in purchase decision-making. CVS is an effective noninvasive brain stimulation method, which activates vestibular and overlapping emotional circuits (e.g., the insular cortex and the anterior cingulate cortex (ACC)). Subjects were exposed to CVS and sham stimulation while they performed two purchase decision-making tasks. In Experiment 1 subjects had to decide whether to purchase or not. CVS significantly reduced probability of buying a product. In Experiment 2 subjects had to rate desirability of the products and willingness to pay (WTP) while they were exposed to CVS and sham stimulation. CVS modulated desirability of the products but not WTP. The results suggest that CVS interfered with emotional circuits and thus attenuated the pleasant and rewarding effect of acquisition, which in turn reduced purchase probability. The present findings contribute to the rapidly growing literature on the neural basis of purchase decision-making.

Respuesta fotoperiódica en Origanum vulgare ssp. vulgare y ssp. hirtum Ietsw. : impacto sobre su desarrollo y crecimiento

La productividad del orégano (Origanum vulgare L.) está determinada por la conjunción entre cantidad de biomasa acumulada y contenido de aceite esencial hasta el momento de su cosecha. Numerosos autores han constatado que dicho contenido es máximo al momento de floración pero los procesos que determinan la ocurrencia de la misma son poco claros en esta especie. A través de la prolongación artificial del fotoperíodo, se evaluó la sensibilidad fotoperiódica de dos subespecies tradicionales de orégano (Compacto: Origanum vulgare ssp. vulgare y Criollo: Origanum vulgare ssp. hirtum Ietsw.) y su incidencia en el desarrollo, duración de fases fenológicas y en la dinámica de crecimiento. Se encontró que ambas responden al aumento del fotoperíodo reduciendo la longitud de su ciclo. Ante estas condiciones, las mismas difirieron en la magnitud de su respuesta, siendo la subespecie Criollo más sensible que Compacto. Esto sugiere que el umbral fotoperiódico de inducción a floración es menor en el orégano Criollo que en el orégano Compacto. El acortamiento de la fase de desarrollo vegetativo en ambas subespecies generó menor número de nudos y longitud de ramas finales (disminución más notoria en la subespecie Criollo). El fotoperíodo extendido generó un cambio en el modelo de crecimiento de la longitud de ramas de lineal a lineal con meseta o cuadrático.

Aceptación de aceite transgénico de distinto país de origen en la Región de La Araucanía, Chile

Considerando el rechazo de los consumidores hacia alimentos genéticamente modificados y que el país de origen es usado como indicador de calidad, se estudió la importancia relativa de la existencia de modificación genética (MG), origen y precio en la compra de aceite de girasol en Temuco, Chile, junto con la identificación y la caracterización de diferentes segmentos de mercado, mediante una encuesta a 400 personas. Utilizando análisis conjunto se determinó que la existencia de MG (36,0%) fue levemente más importante que el origen (33,3%) y el precio (30,7%) en la muestra total, con preferencia hacia el producto sin MG, de origen chileno y al menor precio. Mediante análisis de conglomerados jerárquicos se diferenciaron tres segmentos: el mayoritario (45,5%) dio elevada importancia a la existencia de MG y presentó un alto rechazo hacia el aceite transgénico; el segundo grupo (29,7%) asignó mayor relevancia al precio y acepta aceite argentino; el grupo minoritario (24,8%) otorgó mayor importancia al origen y acepta aceite español. Independientemente de lo anterior, los grupos mostraron mayor preferencia por el aceite chileno. La ausencia de MG en aceite es una condición deseable para una importante proporción de consumidores (45,5%), pero el resto se muestra relativamente indiferente hacia la existencia o ausencia de manipulación genética en este producto.

Energía geotérmica de baja entalpía

El actual aumento de concentraciones de gases de efecto invernadero, el agotamiento y encarecimiento de combustibles fósiles, y el cuidado del ambiente, son los motivos principales por los cuales el uso de las energías a partir de fuentes renovables está incrementando. La energía geotérmica es un tipo de energía potencialmente renovable. La misma presenta varias tipologías, siendo la de baja entalpía la que posee mayor disponibilidad en todo el mundo. Este tipo de energía se puede utilizar para climatizar ambientes, durante todo el año, debido a la estabilidad térmica que la misma brinda. Se ha realizado un análisis del recurso presente en los primeros metros de profundidad de suelo, bajo determinadas condiciones externas y de extracción, y dentro de estas circunstancias se obtuvieron datos de temperatura de suelo, y de aire (tanto arriba como debajo de la tierra), los cuales, luego de ser estudiados, fueron comprobados matemáticamente y pudieron brindar un ábaco que sirve como herramienta para ser utilizado en distintos aprovechamientos utilizando el prototipo elaborado, pudiendo reflejar en la realidad práctica las investigaciones realizadas.

Instituciones, población y mercados de tierra locales en perspectiva comparada. Los ejidos y colonias agrícolas de Chascomús y Junín [Buenos Aires, Argentina], 1860-1914

El objetivo de esta ponencia es analizar el funcionamiento del mercado de tierras privadas ejidales y de colonias cuando la provincia de Buenos Aires estaba impulsando la mayor expansión territorial del siglo y recibía un importante flujo de inmigrantes, entre 1860 y la primera guerra mundial. Enfocaremos nuestra indagación en los partidos de Chascomús y Junín. Ya hemos estudiado el mercado de tierras de campos y estancias en los partidos elegidos y también hemos comparado esos datos con el único trabajo que se ocupa de un ejido en la provincia (Mercedes), cuyos resultados nos indican un comportamiento diferente en los actores y en la conformación del mercado, nos parece pertinente estudiar el impacto que tuvieron en las transacciones y en la formación del precio el crecimiento demográfico, los cambios institucionales, las políticas públicas sobre tierras (especialmente las relacionadas con las colonias y la expansión de los ejidos). De esta manera podremos estimar las interrelaciones entre los mercados en campos de grandes dimensiones y los más reducidos de los ejidos y colonias

Instituciones, población y mercados de tierra locales en perspectiva comparada. Los ejidos y colonias agrícolas de Chascomús y Junín [Buenos Aires, Argentina], 1860-1914

El objetivo de esta ponencia es analizar el funcionamiento del mercado de tierras privadas ejidales y de colonias cuando la provincia de Buenos Aires estaba impulsando la mayor expansión territorial del siglo y recibía un importante flujo de inmigrantes, entre 1860 y la primera guerra mundial. Enfocaremos nuestra indagación en los partidos de Chascomús y Junín. Ya hemos estudiado el mercado de tierras de campos y estancias en los partidos elegidos y también hemos comparado esos datos con el único trabajo que se ocupa de un ejido en la provincia (Mercedes), cuyos resultados nos indican un comportamiento diferente en los actores y en la conformación del mercado, nos parece pertinente estudiar el impacto que tuvieron en las transacciones y en la formación del precio el crecimiento demográfico, los cambios institucionales, las políticas públicas sobre tierras (especialmente las relacionadas con las colonias y la expansión de los ejidos). De esta manera podremos estimar las interrelaciones entre los mercados en campos de grandes dimensiones y los más reducidos de los ejidos y colonias

Instituciones, población y mercados de tierra locales en perspectiva comparada. Los ejidos y colonias agrícolas de Chascomús y Junín [Buenos Aires, Argentina], 1860-1914

El objetivo de esta ponencia es analizar el funcionamiento del mercado de tierras privadas ejidales y de colonias cuando la provincia de Buenos Aires estaba impulsando la mayor expansión territorial del siglo y recibía un importante flujo de inmigrantes, entre 1860 y la primera guerra mundial. Enfocaremos nuestra indagación en los partidos de Chascomús y Junín. Ya hemos estudiado el mercado de tierras de campos y estancias en los partidos elegidos y también hemos comparado esos datos con el único trabajo que se ocupa de un ejido en la provincia (Mercedes), cuyos resultados nos indican un comportamiento diferente en los actores y en la conformación del mercado, nos parece pertinente estudiar el impacto que tuvieron en las transacciones y en la formación del precio el crecimiento demográfico, los cambios institucionales, las políticas públicas sobre tierras (especialmente las relacionadas con las colonias y la expansión de los ejidos). De esta manera podremos estimar las interrelaciones entre los mercados en campos de grandes dimensiones y los más reducidos de los ejidos y colonias

Chapter 5 Product Differentiation versus Geographical Differentiation: Evidence from the Pork Processing Industry in China

This chapter attempts to identify whether product differentiation or geographical differentiation is the main source of profit for firms in developing economies by employing a simple idea from the recently developed method of empirical industrial organization. Theoretically, location choice and product choice have been considered as analogues in differentiation, but in the real world, which of these strategies is chosen will result in an immense difference in firm behavior and in the development process of the industry. Development of the technique of empirical industrial organization enabled us to identify market outcomes with endogeneity. A typical case is the market outcome with differentiation, where price or product choice is endogenously determined. Our original survey contains data on market location, differences in product types, and price. The results show that product differentiation rather than geographical differentiation mitigates pressure on price competition, but 70 per cent secures geographical monopoly.

Competition of the mechanisms : how Chinese home appliance firms coped with default risk of trade credit?

During the transition period from a planned economy to a market economy in 1990s of China, there was a considerable accrual of deferred payment, and default due to inferior enforcement institutions. This is a very common phenomenon in the transition economies at that time. Interviews with home electronics appliance firms revealed that firms coped with this problem by adjusting their sales mechanisms (found four types), and the benefit of institutions was limited. A theoretical analysis claim that spot and integration are inferior to contracts, a contract with a rebate on volume and prepayment against an exclusive agent can realize the lowest cost and price. The empirical part showed that mechanisms converged into a mechanism with the rebate on volume an against exclusive agent and its price level is the lowest. The competition is the driving force of the convergence of mechanisms and improvement risk management capacity.

Quasi-experimental evidence on the drivers of index-based livestock insurance demand in Southern Ethiopia

Microinsurance is widely considered an important tool for sustainable poverty reduction, especially in the face of increasing climate risk. Although index-based microinsurance, which should be free from the classical incentive problems, has attracted considerable attention, uptake rates have generally been weak in low-income rural communities. We explore the purchase patterns of index-based livestock insurance in southern Ethiopia, focusing in particular on the role of accurate product comprehension and price, including the prospective impact of temporary discount coupons on subsequent period demand due to price anchoring effects. We find that randomly distributed learning kits contribute to improving subjects' knowledge of the products; however, we do not find strong evidence that the improved knowledge per se induces greater uptake. We also find that reduced price due to randomly distributed discount coupons has an immediate, positive impact on uptake, without dampening subsequent period demand due to reference-dependence associated with price anchoring effects.

Evaluation of the trading development in the Iberian Energy Derivatives Market

The efficiency of the Iberian Energy Derivatives Market in its first five and a half years is assessed in terms of volume, open interest and price. The continuous market shows steady liquidity growth. Its volume is strongly correlated to that of the Over The Counter (OTC) market, the amount of market makers, the enrolment of financial agents and generation companies belonging to the integrated group of last resort suppliers, and the OTC cleared volume in its clearing house. The hedging efficiency, measured through the ratio between the final open interest and the cleared volume, shows the lowest values for the Spanish base load futures as they are the most liquid contracts. The ex-post forward risk premium has diminished due to the learning curve and the effect of the fixed price retributing the indigenous coal fired generation. This market is quite less developed than the European leaders headquartered in Norway and Germany. Enrolment of more traders, mainly international energy companies, financial agents, energy intensive industries and renewable generation companies is desired. Market monitoring reports by the market operator providing post-trade transparency, OTC data access by the energy regulator, and assessment of the regulatory risk can contribute to efficiency gains.