Search results for "Integer programming"
showing 10 items of 69 documents
Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem
2014
Finding differentially regulated subgraphs in a biochemical network is an important problem in bioinformatics. We present a new model for finding such subgraphs which takes the polarity of the edges (activating or inhibiting) into account, leading to the problem of finding a connected subgraph induced by \(k\) vertices with maximum weight. We present several algorithms for this problem, including dynamic programming on tree decompositions and integer linear programming. We compare the strength of our integer linear program to previous formulations of the \(k\)-cardinality tree problem. Finally, we compare the performance of the algorithms and the quality of the results to a previous approac…
Discrete frequency models for inventory management – an introduction
2001
Abstract The paper deals with the problem of devising a periodic replenishment policy when orders must be periodic, but only a given, discrete set of order frequencies can be used. The multi-item, instantaneous replenishment case with known demand is studied. In particular, staggering policies somehow arranging replenishments not to come at the same time instants are considered. The paper is composed of three parts: first, a taxonomy of several versions of the discrete frequency problem is proposed, according to different elements; in the second part, a general mixed integer programming model is proposed which is able to capture the peculiarities of the whole spectrum of this kind of proble…
A polynomial algorithm solving a special class of hybrid optimal control problems
2006
Hybrid optimal control problems are, in general, difficult to solve. A current research goal is to isolate those problems that lead to tractable solutions [5]. In this paper, we identify a special class of hybrid optimal control problems which are easy to solve. We do this by using a paradigm borrowed from the Operations Research field. As main result, we present a solution algorithm that converges to the exact solution in polynomial time. Our approach consists in approximating the hybrid optimal control problem via an integer-linear programming reformulation. The integer-linear programming problem is a Set-covering one with a totally unimodular constraint matrix and therefore solving the S…
An Effective Multirestart Deterministic Annealing Metaheuristic for the Fleet Size and Mix Vehicle-Routing Problem with Time Windows
2008
This paper presents a new deterministic annealing metaheuristic for the fleet size and mix vehicle-routing problem with time windows. The objective is to service, at minimal total cost, a set of customers within their time windows by a heterogeneous capacitated vehicle fleet. First, we motivate and define the problem. We then give a mathematical formulation of the most studied variant in the literature in the form of a mixed-integer linear program. We also suggest an industrially relevant, alternative definition that leads to a linear mixed-integer formulation. The suggested metaheuristic solution method solves both problem variants and comprises three phases. In Phase 1, high-quality init…
Decentralized price-driven grid balancing via repurposed electric vehicle batteries
2017
Abstract The share of electricity generated from intermittent renewable sources, e.g., wind and solar grows rapidly. This affects grid stability and power quality. If the share of renewable power generation is to be increased further, additional flexibilities must be introduced. Aggregating small, distributed loads and energy storage facilities is a good medium-term option. In this paper, the suitability of decentralized and on-site optimized storage system consisting of repurposed electric vehicle batteries for grid balancing is investigated. Battery operation is controlled via an optimization procedure, which relies on a one-way communicated pseudo-cost function (PCF). Day-ahead electrici…
A GRASP algorithm for the container stowage slot planning problem
2016
This work presents a generalization of the Slot Planning Problem which raises when the liner shipping industry needs to plan the placement of containers within a vessel (stowage planning). State-of-the-art stowage planning relies on a heuristic decomposition where containers are first distributed in clusters along the vessel. For each of those clusters a specific position for each container must be found. Compared to previous studies, we have introduced two new features: the explicit handling of rolled out containers and the inclusion of separations rules for dangerous cargo. We present a novel integer programming formulation and a Greedy Randomized Adaptive Search Procedure (GRASP) to solv…
An Optimal Monitoring Program for Obtaining Voltage Sag System Indexes
2006
This paper presents a meter placement method for voltage sags monitoring in large transmission systems. An integer programming-based modeling is proposed for choosing the locations of power quality meters. A branch-and-bound-type algorithm is used to solve the optimization problem. A large transmission network is used to validate the method. Stochastic assessment of voltage sags is applied to the test network to obtain simulated monitoring results. Voltage sags system indexes are calculated from monitoring programs designed according to the optimization method. Comparisons with the system indexes obtained from a full monitoring program show the applicability of the method.
A comprehensive tool for efficient design and operation of polygeneration-based energy μgrids serving a cluster of buildings. Part I: Description of …
2013
Polygeneration systems with thermal energy storage represent promising solutions to achieve energy saving and emissions reduction in the civil sector. The definition of customer-oriented design and operation strategies represents a most challenging task, in order to maximize the profitability and make the investment attractive. A large potential is often recognized for the installation of centralized plants serving a cluster of buildings located over a small area; in such cases the design problem becomes extremely complex and the analyst needs reliable instruments to identify the optimal solution. This paper in two parts presents a scientific tool for the optimization of design and operatio…
Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants
2018
We consider extensions of the two-variable guarded fragment, GF2, where distinguished binary predicates that occur only in guards are required to be interpreted in a special way (as transitive relations, equivalence relations, pre-orders or partial orders). We prove that the only fragment that retains the finite (exponential) model property is GF2 with equivalence guards without equality. For remaining fragments we show that the size of a minimal finite model is at most doubly exponential. To obtain the result we invent a strategy of building finite models that are formed from a number of multidimensional grids placed over a cylindrical surface. The construction yields a 2NExpTime-upper bou…
Capacity and Energy-Consumption Optimization for the Cluster-Tree Topology in IEEE 802.15.4
2011
International audience; 802.15.4 proposes to use a cluster-tree hierar- chy to organize the transmissions in Wireless Sensor Networks. In this letter, we propose a framework to analyze formally the capacity and the energy consumption of this structure. We derive a Mixed Integer Linear Programming (MILP) formulation to obtain a topology compliant with the standard. This formulation provides the optimal solution for the network capacity: this con- stitutes an upper bound for any distributed algorithms permitting to construct a cluster-tree. This framework can also be used to evaluate the capacity and to compare quantitatively different cluster-tree algorithms.