Stronger column generation bounds for the Minimum Cost Hop-and-root Constrained Forest Problem

In this paper, we present a Dantzig-Wolfe reformulation for the Minimum Cost Hop-and-root Constrained Forest Problem and discuss a Column Generation (CG) method to evaluate its Linear Programming (LP) bounds. For solving one of two types of pricing problems that arise in CG, we compared two solution strategies: Dynamic Programming and a Branch-and-cut (BC) algorithm. In general, CG performed much better when BC was used. Not only the LP bounds implied by the proposed reformulation are much stronger than the multi-commodity flow bounds from the literature, but also could be evaluated with less computational time. A Column Generation Heuristic was discussed and implemented, providing upper bounds that are, on average, within 2.3% of optimality.     

A Branch-and-price algorithm for a Vehicle Routing Problem with Cross-Docking

n this paper, we propose a reformulation and a Branch-and-price (BP) algorithm for the Vehicle Routing Problem with Cross-Docking (VRPCD). Our computational results indicate that the reformulation provides bounds much stronger than network flow bounds from previous studies. As a consequence, when BP and a Linear Programming based Branch-and-bound (LPBB) method (that relies on the network flow formulation) are run for the same restricted time limit, BP clearly dominates LPBB in terms of the quality of lower and upper bounds found during the search.     

A computational study of exact knapsack separation for the generalized assignment problem

The Generalized Assignment Problem is a well-known NP-hard combinatorial optimization problem which consists of minimizing the assignment costs of a set of jobs to a set of machines satisfying capacity constraints. Most of the existing algorithms are of a Branch-and-Price type, with lower bounds computed through Dantzig–Wolfe reformulation and column generation.     

Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines. The aim of the article is to develop a Lagrangian heuristic to obtain good solutions to this problem and good lower bounds to certify the quality of solutions. Based on a strong reformulation of the problem as a shortest path problem, the Lagrangian relaxation is applied to the demand constraints (flow constraint) and the relaxed problem is decomposed per period and per machine. The subgradient optimization method is used to update the Lagrangian multipliers. A primal heuristic, based on transfers of production, is designed to generate feasible solutions (upper bounds). Computational results using data from the literature are presented and show that our method is efficient, produces lower bounds of good quality and competitive upper bounds, when compared with the bounds produced by another method from the literature and by high-performance MIP software.     

A reformulation for the stochastic lot sizing problem with service-level constraints

We study the stochastic lot-sizing problem with service level constraints and propose an efficient mixed integer reformulation thereof. We use the formulation of the problem present in the literature as a benchmark, and prove that the reformulation has a stronger linear relaxation. Also, we numerically illustrate that it yields a superior computational performance. The results of our numerical study reveals that the reformulation can optimally solve problem instances with planning horizons over 200 periods in less than a minute.     

The one-warehouse multi-retailer problem: reformulation, classification, and computational results

We consider the one-warehouse multi-retailer problem where a warehouse replenishes multiple retailers with deterministic dynamic demands over a horizon. The problem is to determine when and how much to order to the warehouse and retailers such that the total system-wide costs are minimized. We propose a new (combined transportation and shortest path based) integer programming reformulation for the problem in addition to the echelon stock and transportation based formulations in the literature. We analyze the strength of the LP relaxations of three formulations and show that the new formulation is stronger than others. We also show that the new and transportation based formulations are equivalent for the joint replenishment problem, where the warehouse is a crossdocking facility. We extend all formulations to the case with initial inventory at the warehouse and reveal the relation among their LP relaxations. We present our computational experiments with all formulations over a set of randomly generated test instances.     

The quadratic knapsack problem—a survey

The binary quadratic knapsack problem maximizes a quadratic objective function subject to a linear capacity constraint. Due to its simple structure and challenging difficulty it has been studied intensively during the last two decades. The present paper gives a survey of upper bounds presented in the literature, and show the relative tightness of several of the bounds. Techniques for deriving the bounds include relaxation from upper planes, linearization, reformulation, Lagrangian relaxation, Lagrangian decomposition, and semidefinite programming. A short overview of heuristics, reduction techniques, branch-and-bound algorithms and approximation results is given, followed by an overview of valid inequalities for the quadratic knapsack polytope. The paper is concluded by an experimental study where the upper bounds presented are compared with respect to strength and computational effort.     

Reformulation by discretization: Application to economic lot sizing

In this paper we apply a discretization reformulation technique to the classical economic lot sizing problem. This reformulation yields the same LP bounds as the original model. We show, however, that by reducing adequately the coefficients of some variables, one obtains an enhanced reformulation whose LP relaxation solution is integer.     

Lagrangean relaxation based heuristics for lot sizing with setup times

We consider a lot sizing problem with setup times where the objective is to minimize the total inventory carrying cost only. The demand is dynamic over time and there is a single resource of limited capacity. We show that the approaches implemented in the literature for more general versions of the problem do not perform well in this case. We examine the Lagrangean relaxation (LR) of demand constraints in a strong reformulation of the problem. We then design a primal heuristic to generate upper bounds and combine it with the LR problem within a subgradient optimization procedure. We also develop a simple branch and bound heuristic to solve the problem. Computational results on test problems taken from the literature show that our relaxation procedure produces consistently better solutions than the previously developed heuristics in the literature.     

Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem

In this paper, we investigate Semidefinite Programming (SDP) lower bounds for the Quadratic Minimum Spanning Tree Problem (QMSTP). Two SDP lower bounding approaches are introduced here. Both apply Lagrangian Relaxation to an SDP relaxation for the problem. The first one explicitly dualizes the semidefiniteness constraint, attaching to it a positive semidefinite matrix of Lagrangian multipliers. The second relies on a semi-infinite reformulation for the cone of positive semidefinite matrices and dualizes a dynamically updated finite set of inequalities that approximate the cone. These lower bounding procedures are the core ingredient of two QMSTP Branch-and-bound algorithms. Our computational experiments indicate that the SDP bounds computed here are very strong, being able to close at least 70% of the gaps of the most competitive formulation in the literature. As a result, their accompanying Branch-and-bound algorithms are competitive with the best previously available QMSTP exact algorithm in the literature. In fact, one of these new Branch-and-bound algorithms stands out as the new best exact solution approach for the problem.     

Improved approximation results on standard quartic polynomial optimization

In this paper, we consider the problem of approximately solving standard quartic polynomial optimization (SQPO). Using its reformulation as a copositive tensor programming, we show how to approximate the optimal solution of SQPO by using a series of polyhedral cones to approximate the cone of copositive tensors. The established quality of approximation is sharper than the ones studied in the literature. As an interesting extension, we also propose some approximation bounds on multi-homogenous polynomial optimization problems.     

An integer linear programming approach for a class of bilinear integer programs

We propose an Integer Linear Programming (ILP) approach for solving integer programs with bilinear objectives and linear constraints. Our approach is based on finding upper and lower bounds for the integer ensembles in the bilinear objective function, and using the bounds to obtain a tight ILP reformulation of the original problem, which can then be solved efficiently. Numerical experiments suggest that the proposed approach outperforms a latest iterative ILP approach, with notable reductions in the average solution time.     

Improved lower bounds for the capacitated lot sizing problem with setup times

We present new lower bounds for the capacitated lot sizing problem, applying decomposition to the network reformulation. The demand constraints are the linking constraints and the problem decomposes into subproblems per period containing the capacity and setup constraints. Computational results and a comparison to other lower bounds are presented.     

An evaluation of semidefinite programming based approaches for discrete lot-sizing problems

The present work is intended as a first step towards applying semidefinite programming models and tools to discrete lot-sizing problems including sequence-dependent changeover costs and times. Such problems can be formulated as quadratically constrained quadratic binary programs. We investigate several semidefinite relaxations by combining known reformulation techniques recently proposed for generic quadratic binary problems with problem-specific strengthening procedures developed for lot-sizing problems. Our computational results show that the semidefinite relaxations consistently provide lower bounds of significantly improved quality as compared with those provided by the best previously published linear relaxations. In particular, the gap between the semidefinite relaxation and the optimal integer solution value can be closed for a significant proportion of the small-size instances, thus avoiding to resort to a tree search procedure. The reported computation times are significant. However improvements in SDP technology can still be expected in the future, making SDP based approaches to discrete lot-sizing more competitive.     

Bounds on stochastic convex allocation problems

We consider a stochastic convex program arising in a certain resource allocation problem. The uncertainty is in the demand for a resource which is to be allocated among several competing activities under convex inventory holding and shortage costs. The problem is cast as a two–period stochastic convex program and we derive tight upper and lower bounds to the problem using marginal distributions of the demands, which may be stochastically dependent. It turns out that these bounds are tighter than the usual bounds in the literature which are based on limited moment information of the underlying random variables. Numerical examples illustrate the bounds.     

Linear,Integer, Separable and Fuzzy Programming Problems: A Unified Approach towards Reformulation

For mathematical programming (MP) to have greater impact as a decision tool, MP software systems must offer suitable support in terms of model communication and modelling techniques. In this paper, modelling techniques that allow logical restrictions to be modelled in integer programming terms are described, and their implications discussed. In addition, it is illustrated that many classes of non-linearities which are not variable separable may be, after suitable algebraic manipulation, put in a variable separable form. The methods of reformulating the fuzzy linear programming problem as a max-min problem is also introduced. It is shown that analysis of bounds plays a key role in the following four important contexts: model reduction, reformulation of logical restrictions as 0-1 mixed integer programmes, reformulation of non-linear programmes as variable separable programmes and reformulation of fuzzy linear programmes. It is observed that, as well as incorporating an interface between the modeller and the optimizer, there is a need to make available to the modeller software facilities which support the model reformulation techniques described here.     

Automatic Dantzig–Wolfe reformulation of mixed integer programs

Mathematical Programming - Dantzig–Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the...     

A tree search algorithm for the multi-commodity location problem

The multi-commodity location problem is an extension of the simple plant location problem. The problem is to decide on locations of facilities to meet customer demands for several commodities in such a way that total fixed plus variable costs are minimized. Only one commodity may be supplied from any location.In this paper a primal and a dual heuristic for producing good bounds are presented. A method of improving these bounds by using a new Lagrangean relaxation for the problem is also presented. Computational results with problems taken from the literature are provided.     

Stronger upper and lower bounds for a hard batching problem to feed assembly lines

In this paper we present an Integer Programming reformulation for a hard batching problem encountered in feeding assembly lines. The study was motivated by the real process to feed the production flow through the shop floor in a leading automobile industry in Brazil. The problem consists of deciding the assignment of items to containers and the frequency of moves from the storage area to the line in order to meet demands with minimum cost. Better lower and upper bounds were obtained by a branch-and-bound algorithm based on the proposed reformulation. We also present valid inequalities that may improve such algorithm even further.