Algebraic duality theorems for infinite LP problems

In this paper we consider a primal-dual infinite linear programming problem-pair, i.e. LPs on infinite dimensional spaces with infinitely many constraints. We present two duality theorems for the problem-pair: a weak and a strong duality theorem. We do not assume any topology on the vector spaces, therefore our results are algebraic duality theorems. As an application, we consider transferable utility cooperative games with arbitrarily many players.

A nettó jelenérték maximalizálása erőforrás-korlátos projektekben - egy új harmóniakereső metaheurisztika (A harmony search metaheuristic for the resourceconstrained project scheduling problem with discounted cash flows)

Ebben a tanulmányban a szerző egy új harmóniakereső metaheurisztikát mutat be, amely a minimális időtartamú erőforrás-korlátos ütemezések halmazán a projekt nettó jelenértékét maximalizálja. Az optimális ütemezés elméletileg két egész értékű (nulla-egy típusú) programozási feladat megoldását jelenti, ahol az első lépésben meghatározzuk a minimális időtartamú erőforrás-korlátos ütemezések időtartamát, majd a második lépésben az optimális időtartamot feltételként kezelve megoldjuk a nettó jelenérték maximalizálási problémát minimális időtartamú erőforrás-korlátos ütemezések halmazán. A probléma NP-hard jellege miatt az egzakt megoldás elfogadható idő alatt csak kisméretű projektek esetében képzelhető el. A bemutatandó metaheurisztika a Csébfalvi (2007) által a minimális időtartamú erőforrás-korlátos ütemezések időtartamának meghatározására és a tevékenységek ennek megfelelő ütemezésére kifejlesztett harmóniakereső metaheurisztika továbbfejlesztése, amely az erőforrás-felhasználási konfliktusokat elsőbbségi kapcsolatok beépítésével oldja fel. Az ajánlott metaheurisztika hatékonyságának és életképességének szemléltetésére számítási eredményeket adunk a jól ismert és népszerű PSPLIB tesztkönyvtár J30 részhalmazán futtatva. Az egzakt megoldás generálásához egy korszerű MILP-szoftvert (CPLEX) alkalmaztunk. _______________ This paper presents a harmony search metaheuristic for the resource-constrained project scheduling problem with discounted cash flows. In the proposed approach, a resource-constrained project is characterized by its „best” schedule, where best means a makespan minimal resource constrained schedule for which the net present value (NPV) measure is maximal. Theoretically the optimal schedule searching process is formulated as a twophase mixed integer linear programming (MILP) problem, which can be solved for small-scale projects in reasonable time. The applied metaheuristic is based on the "conflict repairing" version of the "Sounds of Silence" harmony search metaheuristic developed by Csébfalvi (2007) for the resource-constrained project scheduling problem (RCPSP). In order to illustrate the essence and viability of the proposed harmony search metaheuristic, we present computational results for a J30 subset from the well-known and popular PSPLIB. To generate the exact solutions a state-of-the-art MILP solver (CPLEX) was used.

Általános egyensúlyi modellek alkalmazása gazdaságpolitikai elemzésekre (Application of general equilibrium models to economic policy analyses)

A szerző az alkalmazott többszektoros modellezés területén a lineáris programozási modellektől a számszerűsített általános egyensúlyi modellekig végbement változásokat tekinti át. Egy rövid történeti visszapillantás után a lineáris programozás módszereire épülő nemzetgazdasági szintű modellekkel összevetve mutatja be az általános egyensúlyi modellek közös, illetve eltérő jellemzőit. Egyidejűleg azt is érzékelteti, hogyan lehet az általános egyensúlyi modelleket a gazdaságpolitikai célok konzisztenciájának, a célok közötti átváltási lehetőségek elemzésére és általában a gazdaságpolitikai elképzelések érzékenységi vizsgálatára felhasználni. A szerző az elméleti-módszertani kérdések taglalását számszerűsített általános egyensúlyi modell segítségével illusztrálja. _______ The author surveys the changes having taken place in the field of multi-sector modeling, from the linear programming models to the quantified general equilibrium models. After a brief historical retrospection he presents the common and different characteristic features of the general equilibrium models by comparing them with the national economic level models based on the methods of linear programming. He also makes clear how the general equilibrium models can be used for analysing the consistency of economic policy targets, for the investigation of trade-off possibilities among the targets and, in general, for sensitivity analyses of economic policy targets. The discussion of theoretical and methodological quuestions is illustrated by the author with the aid of a quantified general equilibrium model.

Economic reform, allocative effiency and terms of trade

It has widely been agreed that the distorted price system is one of the causes of inefficient ecooomic decisions in centrally planned economies. The paper investigates the possible effect of a price reform on the allocation of resources in a situation where micro-efficiency remains unchanged. Foreign trade and endogenously induced terms-of-trade changes are focal points ín the multisectoral applied general equilibrium analysis. Special attention is paid to some methodological problems connected to the representation of foreign trade in such models. The adoption of Armington's assumption leads to an export demand function and this in turn gives rise to the question of optimal export structure, different from the equilibrium one-an aspect so far neglected in the related literature. The results show, that the applied model allows for a more flexible handling of the overspecialization problem, than the linear programming models. It also becomes evident that the use of export demand functions brings unwanted terms-of-trade changes into the model, to be avoided by a suitable reformulation of the model. The analysis also suggests, that a price reform alone does not significantly increase global economic efficiency. Thus the effect of an economic reform on micro-efficiency appears to be a more crucial factor. The author raises in conclusion some rather general questions related to the foreign trade practice of small open economies.

System design and resource management in the next-generation integrated WLAN and 3G cellular networks

Next-generation integrated wireless local area network (WLAN) and 3G cellular networks aim to take advantage of the roaming ability in a cellular network and the high data rate services of a WLAN. To ensure successful implementation of an integrated network, many issues must be carefully addressed, including network architecture design, resource management, quality-of-service (QoS), call admission control (CAC) and mobility management. ^ This dissertation focuses on QoS provisioning, CAC, and the network architecture design in the integration of WLANs and cellular networks. First, a new scheduling algorithm and a call admission control mechanism in IEEE 802.11 WLAN are presented to support multimedia services with QoS provisioning. The proposed scheduling algorithms make use of the idle system time to reduce the average packet loss of realtime (RT) services. The admission control mechanism provides long-term transmission quality for both RT and NRT services by ensuring the packet loss ratio for RT services and the throughput for non-real-time (NRT) services. ^ A joint CAC scheme is proposed to efficiently balance traffic load in the integrated environment. A channel searching and replacement algorithm (CSR) is developed to relieve traffic congestion in the cellular network by using idle channels in the WLAN. The CSR is optimized to minimize the system cost in terms of the blocking probability in the interworking environment. Specifically, it is proved that there exists an optimal admission probability for passive handoffs that minimizes the total system cost. Also, a method of searching the probability is designed based on linear-programming techniques. ^ Finally, a new integration architecture, Hybrid Coupling with Radio Access System (HCRAS), is proposed for lowering the average cost of intersystem communication (IC) and the vertical handoff latency. An analytical model is presented to evaluate the system performance of the HCRAS in terms of the intersystem communication cost function and the handoff cost function. Based on this model, an algorithm is designed to determine the optimal route for each intersystem communication. Additionally, a fast handoff algorithm is developed to reduce the vertical handoff latency.^

The order selection and lot sizing problem in the make-to-order environment

This research is motivated by the need for considering lot sizing while accepting customer orders in a make-to-order (MTO) environment, in which each customer order must be delivered by its due date. Job shop is the typical operation model used in an MTO operation, where the production planner must make three concurrent decisions; they are order selection, lot size, and job schedule. These decisions are usually treated separately in the literature and are mostly led to heuristic solutions. The first phase of the study is focused on a formal definition of the problem. Mathematical programming techniques are applied to modeling this problem in terms of its objective, decision variables, and constraints. A commercial solver, CPLEX is applied to solve the resulting mixed-integer linear programming model with small instances to validate the mathematical formulation. The computational result shows it is not practical for solving problems of industrial size, using a commercial solver. The second phase of this study is focused on development of an effective solution approach to this problem of large scale. The proposed solution approach is an iterative process involving three sequential decision steps of order selection, lot sizing, and lot scheduling. A range of simple sequencing rules are identified for each of the three subproblems. Using computer simulation as the tool, an experiment is designed to evaluate their performance against a set of system parameters. For order selection, the proposed weighted most profit rule performs the best. The shifting bottleneck and the earliest operation finish time both are the best scheduling rules. For lot sizing, the proposed minimum cost increase heuristic, based on the Dixon-Silver method performs the best, when the demand-to-capacity ratio at the bottleneck machine is high. The proposed minimum cost heuristic, based on the Wagner-Whitin algorithm is the best lot-sizing heuristic for shops of a low demand-to-capacity ratio. The proposed heuristic is applied to an industrial case to further evaluate its performance. The result shows it can improve an average of total profit by 16.62%. This research contributes to the production planning research community with a complete mathematical definition of the problem and an effective solution approach to solving the problem of industry scale.

Formulações e algoritmos para o problema das p-medianas heterogêneo livre de penalidade

This work presents a new model for the Heterogeneous p-median Problem (HPM), proposed to recover the hidden category structures present in the data provided by a sorting task procedure, a popular approach to understand heterogeneous individual’s perception of products and brands. This new model is named as the Penalty-free Heterogeneous p-median Problem (PFHPM), a single-objective version of the original problem, the HPM. The main parameter in the HPM is also eliminated, the penalty factor. It is responsible for the weighting of the objective function terms. The adjusting of this parameter controls the way that the model recovers the hidden category structures present in data, and depends on a broad knowledge of the problem. Additionally, two complementary formulations for the PFHPM are shown, both mixed integer linear programming problems. From these additional formulations lower-bounds were obtained for the PFHPM. These values were used to validate a specialized Variable Neighborhood Search (VNS) algorithm, proposed to solve the PFHPM. This algorithm provided good quality solutions for the PFHPM, solving artificial generated instances from a Monte Carlo Simulation and real data instances, even with limited computational resources. Statistical analyses presented in this work suggest that the new algorithm and model, the PFHPM, can recover more accurately the original category structures related to heterogeneous individual’s perceptions than the original model and algorithm, the HPM. Finally, an illustrative application of the PFHPM is presented, as well as some insights about some new possibilities for it, extending the new model to fuzzy environments

Cooperative routing for collision minimization in wireless sensor networks

Cooperative communication has gained much interest due to its ability to exploit the broadcasting nature of the wireless medium to mitigate multipath fading. There has been considerable amount of research on how cooperative transmission can improve the performance of the network by focusing on the physical layer issues. During the past few years, the researchers have started to take into consideration cooperative transmission in routing and there has been a growing interest in designing and evaluating cooperative routing protocols. Most of the existing cooperative routing algorithms are designed to reduce the energy consumption; however, packet collision minimization using cooperative routing has not been addressed yet. This dissertation presents an optimization framework to minimize collision probability using cooperative routing in wireless sensor networks. More specifically, we develop a mathematical model and formulate the problem as a large-scale Mixed Integer Non-Linear Programming problem. We also propose a solution based on the branch and bound algorithm augmented with reducing the search space (branch and bound space reduction). The proposed strategy builds up the optimal routes from each source to the sink node by providing the best set of hops in each route, the best set of relays, and the optimal power allocation for the cooperative transmission links. To reduce the computational complexity, we propose two near optimal cooperative routing algorithms. In the first near optimal algorithm, we solve the problem by decoupling the optimal power allocation scheme from optimal route selection. Therefore, the problem is formulated by an Integer Non-Linear Programming, which is solved using a branch and bound space reduced method. In the second near optimal algorithm, the cooperative routing problem is solved by decoupling the transmission power and the relay node se- lection from the route selection. After solving the routing problems, the power allocation is applied in the selected route. Simulation results show the algorithms can significantly reduce the collision probability compared with existing cooperative routing schemes.

Shift Scheduling in Services When Employees Have Limited Availability: An L. P. Approach

This paper compares two linear programming (LP) models for shift scheduling in services where homogeneously-skilled employees are available at limited times. Although both models are based on set covering approaches, one explicitly matches employees to shifts, while the other imposes this matching implicitly. Each model is used in three forms—one with complete, another with very limited meal break placement flexibility, and a third without meal breaks—to provide initial schedules to a completion/improvement heuristic. The term completion/improvement heuristic is used to describe a construction/ improvement heuristic operating on a starting schedule. On 80 test problems varying widely in scheduling flexibility, employee staffing requirements, and employee availability characteristics, all six LP-based procedures generated lower cost schedules than a comparison from-scratch construction/improvement heuristic. This heuristic, which perpetually maintains an explicit matching of employees to shifts, consists of three phases which add, drop, and modify shifts. In terms of schedule cost, schedule generation time, and model size, the procedures based on the implicit model performed better, as a group, than those based on the explicit model. The LP model with complete break placement flexibility and implicitly matching employees to shifts generated schedules costing 6.7% less than those developed by the from-scratch heuristic.

Improving the Utilization of Front-Line Service Delivery System Personnel

There are two types of work typically performed in services which differ in the degree of control management has over when the work must be done. Serving customers, an activity that can occur only when customers are in the system is, by its nature, uncontrollable work. In contrast, the execution of controllable work does not require the presence of customers, and is work over which management has some degree of temporal control. This paper presents two integer programming models for optimally scheduling controllable work simultaneously with shifts. One model explicitly defines variables for the times at which controllable work may be started, while the other uses implicit modeling to reduce the number of variables. In an initial experiment of 864 test problems, the latter model yielded optimal solutions in approximately 81 percent of the time required by the former model. To evaluate the impact on customer service of having front-line employees perform controllable work, a second experiment was conducted simulating 5,832 service delivery systems. The results show that controllable work offers a useful means of improving labor utilization. Perhaps more important, it was found that having front-line employees perform controllable work did not degrade the desired level of customer service.

Schedulazione delle rotte marittime nel settore ortofrutticolo. Modelli e Metodi

Il trasporto marittimo è una delle modalità più utilizzate soprattutto per la movimentazione di grandi volumi di prodotti tra i continenti in quanto è a basso costo, sicuro e meno inquinante rispetto ad altri mezzi di movimentazione. Ai giorni nostri è responsabile di circa l’80% del commercio globale (in volume di carichi trasportati). Il settore del trasporto marittimo ha avuto una lunga tradizione di pianificazione manuale effettuata da progettisti esperti.
 L’obiettivo principale di questa trattazione è stato quello di implementare un modello matematico lineare (MILP, Mixed-Integer Linear Programming Model) per l’ottimizzazione delle rotte marittime nell’ambito del mercato orto-frutticolo che si sviluppa nel bacino del Mediterraneo (problema di Ship-Scheduling). Il modello fornito in questa trattazione è un valido strumento di supporto alle decisioni che può utilizzare uno spedizioniere nell’ambito della pianificazione delle rotte marittime della flotta di navi in suo possesso. Consente di determinare l’insieme delle rotte ottimali che devono essere svolte da un insieme di vettori al fine di massimizzare il profitto complessivo dello spedizioniere, generato nell’arco di tempo considerato. Inoltre, permette di ottenere, per ogni nave considerata, la ripartizione ottimale della merce (carico ottimale).

How do Small Players Deduce Beliefs about Uncertainty? A Look at Texas Shale Oil Investments

Thesis (Ph.D.)--University of Washington, 2016-08

Discrete-time positive periodic systems with state and control constraints

The aim of this paper is to provide an efficient control design technique for discrete-time positive periodic systems. In particular, stability, positivity and periodic invariance of such systems are studied. Moreover, the concept of periodic invariance with respect to a collection of boxes is introduced and investigated with connection to stability. It is shown how such concept can be used for deriving a stabilizing state-feedback control that maintains the positivity of the closed-loop system and respects states and control signals constraints. In addition, all the proposed results can be efficiently solved in terms of linear programming.

Contribution à la planification tactique et opérationnelle du transport forestier

Cette thèse est une contribution à la modélisation, la planification et l’optimisation du transport pour l’approvisionnement en bois de forêt des industries de première transformation. Dans ce domaine, les aléas climatiques (mise au sol des bois par les tempêtes), sanitaires (attaques bactériologiques et fongiques des bois) et commerciaux (variabilité et exigence croissante des marchés) poussent les divers acteurs du secteur (entrepreneurs et exploitants forestiers, transporteurs) à revoir l’organisation de la filière logistique d’approvisionnement, afin d’améliorer la qualité de service (adéquation offre-demande) et de diminuer les coûts. L’objectif principal de cette thèse était de proposer un modèle de pilotage améliorant la performance du transport forestier, en respectant les contraintes et les pratiques du secteur. Les résultats établissent une démarche de planification hiérarchique des activités de transport à deux niveaux de décision, tactique et opérationnel. Au niveau tactique, une optimisation multi-périodes permet de répondre aux commandes en minimisant l’activité globale de transport, sous contrainte de capacité agrégée des moyens de transport accessibles. Ce niveau permet de mettre en œuvre des politiques de lissage de charge et d’organisation de sous-traitance ou de partenariats entre acteurs de transport. Au niveau opérationnel, les plans tactiques alloués à chaque transporteur sont désagrégés, pour permettre une optimisation des tournées des flottes, sous contrainte des capacités physiques de ces flottes. Les modèles d’optimisation de chaque niveau sont formalisés en programmation linéaire mixte avec variables binaires. L’applicabilité des modèles a été testée en utilisant un jeu de données industrielles en région Aquitaine et a montré des améliorations significatives d’exploitation des capacités de transport par rapport aux pratiques actuelles. Les modèles de décision ont été conçus pour s’adapter à tout contexte organisationnel, partenarial ou non : la production du plan tactique possède un caractère générique sans présomption de l’organisation, celle-ci étant prise en compte, dans un deuxième temps, au niveau de l’optimisation opérationnelle du plan de transport de chaque acteur.