Search results for "integer programming"

Nesting Problems : Exact and Heuristic Algorithms

2013

Nesting problems are two-dimensional cutting and packing problems involving irregular shapes. This thesis is focused on real applications on Nesting problems such as the garment industry or the glass cutting. The aim is to study different mathematical methodologies to obtain good lower bounds by exact procedures and upper bounds by heuristic algorithms. The core of the thesis is a mathematical model, a Mixed Integer Programming model, which is adapted in each one of the parts of the thesis. This study has three main parts: first, an exact algorithm for Nesting problems when rotation for the pieces is not allowed; second, an Iterated Greedy algorithm to deal with more complex Nesting problem…

Minimizing fleet operating costs for a container transportation company

2006

Abstract This paper focuses on a fleet management problem that arises in container trucking industry. From the container transportation company perspective, the present and future operating costs to minimize can be divided in three components: the routing costs, the resource (i.e., driver and truck) assignment costs and the container repositioning costs (i.e., the costs of restoring a given container fleet distribution over the serviced territory, as requested by the shippers that own the containers). This real-world problem has been modeled as an integer programming problem. The proposed solution approach is based on the decomposition of this problem in three simpler sub-problems associate…

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…

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…

Landowner preferences and conservation prioritization: response to Nielsen et al.

2017

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…

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…

Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem

2012

This paper presents the first full-fledged branch-and-price (bap) algorithm for the capacitated arc-routing problem (CARP). Prior exact solution techniques either rely on cutting planes or the transformation of the CARP into a node-routing problem. The drawbacks are either models with inherent symmetry, dense underlying networks, or a formulation where edge flows in a potential solution do not allow the reconstruction of unique CARP tours. The proposed algorithm circumvents all these drawbacks by taking the beneficial ingredients from existing CARP methods and combining them in a new way. The first step is the solution of the one-index formulation of the CARP in order to produce strong cut…

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.

Mathematical models for multicontainer loading problems

2017

Abstract This paper deals with the problem of a distribution company that has to serve its customers by putting first the products on pallets and then loading the pallets onto trucks. We approach the problem by developing and solving integer linear models. We start with basic models, that include the essential features of the problem, such as respecting the dimensions of the truck, and not exceeding the total weight capacity and the maximum weigh capacity on each axle. Then, we add progressively new conditions to consider the weight and volume of pallet bases and to include other desirable features for the solutions to be useful in practice, such as the position of the center of gravity and…