Search results for "Integer programming"
showing 10 items of 69 documents
Competition and cooperation for intermodal container transhipment: A network optimization approach
2018
Abstract This study presents an analysis of cross-border competition and cooperation between ports in Bangladesh and India. Nepal and Bhutan are countries without access to seaports — two landlocked countries in South Asia, depending solely on the Indian port of Kolkata for their international seaborne trade. Alternatives do exist in the Bangladeshi ports of Chittagong and Mongla but these are not exploited, in spite of trade agreements that allow access to a third country's port, and/or crossing the land of a third, intermediate, country. We formulate a mixed integer linear programming optimization model to find the optimum economic benefit of port users (serving Bhutan, Nepal and Northeas…
A new compact formulation for the discrete p-dispersion problem
2017
Abstract This paper addresses the discrete p -dispersion problem (PDP) which is about selecting p facilities from a given set of candidates in such a way that the minimum distance between selected facilities is maximized. We propose a new compact formulation for this problem. In addition, we discuss two simple enhancements of the new formulation: Simple bounds on the optimal distance can be exploited to reduce the size and to increase the tightness of the model at a relatively low cost of additional computation time. Moreover, the new formulation can be further strengthened by adding valid inequalities. We present a computational study carried out over a set of large-scale test instances i…
Packing a Trunk
2003
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to pack as many identical boxes of size 4 × 2 × 1 units as possible into the interior of the trunk. This measure is important for car manufacturers, because it is a standard in the European Union.
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…
Perceived-Value-driven Optimization of Energy Consumption in Smart Homes
2020
Residential energy consumption has been rising rapidly during the last few decades. Several research efforts have been made to reduce residential energy consumption, including demand response and smart residential environments. However, recent research has shown that these approaches may actually cause an increase in the overall consumption, due to the complex psychological processes that occur when human users interact with these energy management systems. In this article, using an interdisciplinary approach, we introduce a perceived-value driven framework for energy management in smart residential environments that considers how users perceive values of different appliances and how the us…
The Steiner Traveling Salesman Problem and its extensions
2019
Abstract This paper considers the Steiner Traveling Salesman Problem, an extension of the classical Traveling Salesman Problem on an incomplete graph where not all vertices have demand. Some extensions including several depots or location decisions are introduced, modeled and solved. A compact integer linear programming formulation is proposed for each problem, where the routes are represented with two-index decision variables, and parity conditions are modeled using cocircuit inequalities. Exact branch-and-cut algorithms are developed for all formulations. Computational results obtained confirm the good performance of the algorithms. Instances with up to 500 vertices are solved optimally.
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.
Branch and bound for the cutwidth minimization problem
2013
The cutwidth minimization problem consists of finding a linear arrangement of the vertices of a graph where the maximum number of cuts between the edges of the graph and a line separating consecutive vertices is minimized. We first review previous approaches for special classes of graphs, followed by lower bounds and then a linear integer formulation for the general problem. We then propose a branch-and-bound algorithm based on different lower bounds on the cutwidth of partial solutions. Additionally, we introduce a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic to obtain good initial solutions. The combination of the branch-and-bound and GRASP methods results in optimal solu…
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…
Optimal Usage of Multiple Network Connections
2008
In the future mobile networks, a mobile terminal is able to select the best suitable network for each data transmission. The selection of a network connection to be used has been under a lot of study. In this paper, we consider a more extensive case in which we do not select a network connection but use several network connections simultaneously to transfer data. When data is transferred using multiple network connections, a network connection has to be selected for each component of the data. We have modelled this problem as a multiobjective optimization problem and developed a heuristic to solve the problem fast in a static network environment. In this paper, we discuss solving the proble…