Search results for "integer programming"
showing 10 items of 69 documents
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.
Landowner preferences and conservation prioritization : response to Nielsen et al
2017
Decomposition and Mean-Field Approach to Mixed Integer Optimal Compensation Problems
2016
Mixed integer optimal compensation deals with optimization problems with integer- and real-valued control variables to compensate disturbances in dynamic systems. The mixed integer nature of controls could lead to intractability in problems of large dimensions. To address this challenge, we introduce a decomposition method which turns the original n-dimensional optimization problem into n independent scalar problems of lot sizing form. Each of these problems can be viewed as a two-player zero-sum game, which introduces some element of conservatism. Each scalar problem is then reformulated as a shortest path one and solved through linear programming over a receding horizon, a step that mirro…
Integer linear programming in computational biology
2009
Computational molecular biology (bioinformatics) is a young research field that is rich in NP-hard optimization problems. The problem instances encountered are often huge and comprise thousands of variables. Since their introduction into the field of bioinformatics in 1997, integer linear programming (ILP) techniques have been successfully applied to many optimization problems. These approaches have added much momentum to development and progress in related areas. In particular, ILP-based approaches have become a standard optimization technique in bioinformatics. In this review, we present applications of ILP-based techniques developed by members and former members of Kurt Mehlhorn's group.…
Optimised assembly mode reconfiguration of the 5-DOF Gantry-Tau using mixed-integer programming
2010
Pulished version of an article in the journal: Meccanica. Also available from the publisher at: http://dx.doi.org/10.1007/s11012-010-9404-y This paper presents a systematic approach based on Mixed Integer Linear Programming for finding an optimal singularity-free reconfiguration path of the 5-DOF Gantry-Tau parallel kinematic machine. The results in the paper demonstrate that singularity-free reconfiguration (change of assembly mode) of the machine is possible, which significantly increases the usable workspace. The method has been applied to a full-scale prototype and the singularity-free path has been verified both in simulations and with physical experiments using real-time control of th…
The berth allocation problem in terminals with irregular layouts
2019
As international trade thrives, terminals attempt to obtain higher revenue while coping with an increased complexity with regard to terminal management operations. One of the most prevalent problems such terminals face is the Berth Allocation Problem (BAP), which concerns allocating vessels to a set of berths and time slots while simultaneously minimizing objectives such as total stay time or total assignment cost. Complex layouts of real terminals introduce spatial constraints which limit the mooring and departure of vessels. Although significant research has been conducted regarding the BAP, these real-world restrictions have not been taken into account in a general way. The present work …
An Exact Algorithm for the Quadratic Assignment Problem on a Tree
1989
The Tree QAP is a special case of the Quadratic Assignment Problem (QAP) where the nonzero flows form a tree. No condition is required for the distance matrix. This problem is NP-complete and is also a generalization of the Traveling Salesman Problem. In this paper, we present a branch-and-bound algorithm for the exact solution of the Tree QAP based on an integer programming formulation of the problem. The bounds are computed using a Lagrangian relaxation of this formulation. To solve the relaxed problem, we present a Dynamic Programming algorithm which is polynomially bounded. The obtained lower bound is very sharp and equals the optimum in many cases. This fact allows us to employ a redu…
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.
TCSC allocation based on line flow based equations via mixed-integer programming
2007
Summary form only given. Research effort has been given to locate the optimal locations of thyristor-controlled series capacitor (TCSC) and their initial compensation levels using mixed-integer programming (MIP). As a useful technique for combinatorial optimisation over integer and continuous variables, the MIP approach can provide robust performance as well as high computational efficiency while solving complex optimal problems. Previous work using MIP employed DC load flow model ignoring reactive power balance, power loss and transformer tap ratios. In this paper, a new planning method is developed based on recently reported line flow equations and basic linearisation of binary-continuous…
Exact solution of the soft-clustered vehicle-routing problem
2020
Abstract The soft-clustered vehicle-routing problem (SoftCluVRP) extends the classical capacitated vehicle-routing problem by one additional constraint: The customers are partitioned into clusters and feasible routes must respect the soft-cluster constraint, that is, all customers of the same cluster must be served by the same vehicle. In this article, we design and analyze different branch-and-price algorithms for the exact solution of the SoftCluVRP. The algorithms differ in the way the column-generation subproblem, a variant of the shortest-path problem with resource constraints (SPPRC), is solved. The standard approach for SPPRCs is based on dynamic-programming labeling algorithms. We s…