Search results for "integer programming"
showing 10 items of 69 documents
An adaptive multimeme algorithm for designing HIV multidrug therapies.
2007
This paper proposes a period representation for modeling the multidrug HIV therapies and an Adaptive Multimeme Algorithm (AMmA) for designing the optimal therapy. The period representation offers benefits in terms of flexibility and reduction in dimensionality compared to the binary representation. The AMmA is a memetic algorithm which employs a list of three local searchers adaptively activated by an evolutionary framework. These local searchers, having different features according to the exploration logic and the pivot rule, have the role of exploring the decision space from different and complementary perspectives and, thus, assisting the standard evolutionary operators in the optimizati…
The multiple vehicle pickup and delivery problem with LIFO constraints
2015
Abstract This paper approaches a pickup and delivery problem with multiple vehicles in which LIFO conditions are imposed when performing loading and unloading operations and the route durations cannot exceed a given limit. We propose two mixed integer formulations of this problem and a heuristic procedure that uses tabu search in a multi-start framework. The first formulation is a compact one, that is, the number of variables and constraints is polynomial in the number of requests, while the second one contains an exponential number of constraints and is used as the basis of a branch-and-cut algorithm. The performances of the proposed solution methods are evaluated through an extensive comp…
Enabling peer-to-peer User-Preference-Aware Energy Sharing Through Reinforcement Learning
2020
Renewable, heterogeneous and distributed energy resources are the future of power systems, as envisioned by the recent paradigm of Virtual Power Plants (VPPs). Residential electricity generation, e.g., through photovoltaic panels, plays a fundamental role in this paradigm, where users are able to participate in an energy sharing system and exchange energy resources among each other. In this work, we study energy sharing systems and, differently from previous approaches, we consider realistic user behaviors by taking into account the user preferences and level of engagement in the energy trades. We formulate the problem of matching energy resources while contemplating the user behavior as a …
Polyhedral results for a vehicle routing problem
1991
Abstract The Vehicle Routing Problem is a well known, and hard, combinatorial problem, whose polyhedral structure has deserved little attention. In this paper we consider the particular case in which all the demands are equal (since in the general case the associated polytope may be empty). From a known formulation of the problem we obtain the dimension of the corresponding polytope and we study the facetial properties of every inequality in it.
Comment on “A simple way to incorporate uncertainty and risk into forest harvest scheduling”
2017
In a recent research article, Robinson et al. (2016) described a method of estimating uncertainty of harvesting outcomes by analyzing the historical yield to the associated prediction for a large number of harvest operations. We agree with this analysis, and consider it a useful tool to integrate estimates of uncertainty into the optimization process. The authors attempt to manage the risk using two different methods, based on deterministic integer linear programming. The first method focused on maximizing the 10th quantile of the distribution of predicted volume subject to area constraint, while the second method focused on minimizing the variation of total quantity of volume harvested sub…
Nurse Scheduling Problem: An Integer Programming Model with a Practical Application
2012
We use a binary integer programming model to formulate and solve a nurse scheduling problem (NSP) which maximally satisfies nurse preferences. In a practical application of a VA hospital, besides considering the scheduling of two types of nurses (registered nurses and licensed practical nurses), two other types of employees (nursing assistants and health care techs), one nurse manager, and a clinical nurse leader are also included in our model. Most of these employees are working full-time. In addition, we distinguish the schedule of weekdays and weekends with different requirements and different preferences for employees. Besides the requirements for each shift, we consider requirements fo…
Cotas inferiores para el QAP-Arbol
1985
The Tree-QAP is a special case of the Quadratic Assignment Problem where the flows not equal zero form a tree. No condition is required for the distance matrix. In this paper we present an integer programming formulation for the Tree-QAP. We use this formulation to construct four Lagrangean relaxations that produce several lower bounds for this problem. To solve one of the relaxed problems we present a Dynamic Programming algorithm which is a generalization of the algorithm of this type that gives a lower bound for the Travelling Salesman Problem. A comparison is given between the lower bounds obtained by each ralaxation for examples with size from 12 to 25.
Flexibility Services to Minimize the Electricity Production from Fossil Fuels. A Case Study in a Mediterranean Small Island
2019
The design of multi-carrier energy systems (MESs) has become increasingly important in the last decades, due to the need to move towards more efficient, flexible, and reliable power systems. In a MES, electricity, heating, cooling, water, and other resources interact at various levels, in order to get optimized operation. The aim of this study is to identify the optimal combination of components, their optimal sizes, and operating schedule allowing minimizing the annual cost for meeting the energy demand of Pantelleria, a Mediterranean island. Starting from the existing energy system (comprising diesel generators, desalination plant, freshwater storage, heat pumps, and domestic hot water st…
GRASP and path relinking for the max–min diversity problem
2010
The max-min diversity problem (MMDP) consists in selecting a subset of elements from a given set in such a way that the diversity among the selected elements is maximized. The problem is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in the social and biological sciences. We propose a heuristic method-based on the GRASP and path relinking methodologies-for finding approximate solutions to this optimization problem. We explore different ways to hybridize GRASP and path relinking, including the recently proposed variant known as GRASP with evolutionary p…
Dual Inequalities for Stabilized Column Generation Revisited
2014
Column generation (CG) models have several advantages over compact formulations: they provide better linear program bounds, may eliminate symmetry, and can hide nonlinearities in their subproblems. However, users also encounter drawbacks in the form of slow convergence, also known as the tailing-off effect, and the oscillation of the dual variables. Among different alternatives for stabilizing the CG process, Ben Amor et al. [Ben Amor H, Desrosiers J, Valério de Carvalho JM (2006) Dual-optimal inequalities for stabilized column generation. Oper. Res. 54(3):454–463] suggest the use of dual-optimal inequalities (DOIs) in the context of cutting stock and bin packing problems. We generalize th…