Search results for "Integer"
showing 10 items of 250 documents
A branch-and-cut algorithm for the Orienteering Arc Routing Problem
2016
[EN] In arc routing problems, customers are located on arcs, and routes of minimum cost have to be identified. In the Orienteering Arc Routing Problem (OARP),in addition to a set of regular customers that have to be serviced, a set of potential customers is available. From this latter set, customers have to be chosen on the basis of an associated profit. The objective is to find a route servicing the customers which maximize the total profit collected while satisfying a given time limit on the route.In this paper, we describe large families of facet-inducing inequalities for the OARP and present a branch-and-cut algorithm for its solution. The exact algorithm embeds a procedure which builds…
Matheuristics for the irregular bin packing problem with free rotations
2017
[EN] We present a number of variants of a constructive algorithm able to solve a wide variety of variants of the Two-Dimensional Irregular Bin Packing Problem (2DIBPP). The aim of the 2DIBPP is to pack a set of irregular pieces, which may have concavities, into stock sheets (bins) with fixed dimensions in such a way that the utilization is maximized. This problem is inspired by a real application from a ceramic company in Spain. In addition, this problem arises in other industries such as the garment industry or ship building. The constructive procedure presented in this paper allows both free orientation for the pieces, as in the case of the ceramic industry, or a finite set of orientation…
The continuous Berth Allocation Problem in a container terminal with multiple quays
2015
We propose an integer linear model for the case of BAP with multiple quays.We design several constructive procedures and propose a large set of priority rules.We design a genetic algorithm, using the solutions obtained by the priority rules.For BAP with one quay, our genetic algorithm outperforms the best published methods. This paper extends the study of the continuous Berth Allocation Problem to the case of multiple quays, which is found in many container terminals around the world. Considering multiple quays adds a problem of assigning vessels to quays to the problem of determining berthing times and positions for each incoming vessel.This problem has not been considered in the literatur…
The Multiple Multidimensional Knapsack with Family-Split Penalties
2021
Abstract The Multiple Multidimensional Knapsack Problem with Family-Split Penalties (MMdKFSP) is introduced as a new variant of both the more classical Multi-Knapsack and Multidimensional Knapsack Problems. It reckons with items categorized into families and where if an individual item is selected to maximize the profit, all the items of the same family must be selected as well. Items belonging to the same family can be assigned to different knapsacks; however, in this case, split penalties are incurred. This problem arises in resource management of distributed computing contexts and Service Oriented Architecture environments. An exact algorithm based on the exploitation of a specific combi…
Data-Driven Pump Scheduling for Cost Minimization in Water Networks
2021
Pumps consume a significant amount of energy in a water distribution network (WDN). With the emergence of dynamic energy cost, the pump scheduling as per user demand is a computationally challenging task. Computing the decision variables of pump scheduling relies over mixed integer optimization (MIO) formulations. However, MIO formulations are NP-hard in general and solving such problems is inefficient in terms of computation time and memory. Moreover, the computational complexity of solving such MIO formulations increases exponentially with the size of the WDN. As an alternative, we propose a data-driven approach to estimate the decision variables of pump scheduling using deep neural netwo…
GRASP with path relinking heuristics for the antibandwidth problem
2010
This article proposes a linear integer programming formulation and several heuristics based on GRASP and path relinking for the antibandwidth problem. In the antibandwidth problem, one is given an undirected graph with n nodes and must label the nodes in a way that each node receives a unique label from the set {1, 2,…,n}, such that, among all adjacent node pairs, the minimum difference between the node labels is maximized. Computational results show that only small instances of this problem can be solved exactly (to optimality) with a commercial integer programming solver and that the heuristics find high-quality solutions in much less time than the commercial solver. © 2010 Wiley Periodic…
Scatter Search and Local NLP Solvers: A Multistart Framework for Global Optimization
2007
The algorithm described here, called OptQuest/NLP or OQNLP, is a heuristic designed to find global optima for pure and mixed integer nonlinear problems with many constraints and variables, where all problem functions are differentiable with respect to the continuous variables. It uses OptQuest, a commercial implementation of scatter search developed by OptTek Systems, Inc., to provide starting points for any gradient-based local solver for nonlinear programming (NLP) problems. This solver seeks a local solution from a subset of these points, holding discrete variables fixed. The procedure is motivated by our desire to combine the superior accuracy and feasibility-seeking behavior of gradie…
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…
Applying the approximation method PAINT and the interactive method NIMBUS to the multiobjective optimization of operating a wastewater treatment plant
2014
Using an interactive multiobjective optimization method called NIMBUS and an approximation method called PAINT, preferable solutions to a five-objective problem of operating a wastewater treatment plant are found. The decision maker giving preference information is an expert in wastewater treatment plant design at the engineering company Pöyry Finland Ltd. The wastewater treatment problem is computationally expensive and requires running a simulator to evaluate the values of the objective functions. This often leads to problems with interactive methods as the decision maker may get frustrated while waiting for new solutions to be computed. Thus, a newly developed PAINT method is used to spe…
A hierarchic approach to production planning and scheduling of a flexible manufacturing system
1999
Abstract The paper deals with the problem of improving the machine utilization of a flexible manufacturing cell. Limited tool magazine space of the machines turns out to be a relevant bottleneck. A hierarchic approach for this problem is proposed. At the upper level, sets of parts that can be concurrently processed (batches) are determined. At the lower levels, batches are sequenced, linked, and scheduled. Methods taken from the literature are used for the solution of the latter subproblems, and an original mixed integer programming model is formulated to determine batches. The proposed methods are discussed on the basis of computational experience carried out on real instances.