Upper Bounds for the SPOT 5 Daily Photograph Scheduling Problem

This paper introduces tight upper bounds for the daily photograph scheduling problem of earth observation satellites. These bounds, which were unavailable until now, allow us to assess the quality of the heuristic solutions obtained previously. These bounds are obtained with a partition-based approach following the divide and pas conquer principle. Dynamic programming and tabu search are conjointly used in this approach. We present also simplex-based linear programming relaxation and a relaxed knapsack approach for the problem.     

Integrated Procurement Planning in Multi‐division Firms

For large multi‐division firms, coordinating procurement policies across multiple divisions to leverage volume discounts from suppliers based on firm‐wide purchasing power can yield millions of dollars of savings in procurement costs. Coordinated procurement entails deciding which suppliers to use to meet each division's purchasing needs and sourcing preferences so as to minimize overall purchasing, logistics, and operational costs. Motivated by this tactical procurement planning problem facing a large industrial products manufacturer, we propose an integrated optimization model that simultaneously considers both firm‐wide volume discounts and divisional ordering and inventory costs. To effectively solve this large‐scale integer program, we develop and apply a tailored solution approach that exploits the problem structure to generate tight bounds. We identify several classes of valid inequalities to strengthen the linear programming relaxation, establish polyhedral properties of these inequalities, and develop both a cutting‐plane method and a sequential rounding heuristic procedure. Extensive computational tests for realistic problems demonstrate that our integrated sourcing model and solution method are effective and can provide significant economic benefits. The integrated approach yields average savings of 7.5% in total procurement costs compared to autonomous divisional policies, and our algorithm generates near‐optimal solutions (within 0.75% of optimality) within reasonable computational time.     

An improved MIP heuristic for the intermodal hub location problem

Optimization methods have been commonly developed for the intermodal hub location problem because it has a broad range of practical applications. These methods include exact methods (limited on solving large-size problems) and heuristics (no guarantee on solution quality). In order to avoid their weakness but to leverage their strength, we develop an improved MIP heuristic combining branch-and-bound, Lagrangian relaxation, and linear programming relaxation. In the heuristic, we generate a population of initial feasible solutions using the branch-and-bound and Lagrangian relaxation methods and create a linear-relaxed solution using the linear programming relaxation method. We combine these feasible and linear-relaxed solutions to fix a portion of hub location variables so as to create a number of restricted hub location subproblems. We then combine the branch-and-bound method to solve these restricted subproblems for iteratively improving solution quality. We discuss in detail the application of the method to the intermodal hub location problem. The discussion is followed by extensive statistical analysis and computational tests, where the analysis shows statistical significance of solutions for guiding the heuristic search and comparisons with other methods indicate that the proposed approach is computationally tractable and is able to obtain competitive results.     

Solving Steiner Tree Problems in Graphs with Lagrangian Relaxation

This paper presents an algorithm to obtain near optimal solutions for the Steiner tree problem in graphs. It is based on a Lagrangian relaxation of a multi-commodity flow formulation of the problem. An extension of the subgradient algorithm, the volume algorithm, has been used to obtain lower bounds and to estimate primal solutions. It was possible to solve several difficult instances from the literature to proven optimality without branching. Computational results are reported for problems drawn from the SteinLib library.     

Coordinated Capacitated Lot‐Sizing Problem with Dynamic Demand: A Lagrangian Heuristic

Coordinated replenishment problems are common in manufacturing and distribution when a family of items shares a common production line, supplier, or a mode of transportation. In these situations the coordination of shared, and often limited, resources across items is economically attractive. This paper describes a mixed‐integer programming formulation and Lagrangian relaxation solution procedure for the single‐family coordinated capacitated lot‐sizing problem with dynamic demand. The problem extends both the multi‐item capacitated dynamic demand lot‐sizing problem and the uncapacitated coordinated dynamic demand lot‐sizing problem. We provide the results of computational experiments investigating the mathematical properties of the formulation and the performance of the Lagrangian procedures. The results indicate the superiority of the dual‐based heuristic over linear programming‐based approaches to the problem. The quality of the Lagrangian heuristic solution improved in most instances with increases in problem size. Heuristic solutions averaged 2.52% above optimal. The procedures were applied to an industry test problem yielding a 22.5% reduction in total costs.     

The location-routing problem with simultaneous pickup and delivery: Formulations and a heuristic approach

In this paper, we consider a variant of the Location-Routing Problem (LRP), namely the LRP with simultaneous pickup and delivery (LRPSPD). The LRPSPD seeks to minimize total cost by simultaneously locating the depots and designing the vehicle routes that satisfy pickup and delivery demand of each customer at the same time. We propose two polynomial-size mixed integer linear programming formulations for the problem and a family of valid inequalities to strengthen the formulations. While the first formulation is a node-based formulation, the second one is a flow-based formulation. Furthermore, we propose a two-phase heuristic approach based on simulated annealing, tp_SA, to solve the large-size LRPSPD and two initialization heuristics to generate an initial solution for the tp_SA. We then empirically evaluate the strengths of the proposed formulations with respect to their ability to find optimal solutions or strong lower bounds, and investigate the performance of the proposed heuristic approach. Computational results show that the flow-based formulation performs better than the node-based formulation in terms of the solution quality and the computation time on small-size problems. However, the node-based formulation can yield competitive lower bounds in a reasonable amount of time on medium-size problems. Meantime, the proposed heuristic approach is computationally efficient in finding good quality solutions for the LRPSPD.     

Restarting after Branching in the SDP Approach to MAX-CUT and Similar Combinatorial Optimization Problems

Many combinatorial optimization problems have relaxations that are semidefinite programming problems. In principle, the combinatorial optimization problem can then be solved by using a branch-and-cut procedure, where the problems to be solved at the nodes of the tree are semidefinite programs. It is desirable that the solution to one node of the tree should be exploited at the child node in order to speed up the solution of the child. We show how the solution to the parent relaxation can be used as a warm start to construct an appropriate initial dual solution to the child problem. This restart method for SDP branch-and-cut can be regarded as analogous to the use of the dual simplex method in the branch-and-cut method for mixed integer linear programming problems.     

Semidefinite Programming Relaxations for the Quadratic Assignment Problem

Semidefinite programming (SDP) relaxations for the quadratic assignment problem (QAP) are derived using the dual of the (homogenized) Lagrangian dual of appropriate equivalent representations of QAP. These relaxations result in the interesting, special, case where only the dual problem of the SDP relaxation has strict interior, i.e., the Slater constraint qualification always fails for the primal problem. Although there is no duality gap in theory, this indicates that the relaxation cannot be solved in a numerically stable way. By exploring the geometrical structure of the relaxation, we are able to find projected SDP relaxations. These new relaxations, and their duals, satisfy the Slater constraint qualification, and so can be solved numerically using primal-dual interior-point methods.For one of our models, a preconditioned conjugate gradient method is used for solving the large linear systems which arise when finding the Newton direction. The preconditioner is found by exploiting the special structure of the relaxation. See e.g., Vandenverghe and Boyd (1995) for a similar approach for solving SDP problems arising from control applications.Numerical results are presented which indicate that the described methods yield at least competitive lower bounds.     

FIRM EXPANSION THROUGH FRANCHISING: A MODEL AND SOLUTION PROCEDURES

This paper presents a practical model for firm expansion through franchising. The model allows the possibility of opening both company-owned and franchised stores. The objective is to maximize the expected returns to the franchisor from both types of stores, subject to the total capital outlay budget and the excess capacity available at each warehouse. A relaxation for this problem is studied and a heuristic solution procedure that makes use of this relaxation is developed. Experimental results over a wide range of problem structures show this solution methodology to be very effective, with gaps between feasible solution values and upper bounds generally in the 0 to 1 percent range. An efficient branch-and-bound code also is developed. This code is tested on problems with up to 100 potential store locations and 20 regions. It is found to be at least two orders of magnitude faster than a state-of-the-art commercial integer programming package.     

Strengthening a linear reformulation of the 0-1 cubic knapsack problem via variable reordering

The 0-1 cubic knapsack problem (CKP), a generalization of the classical 0-1 quadratic knapsack problem, is an extremely challenging NP-hard combinatorial optimization problem. An effective exact solution strategy for the CKP is to reformulate the nonlinear problem into an equivalent linear form that can then be solved using a standard mixed-integer programming solver. We consider a classical linearization method and propose a variant of a more recent technique for linearizing 0-1 cubic programs applied to the CKP. Using a variable reordering strategy, we show how to improve the strength of the linear programming relaxation of our proposed reformulation, which ultimately leads to reduced overall solution times. In addition, we develop a simple heuristic method for obtaining good-quality CKP solutions that can be used to provide a warm start to the solver. Computational tests demonstrate the effectiveness of both our variable reordering strategy and heuristic method.

     

Distribution planning of bulk lubricants at BP Turkey

We address the distribution planning problem of bulk lubricants at BP Turkey. The problem involves the distribution of different lube products from a single production plant to industrial customers using a heterogeneous fleet. The fleet consists of tank trucks where each tank can only be assigned to a single lube. The objective is to minimize total transportation related costs. The problem basically consists of assigning customer orders to the tanks of the trucks and determining the routes of the tank trucks simultaneously. We model this problem as a 0–1 mixed integer linear program. Since the model is intractable for real-life industrial environment we propose two heuristic approaches and investigate their performances. The first approach is a linear programming relaxation-based algorithm while the second is a rolling-horizon threshold heuristic. We propose two variants of the latter heuristic: the first uses a distance priority whereas the second has a due date priority. Our numerical analysis using company data shows that both variants of the rolling horizon threshold heuristic are able to provide good results fast.     

Bounding Optimal Expected Revenues for Assortment Optimization under Mixtures of Multinomial Logits

We consider assortment problems under a mixture of multinomial logit models. There is a fixed revenue associated with each product. There are multiple customer types. Customers of different types choose according to different multinomial logit models whose parameters depend on the type of the customer. The goal is to find a set of products to offer so as to maximize the expected revenue obtained over all customer types. This assortment problem under the multinomial logit model with multiple customer types is NP‐complete. Although there are heuristics to find good assortments, it is difficult to verify the optimality gap of the heuristics. In this study, motivated by the difficulty of finding optimal solutions and verifying the optimality gap of heuristics, we develop an approach to construct an upper bound on the optimal expected revenue. Our approach can quickly provide upper bounds and these upper bounds can be quite tight. In our computational experiments, over a large set of randomly generated problem instances, the upper bounds provided by our approach deviate from the optimal expected revenues by 0.15% on average and by less than one percent in the worst case. By using our upper bounds, we are able to verify the optimality gaps of a greedy heuristic accurately, even when optimal solutions are not available.     

A Lagrangian relaxation approach for the multiple sequence alignment problem

We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. The upper bound at each bb node is based on a Lagrangian relaxation of an integer linear programming formulation for MSA. Dualizing certain inequalities, the Lagrangian subproblem becomes a pairwise alignment problem, which can be solved efficiently by a dynamic programming approach. Due to a reformulation w.r.t. additionally introduced variables prior to relaxation we improve the convergence rate dramatically while at the same time being able to solve the Lagrangian problem efficiently. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem. Furthermore, the quality of the alignments is among the best computed so far.     

An integrated strategy for a production planning and warehouse layout problem: Modeling and solution approaches

We study a real-world production warehousing case, where the company always faces the challenge to find available space for its products and to manage the items in the warehouse. To resolve the problem, an integrated strategy that combines warehouse layout with the capacitated lot-sizing problem is presented, which have been traditionally treated separately in the existing literature. We develop a mixed integer linear programming model to formulate the integrated optimization problem with the objective of minimizing the total cost of production and warehouse operations. The problem with real data is a large-scale instance that is beyond the capability of optimization solvers. A novel Lagrangian relax-and-fix heuristic approach and its variants are proposed to solve the large-scale problem. The preliminary numerical results from the heuristic approaches are reported.     

Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks

We consider the problems of minimum-cost design and augmentation of directed network clusters that have diameter 2 and maintain the same diameter after the deletion of up to R elements (nodes or arcs) anywhere in the cluster. The property of a network to maintain not only the overall connectivity, but also the same diameter after the deletion of multiple nodes/arcs is referred to as strong attack tolerance. This paper presents the proof of NP-completeness of the decision version of the problem, derives tight theoretical bounds, as well as develops a heuristic algorithm for the considered problems, which are extremely challenging to solve to optimality even for small networks. Computational experiments suggest that the proposed heuristic algorithm does identify high-quality near-optimal solutions; moreover, in the special case of undirected networks with identical arc construction costs, the algorithm provably produces an exact optimal solution to strongly attack-tolerant two-hop network design problem, regardless of the network size.     

An upper bound on the minimal total cost of the transportation problem with varying demands and supplies

In general cases, to find the exact upper bound on the minimal total cost of the transportation problem with varying demands and supplies is an NP-hard problem. In literature, there are only two approaches with several shortcomings to solve the problem. In this paper, the problem is formulated as a bi-level programming model, and proven to be solvable in a polynomial time if the sum of the lower bounds for all the supplies is no less than the sum of the upper bounds for all the demands; and a heuristic algorithm named TPVDS-A based on genetic algorithm is developed as an efficient and robust solution method of the model. Computational experiments on benchmark and new randomly generated instances show that the TPVDS-A algorithm outperforms the two existing approaches.     

The maximum dispersion problem

In the maximum dispersion problem, a given set of objects has to be partitioned into a number of groups. Each object has a non-negative weight and each group has a target weight, which may be different for each group. In addition to meeting the target weight of each group, all objects assigned to the same group should be as dispersed as possible with respect to some distance measure between pairs of objects. Potential applications for this problem come from such diverse fields as the problem of creating study groups or the design of waste collection systems. We develop and compare two different (mixed-) integer linear programming formulations for the problem. We also study a specific relaxation that enables us to derive tight bounds that improve the effectiveness of the formulations. Thereby, we obtain an upper bound by finding in an auxiliary graph subsets of given size with minimal diameter. A lower bound is derived based on the relation of the optimal solution of the relaxation to the chromatic number of a series of auxiliary graphs. Finally, we propose an exact solution scheme for the maximum dispersion problem and present extensive computational experiments to assess its efficiency.     

Applications and Implementation A SEPARABLE PROGRAMMING APPROACH TO EXPECTED COVERAGE: AN APPLICATION TO AMBULANCE LOCATION

The maximum expected covering location problem (MEXCLP) is reformulated using a separable programming approach. The resulting formulation—nonlinear maximum expected covering location problem (NMEXCLP)—guarantees optimality and also solves more quickly than previous heuristic approaches. NMEXCLP allows two important extensions. First, minor formulation changes allow the specification of the minimum number of times each node is to be covered in order to satisfy expected coverage criteria. Second, coverage matrices can be constructed that consider two different types of coverage simultaneously. Both extensions are useful for ambulance location problems and are demonstrated in that setting.     

Adapting for Innovation: Including Divestitures in the Debate

Existing literature argues that divested units are unwanted and poor performers - yet evidence suggests that companies do divest well performing units, and often retain a relationship with them, especially in the quest for innovation. This article presents an exploratory case study to examine how a company structures the divestiture of an innovative unit and how it can benefit from the innovation the unit generates. The analysis focuses on how an established company can use divestiture as a strategy to enhance the innovation of its units, and capture its value, by structuring, maintaining and nurturing a special relationship with the unbundled unit. Under new organizational arrangement, resources can be transferred from the parent to the unit, while the parent retains access to the innovation developed within the unit. This study proposes a framework that offers corporate change agents and strategists a new perspective on how to integrate innovation and corporate strategy.     

Multi-time scale Markov decision process approach to strategic network growth of reverse supply chains

This paper addresses a complex set of decisions that surround the growth over time of reverse supply chain networks that collect used products for reuse, refurbishment, and/or recycling by processors. The collection network growth problem is decomposed into strategic, tactical and operational problems. This paper focuses on the strategic problem which is to determine how to allocate capital budget resource effectively to grow the network to meet long term collection targets and collection cost constraints. We model the strategic problem as a Markov decision process which can also be posed as multi-time scale Markov decision problem. The recruitment problem in a tactical level appears as a sub-problem for the strategic model. Using dynamic programming, linear programming and Q-Learning approaches, an heuristic is implemented to solve realistically sized problems. A numerical study demonstrates that the heuristic can obtain a good solution for the large-scale problem in reasonable time which is not possible when trying to obtain the optimal solution with the exact DP approach.