Benefit-of-the-doubt aggregation and the diet problem

In this note we show that the diet problem and the benefit-of-the-doubt (BoD) aggregation are linear programming duals. That is, the primal (dual) formulation of the diet problem is equivalent to the dual (primal) formulation of the BoD model as long as food prices are set equal to one. In addition, we show that the diet problem and the inverted BoD model are linear programming equivalent as long as the nutritional requirements are set equal to one.     

Coordinated deterministic dynamic demand lot-sizing problem: A review of models and algorithms

Due to their importance in industry and mathematical complexity, dynamic demand lot-sizing problems are frequently studied. In this article, we consider coordinated lot-size problems, their variants and exact and heuristic solutions approaches. The problem class provides a comprehensive approach for representing single and multiple items, coordinated and uncoordinated setup cost structures, and capacitated and uncapacitated problem characteristics. While efficient solution approaches have eluded researchers, recent advances in problem formulation and algorithms are enabling large-scale problems to be effectively solved. This paper updates a 1988 review of the coordinated lot-sizing problem and complements recent reviews on the single-item lot-sizing problem and the capacitated lot-sizing problem. It provides a state-of-the-art review of the research and future research projections. It is a starting point for anyone conducting research in the deterministic dynamic demand lot-sizing field.     

Vendor managed inventory in tramp shipping

This paper introduces a new problem to the OR community that combines traditional tramp shipping with a vendor managed inventory (VMI) service. Such a service may replace the more traditional contract of affreightment (COA) which for decades has been the standard agreement between a tramp shipping company and a charterer. We present a mathematical formulation describing the routing and scheduling problem faced by a tramp shipping company that offers a VMI service to its customers. The problem is formulated as an arc-flow model, and is then reformulated as a path-flow model which is solved using a hybrid approach that combines branch-and-price with a priori path-generation. To solve larger, and more realistic, instances we present a heuristic path-generation algorithm. Computational experiments show that the heuristic approach is much faster than the exact method, with insignificant reductions in solution quality. Further, we investigate the economic impact of introducing a VMI service, by comparing the results obtained with the new model with results obtained by solving the traditional routing and scheduling problem faced by tramp shipping companies using COA. The computational results show that it is possible to substantially increase supply chain profit and efficiency by replacing the traditional COAs with VMI services.     

An exact semidefinite programming approach for the max-mean dispersion problem

This paper proposes an exact algorithm for the Max-Mean dispersion problem (\(Max-Mean DP\)), an NP-Hard combinatorial optimization problem whose aim is to select the subset of a set such that the average distance between elements is maximized. The problem admits a natural non-convex quadratic fractional formulation from which a semidefinite programming (SDP) relaxation can be derived. This relaxation can be tightened by means of a cutting plane algorithm which iteratively adds the most violated triangular inequalities. The proposed approach embeds the SDP relaxation and the cutting plane algorithm into a branch and bound framework to solve \(Max-Mean DP\) instances to optimality. Computational experiments show that the proposed method is able to solve to optimality in reasonable time instances with up to 100 elements, outperforming other alternative approaches.     

Discrete parallel machine makespan ScheLoc problem

Scheduling–Location (ScheLoc) problems integrate the separate fields of scheduling and location problems. In ScheLoc problems the objective is to find locations for the machines and a schedule for each machine subject to some production and location constraints such that some scheduling objective is minimized. In this paper we consider the discrete parallel machine makespan ScheLoc problem where the set of possible machine locations is discrete and a set of n jobs has to be taken to the machines and processed such that the makespan is minimized. Since the separate location and scheduling problem are both \(\mathcal {NP}\)-hard, so is the corresponding ScheLoc problem. Therefore, we propose an integer programming formulation and different versions of clustering heuristics, where jobs are split into clusters and each cluster is assigned to one of the possible machine locations. Since the IP formulation can only be solved for small scale instances we propose several lower bounds to measure the quality of the clustering heuristics. Extensive computational tests show the efficiency of the heuristics.     

The supplier selection problem with quantity discounts and truckload shipping

To minimize procurement expenditures both purchasing and transportation costs need to be considered. We study a procurement setting in which a company needs to purchase a number of products from a set of suppliers to satisfy customer demand. The suppliers offer total quantity discounts and transportation costs are based on truckload shipping rates. The goal is to select a set of suppliers so as to satisfy product demand at minimal total costs. The resulting optimization problem is strongly NP-hard. We develop integer programming based heuristics to solve the problem. Extensive computational experiments demonstrate the efficacy of the proposed heuristics and provide insight into the impact of instance characteristics on effective procurement strategies.     

Trip packing in petrol stations replenishment

This paper considers a generalized version of the trip packing problem that we encountered as a sub-problem of the petrol stations replenishment problem. In this version we have to assign a number of trips to a fleet composed of a limited number of non-identical tank-trucks. Each trip has a specific duration, working time of vehicles is limited and the net revenue of each trip depends on the truck used. The paper provides a mathematical formulation of the problem and proposes some construction, improvement and neighbourhood search solution heuristics. A set of benchmark problem instances is created in a way that reflects real-life situations and used to analyse the performance of the proposed heuristics. A real-life case is also used to further assess the proposed heuristics.     

A robust branch-and-cut approach for the minimum-energy symmetric network connectivity problem

This paper considers the minimum-energy symmetric network connectivity problem (MESNC) in wireless sensor networks. The aim of the MESNC is to assign transmission power to each sensor node such that the resulting network, using only bidirectional links, is connected and the total energy consumption is minimized. We first present two new models of this problem and then propose new branch-and-cut algorithms. Based on an existing formulation, we present the first model by introducing additional constraints. These additional constraints allow us to relax certain binary variables to continuous ones and thus to reduce significantly the number of binary variables. Our second model strengthens the first one by adding an exponential number of lifted directed-connectivity constraints. We present two branch-and-cut procedures based on these proposed improvements. The computational results are reported and show that our approaches, using the proposed formulations, can efficiently solve instances with up to 120 nodes, which significantly improve our ability to solve much larger instances in comparison with other exact algorithms in the literature.     

The impact of training on the formulation of ill-structured problems

Problem structuring heuristics and creative thinking techniques have been advanced as useful approaches for solving ill-structured problems. Unfortunately, little controlled experimentation has been done to test the effectiveness of these techniques. This paper describes an experiment in which the effects of training in the use of a problem-structuring heuristic and creative thinking on the quality and quantity of problem statements are investigated. The experiment illustrates that such training does have a positive impact on problem formulation quality and quantity.     

Vehicle routing–scheduling for municipal waste collection system under the “Keep Trash off the Ground” policy

This paper investigates the waste collection problem and characterizes the problem as a set-covering and vehicle routing problem (VRP) complicated by inter-arrival time constraints. The study proposes a bi-level optimization formulation to model the split delivery VRP with multiple trips to determine the minimum-distance route. The first stage optimally plans the collection points that cover all residential blocks. The second stage applies a heuristics method to solve the minimum vehicles used and minimum distance traveled for collecting residential waste. This research contributes to model this period VRP and to introduce the heuristics method to solve the problem efficiently. The study is important in laying the groundwork for understanding the possibility of improving the service level of municipal solid waste collection.     

Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios

We consider the design of a multicommodity flow network, in which point-to-point demands are routed across the network subject to link capacity restrictions. Such a design must build enough capacity and diverse routing paths through the network to ensure that feasible multicommodity flows continue to exist, even when components of the network fail. In this paper, we examine several methodologies to optimally design a minimum-cost survivable network that continues to support a multicommodity flow under any of a given set of failure scenarios, where each failure scenario consists of the simultaneous failure of multiple arcs. We begin by providing a single extensive form mixed-integer programming formulation for this problem, along with a Benders decomposition algorithm as an alternative to the extensive form approach. We next investigate strategies to improve the performance of the algorithm by augmenting the master problem with several valid inequalities such as cover constraints, connectivity constraints, and path constraints. For the smallest instances (eight nodes, 10 origin–destination pairs, and 10 failure scenarios), the Benders implementation consumes only 10% of the time required by the mixed-integer programming formulation, and our best augmentation strategy reduces the solution time by another 50%. For medium- and large-sized instances, the extensive form problem fails to terminate within 2 h on any instance, while our decomposition algorithms provide optimal solutions on all but two problem instances.     

Exact and heuristic algorithms for the circle cutting problem in the manufacturing industry of electric motors

Circular blanks are often cut from silicon steel plates to make stators and rotors of electric motors. The shearing and punching processes are often used to cut the blanks. First a guillotine shear cuts the plate into strips, and then a stamping press cuts the blanks from the strips. The unconstrained circle cutting problem discussed is the problem of cutting from a rectangular plate a number of circular blanks of given diameters and values, so as to maximize the value of blanks cut, where the shearing and punching processes are applied. Two algorithms based on dynamic programming are presented for generating cutting patterns, one is an exact algorithm and the other is a heuristic one. The computational results indicate that the exact algorithm is adequate for small and middle scale problems, the heuristic algorithm is much more time efficient, and can generate cutting patterns close to optimal.     

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.     

Optimal solutions to minimum total energy broadcasting problem in wireless ad hoc networks

In this paper, we present three schemes to solve minimum total energy broadcasting problem in wireless ad hoc networks based on an efficient IP (integer programming) subproblem technique. Due to its NP-hardness, many heuristics have been studied. However, the heuristics in the literature suffer from coarse performance ratio. It is important to have knowledge of the optimal solution structure in order to develop more efficient heuristics and algorithms. We present one IP formulation and two iterative algorithms which make use of relaxed IP's to solve subproblems. The computational results show that our approaches outperform other techniques in the literature. Research is partially supported by NSF and Air Force grants.     

Logic-based Benders decomposition for an inventory-location problem with service constraints

We study an integrated inventory-location problem with service requirements faced by an aerospace company in designing its service parts logistics network. Customer demand is Poisson distributed and the service levels are time-based leading to highly non-linear, stochastic service constraints and a nonlinear, mixed-integer optimization problem. Unlike previous work in the literature, which propose approximations for the nonlinear constraints, we present an exact solution methodology using logic-based Benders decomposition. We decompose the problem to separate the location decisions in the master problem from the inventory decisions in the subproblem. We propose a new family of valid cuts and prove that the algorithm is guaranteed to converge to optimality. This is the first attempt to solve this type of problem exactly. Then, we present a new restrict-and-decompose scheme to further decompose the Benders master problem by part. We test on industry instances as well as random instances. Using the exact algorithm and restrict-and-decompose scheme we are able to solve industry instances with up to 60 parts within reasonable time, while the maximum number of parts attempted in the literature is 5.     

Approximate and Exact Algorithms for Constrained (Un) Weighted Two-dimensional Two-staged Cutting Stock Problems

In this paper we propose two algorithms for solving both unweighted and weighted constrained two-dimensional two-staged cutting stock problems. The problem is called two-staged cutting problem because each produced (sub)optimal cutting pattern is realized by using two cut-phases. In the first cut-phase, the current stock rectangle is slit down its width (resp. length) into a set of vertical (resp. horizontal) strips and, in the second cut-phase, each of these strips is taken individually and chopped across its length (resp. width).First, we develop an approximate algorithm for the problem. The original problem is reduced to a series of single bounded knapsack problems and solved by applying a dynamic programming procedure. Second, we propose an exact algorithm tailored especially for the constrained two-staged cutting problem. The algorithm starts with an initial (feasible) lower bound computed by applying the proposed approximate algorithm. Then, by exploiting dynamic programming properties, we obtain good lower and upper bounds which lead to significant branching cuts. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approximate and exact approaches.     

Assortment optimisation problem: A distribution-free approach

Assortment optimisation is a critical decision that is regularly made by retailers. The decision involves a trade-off between offering a larger assortment of products but smaller inventories of each product and offering a smaller number of varieties with more inventory of each product. We propose a robust, distribution-free formulation of the assortment optimisation problem such that the assortment and inventory levels can be jointly optimised without making specific assumptions on the demand distributions of each product. We take a max-min approach to the problem that provides a guaranteed lower bound to the expected profit when only the mean and variance of the demand distribution are known. We propose and test three heuristic algorithms that provide solutions in O(nlog (n)) time and identify two cases where one of the heuristics is guaranteed to return optimal policies. Through numerical studies, we demonstrate that one of the heuristics performs extremely well, with an average optimality gap of 0.07% when simulated under varying conditions. We perform a sensitivity analysis of product and store demand attributes on the performance of the heuristic. Finally, we extend the problem by including maximum cardinality constraints on the assortment size and perform numerical studies to test the performance of the heuristics.     

A multi-stage stochastic supply network design problem with financial decisions and risk management

In this paper, a multi-period supply chain network design problem is addressed. Several aspects of practical relevance are considered such as those related with the financial decisions that must be accounted for by a company managing a supply chain. The decisions to be made comprise the location of the facilities, the flow of commodities and the investments to make in alternative activities to those directly related with the supply chain design. Uncertainty is assumed for demand and interest rates, which is described by a set of scenarios. Therefore, for the entire planning horizon, a tree of scenarios is built. A target is set for the return on investment and the risk of falling below it is measured and accounted for. The service level is also measured and included in the objective function. The problem is formulated as a multi-stage stochastic mixed-integer linear programming problem. The goal is to maximize the total financial benefit. An alternative formulation which is based upon the paths in the scenario tree is also proposed. A methodology for measuring the value of the stochastic solution in this problem is discussed. Computational tests using randomly generated data are presented showing that the stochastic approach is worth considering in these types of problems.     

Using branch-and-price approach to solve the directed network design problem with relays

We present node-arc and arc-path formulations, and develop a branch-and-price approach for the directed network design problem with relays (DNDR). The DNDR problem can be used to model many network design problems in transportation, service, and telecommunication system, where relay points are necessary. The DNDR problem consists of introducing a subset of arcs and locating relays on a subset of nodes such that in the resulting network, the total cost (arc cost plus relay cost) is minimized, and there exists a directed path linking the origin and destination of each commodity, in which the distances between the origin and the first relay, any two consecutive relays, and the last relay and the destination do not exceed a predefined distance limit. With the node-arc formulation, we can directly solve small DNDR instances using mixed integer programming solver. With the arc-path formulation, we design a branch-and-price approach, which is a variant of branch-and-bound with bounds provided by solving linear programs using column generation at each node of the branch-and-bound tree. We design two methods to efficiently price out columns and present computational results on a set of 290 generated instances. Results demonstrate that our proposed branch-and-price approach is a computationally efficient procedure for solving the DNDR problem.