Exact approaches for the directed network design problem with relays

We study the directed network design problem with relays (DNDPR) whose aim is to construct a minimum cost network that enables the communication of a given set of origin-destination pairs. Thereby, expensive signal regeneration devices need to be placed to cover communication distances exceeding a predefined threshold. Applications of the DNDPR arise in telecommunications and transportation. We propose two new integer programming formulations for the DNDPR. The first one is a flow-based formulation with a pseudo-polynomial number of variables and constraints and the second is a cut-based formulation with an exponential number of constraints. Fractional distance values are handled efficiently by augmenting both models with an exponentially-sized set of infeasible path constraints. We develop branch-and-cut algorithms and also consider valid inequalities to strengthen the obtained dual bounds and to speed up convergence. The results of our extensive computational study on diverse sets of benchmark instances show that our algorithms outperform the previous state-of-the-art method based on column generation.     

Exact approaches for the pickup and delivery problem with loading cost

In this paper, we propose a branch-and-cut algorithm and a branch-and-price algorithm to solve the pickup and delivery problem with loading cost (PDPLC), which is a new problem derived from the classic pickup and delivery problem (PDP) by considering the loading cost in the objective function. Applications of the PDPLC arise in healthcare transportation where the objective function is customer-centric or service-based. In the branch-and-price algorithm, we devise an ad hoc label-setting algorithm to solve the pricing problem and employ the bounded bidirectional search strategy to accelerate the label-setting algorithm. The proposed algorithms were tested on a set of instances generated by a common data generator in the literature. The computational results showed that the branch-and-price algorithm outperformed the branch-and-cut algorithm by a large margin, and can solve instances with 40 requests to optimality in a reasonable time frame.     

The bike sharing rebalancing problem: Mathematical formulations and benchmark instances

Bike sharing systems offer a mobility service whereby public bicycles, located at different stations across an urban area, are available for shared use. These systems contribute towards obtaining a more sustainable mobility and decreasing traffic and pollution caused by car transportation. Since the first bike sharing system was installed in Amsterdam in 1965, the number of such applications has increased remarkably so that hundreds of systems are now operating all over the world.In a bike sharing system, users can take a bicycle from a station, use it to perform a journey and then leave it at a station, not necessarily the same one of departure. This behavior typically leads to a situation in which some stations become full and others are empty. Hence, a balanced system requires the redistribution of bicycles among stations.In this paper, we address the Bike sharing Rebalancing Problem (BRP), in which a fleet of capacitated vehicles is employed in order to re-distribute the bikes with the objective of minimizing total cost. This can be viewed as a special one-commodity pickup-and-delivery capacitated vehicle routing problem. We present four mixed integer linear programming formulations of this problem. It is worth noting that the proposed formulations include an exponential number of constraints, hence, tailor-made branch-and-cut algorithms are developed in order to solve them.The mathematical formulations of the BRP were first computationally tested using data obtained for the city of Reggio Emilia, Italy. Our computational study was then extended to include bike sharing systems from other parts of the world. The information derived from the study was used to build a set of benchmark instances for the BRP which we made publicly available on the web. Extensive experimentation of the branch-and-cut algorithms presented in this paper was carried out and an interesting computational comparison of the proposed mathematical formulations is reported. Finally, several insights on the computational difficulty of the problem are highlighted.     

Benders decomposition for set covering problems

This paper describes Benders decomposition approaches to optimally solve set covering problems “ almost” satisfying the consecutive ones property. The decompositions are based on the fact that set covering problems with consecutive ones property have totally unimodular coefficient matrices. Given a binary matrix, a totally unimodular matrix is enforced by filling up every row with ones between its first and its last non-zero entries. The resulting mistake is handled by introducing additional integer variables whose number depends on the reordering of the columns of the given matrix. This leads us to consider the consecutive block minimization problem. Two cutting plane algorithms are proposed and run on a large set of benchmark instances. The results obtained show that the cutting plane algorithms outperform an existing tree search method designed exclusively for such instances.     

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.     

Fix-and-optimize and variable neighborhood search approaches for multi-level capacitated lot sizing problems

In this paper, a new fix-and-optimize (FO) approach is proposed for two dynamic multi-level capacitated lot sizing problems (MLCLSP), the MLCLSP without setup carryover and the MLCLSP with setup carryover. Given an MIP model of a lot sizing problem, the approach iteratively solves a series of sub-problems of the model until no better solution can be found. Each sub-problem re-optimizes a subset of binary decision variables determined based on the interrelatedness of binary variables in the constraints of the model, while fixing the values of the other binary variables. Based on the FO, a variable neighbourhood search (VNS) approach for the MLCLSP without setup carryover is also developed, which can further improve the solution obtained by the FO by diversifying the search space. Numerical experiments on benchmark instances show that both our FO and VNS approaches can obtain a better solution for most instances compared with that found by the fix-and-optimize approach proposed by Helber and Sahling (International Journal of Production Economics 2010;123:247–256).     

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.     

Two-level network design with intermediate facilities: An application to electrical distribution systems

We consider the two-level network design problem with intermediate facilities. This problem consists of designing a minimum cost network respecting some requirements, usually described in terms of the network topology or in terms of a desired flow of commodities between source and destination vertices. Each selected link must receive one of two types of edge facilities and the connection of different edge facilities requires a costly and capacitated vertex facility. We propose a hybrid decomposition approach which heuristically obtains tentative solutions for the vertex facilities number and location and use these solutions to limit the computational burden of a branch-and-cut algorithm. We test our method on instances of the power system secondary distribution network design problem. The results show that the method is efficient both in terms of solution quality and computational times.     

A genetic algorithm-based decomposition approach to solve an integrated equipment-workforce-service planning problem

We develop a new genetic algorithm to solve an integrated Equipment-Workforce-Service Planning problem, which features extremely large scales and complex constraints. Compared with the canonical genetic algorithm, the new algorithm is innovative in four respects: (1) The new algorithm addresses epistasis of genes by decomposing the problem variables into evolutionary variables, which evolve with the genetic operators, and the optimization variables, which are derived by solving corresponding optimization problems. (2) The new algorithm introduces the concept of Capacity Threshold and calculates the Set of Efficient and Valid Equipment Assignments to preclude unpromising solution spaces, which allows the algorithm to search much narrowed but promising solution spaces in a more efficient way. (3) The new algorithm modifies the traditional genetic crossover and mutation operators to incorporate the gene dependency in the evolutionary procedure. (4) The new algorithm proposes a new genetic operator, self-evolution, to simulate the growth procedure of an individual in nature and use it for guided improvements of individuals. The new genetic algorithm design is proven very effective and robust in various numerical tests, compared to the integer programming algorithm and the canonical genetic algorithm. When the integer programming algorithm is unable to solve the large-scale problem instances or cannot provide good solutions in acceptable times, and the canonical genetic algorithm is incapable of handling the complex constraints of these instances, the new genetic algorithm obtains the optimal or close-to-optimal solutions within seconds for instances as large as 84 million integer variables and 82 thousand constraints.     

Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem

In a previous work we proposed a variable fixing heuristics for the 0-1 Multidimensional knapsack problem (01MDK). This approach uses fractional optima calculated in hyperplanes which contain the binary optimum. This algorithm obtained best lower bounds on the OR-Library benchmarks. Although it is very attractive in terms of results, this method does not prove the optimality of the solutions found and may fix variables to a non-optimal value. In this paper, we propose an implicit enumeration based on a reduced costs analysis which tends to fix non-basic variables to their exact values. The combination of two specific constraint propagations based on reduced costs and an efficient enumeration framework enable us to fix variables on the one hand and to prune significantly the search tree on the other hand. Experimentally, our work provides two main contributions: (1) we obtain several new optimal solutions on hard instances of the OR-Library and (2) we reduce the bounds of the number of items at the optimum on several harder instances.     

A Dynamic Disaggregation Approach to Approximate Linear Programs for Network Revenue Management

The linear programming approach to approximate dynamic programming has received considerable attention in the recent network revenue management (RM) literature. A major challenge of the approach lies in solving the resulting approximate linear programs (ALPs), which often have a huge number of constraints and/or variables. Starting from a recently developed compact affine ALP for network RM, we develop a novel dynamic disaggregation algorithm to solve the problem, which combines column and constraint generation and exploits the structure of the underlying problem. We show that the formulation can be further tightened by considering structural properties satisfied by an optimal solution. We prove that the sum of dynamic bid‐prices across resources is concave over time. We also give a counterexample to demonstrate that the dynamic bid‐prices of individual resources are not concave in general. Numerical experiments demonstrate that dynamic disaggregation is often orders of magnitude faster than existing algorithms in the literature for problem instances with and without choice. In addition, adding the concavity constraints can further speed up the algorithm, often by an order of magnitude, for problem instances with choice.     

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.     

Linear solution schemes for Mean-SemiVariance Project portfolio selection problems: An application in the oil and gas industry

We study the Mean-SemiVariance Project (MSVP) portfolio selection problem, where the objective is to obtain the optimal risk-reward portfolio of non-divisible projects when the risk is measured by the semivariance of the portfolio׳s Net-Present Value (NPV) and the reward is measured by the portfolio׳s expected NPV. Similar to the well-known Mean-Variance portfolio selection problem, when integer variables are present (e.g., due to transaction costs, cardinality constraints, or asset illiquidity), the MSVP problem can be solved using Mixed-Integer Quadratic Programming (MIQP) techniques. However, conventional MIQP solvers may be unable to solve large-scale MSVP problem instances in a reasonable amount of time. In this paper, we propose two linear solution schemes to solve the MSVP problem; that is, the proposed schemes avoid the use of MIQP solvers and only require the use of Mixed-Integer Linear Programming (MILP) techniques. In particular, we show that the solution of a class of real-world MSVP problems, in which project returns are positively correlated, can be accurately approximated by solving a single MILP problem. In general, we show that the MSVP problem can be effectively solved by a sequence of MILP problems, which allow us to solve large-scale MSVP problem instances faster than using MIQP solvers. We illustrate our solution schemes by solving a real MSVP problem arising in a Latin American oil and gas company. Also, we solve instances of the MSVP problem that are constructed using data from the PSPLIB library of project scheduling problems.     

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.     

A multi-compartment vehicle routing problem arising in the collection of olive oil in Tunisia

We introduce, model and solve to optimality a rich multi-product, multi-period and multi-compartment vehicle routing problem with a required compartment cleaning activity. This real-life application arises in the olive oil collection process in Tunisia, where regional collection offices dispose of a fleet of vehicles to collect one or several grades of olive oil from a set of producers. For each grade, the quantity offered by a producer changes dynamically over the planning horizon. We first provide a mathematical formulation of the problem, along with a set of known and new valid inequalities. We then propose an exact branch-and-cut algorithm to solve the problem. We evaluate the performance of the algorithm on real data sets under different transportation scenarios to demonstrate to our industrial partner the advantages of using multi-compartment vehicles.     

Integrated Ant Colony and Tabu Search approach for time dependent vehicle routing problems with simultaneous pickup and delivery

Today manufacturers have become much more concerned with the coordination of both manufacturing (of new products) and recycling (of reusable resources) operations. This requires simultaneous scheduling of both forward and reverse flows of goods over a supply chain network. This paper studies time dependent vehicle routing problems with simultaneous pickup and delivery (TD-VRPSPD). We formulate this problem as a mixed integer programming model, where the time step function is used to calculate the travel time. To efficiently solve this complex problem, we develop a hybrid algorithm that integrates both Ant Colony System (ACS) and Tabu Search (TS) algorithms. Our algorithm uses the pheromones, travel time and vehicle residual loading capacity as a factor structure according to the characteristics of TD-VRPSPD. In our computational experiments, 56 groups of benchmark instances are used to evaluate the performance of our hybrid algorithm. In addition, we compare the performance of our hybrid algorithm with those of individual ACS and TS algorithms. The computational results suggest that our hybrid algorithm outperform stand-alone ACS and the TS algorithms.     

A sustainable supply chain network considering lot sizing with quantity discounts under disruption risks: centralized and decentralized models

This study proposes a framework for the main parties of a sustainable supply chain network considering lot-sizing impact with quantity discounts under disruption risk among the first studies. The proposed problem differs from most studies considering supplier selection and order allocation in this area. First, regarding the concept of the triple bottom line, total cost, environmental emissions, and job opportunities are considered to cover the criteria of sustainability. Second, the application of this supply chain network is transformer production. Third, applying an economic order quantity model lets our model have a smart inventory plan to control the uncertainties. Most significantly, we present both centralized and decentralized optimization models to cope with the considered problem. The proposed centralized model focuses on pricing and inventory decisions of a supply chain network with a focus on supplier selection and order allocation parts. This model is formulated by a scenario-based stochastic mixed-integer non-linear programming approach. Our second model focuses on the competition of suppliers based on the price of products with regard to sustainability. In this regard, a Stackelberg game model is developed. Based on this comparison, we can see that the sum of the costs for both levels is lower than the cost without the bi-level approach. However, the computational time for the bi-level approach is more than for the centralized model. This means that the proposed optimization model can better solve our problem to achieve a better solution than the centralized optimization model. However, obtaining this better answer also requires more processing time. To address both optimization models, a hybrid bio-inspired metaheuristic as the hybrid of imperialist competitive algorithm (ICA) and particle swarm optimization (PSO) is utilized. The proposed algorithm is compared with its individuals. All employed optimizers have been tuned by the Taguchi method and validated by an exact solver in small sizes. Numerical results show that striking similarities are observed between the results of the algorithms, but the standard deviations of PSO and ICA–PSO show better behavior. Furthermore, while PSO consumes less time among the metaheuristics, the proposed hybrid metaheuristic named ICA–PSO shows more time computations in all small instances. Finally, the provided results confirm the efficiency and the performance of the proposed framework and the proposed hybrid metaheuristic algorithm.

     

A market regulation bilevel problem: A case study of the Mexican petrochemical industry

In this paper, a bilevel programming model is proposed to study a problem of market regulation through government intervention. One of the main characteristics of the problem herein analyzed is that the government monopolizes the raw material in one industry, and competes in another industry with private firms for the production of commodities. Under this scheme, the government controls a state-owned firm to balance the market; that is, to minimize the difference between the produced and demanded commodities. On the other hand, a regulatory organization that coordinates private firms aims to maximize the total profit by deciding the amount of raw material bought from the a state-owned firm. Two equivalent single-level reformulations are proposed to solve the problem. The first reformulation is based on the strong duality condition of the lower level and results in a continuous non-linear model. The second reformulation resorts to the complementarity slackness optimality constraints yielding a mixed-integer linear model. Additionally, three heuristic algorithms are designed to obtain good-quality solutions with low computational effort. In this problem, the feasible region of the dual problem associated to the follower is independent from the leader’s decision. Therefore, the proposed heuristics exploit this particular characteristic of the bilevel model. Moreover, the third heuristic hybridizes the other two algorithms to enhance its performance. Extensive computational experimentation is carried out to measure the efficiency of the proposed solution methodologies. A case study based on the Mexican petrochemical industry is presented. Additional instances generated from the case study are considered to validate the robustness of the proposed heuristic algorithms. Numerical results indicate that the hybrid algorithm outperforms the other two heuristics. However, all of them demonstrate to be good alternatives for solving the problem. Additionally, optimal solutions of all the instances are obtained by using good quality solutions (given by the hybrid algorithm) as initial solutions when solving the second reformulation via a general purpose solver.     

Exact solution method to solve large scale integer quadratic multidimensional knapsack problems

In this paper we develop a branch-and-bound algorithm for solving a particular integer quadratic multi-knapsack problem. The problem we study is defined as the maximization of a concave separable quadratic objective function over a convex set of linear constraints and bounded integer variables. Our exact solution method is based on the computation of an upper bound and also includes pre-procedure techniques in order to reduce the problem size before starting the branch-and-bound process. We lead a numerical comparison between our method and three other existing algorithms. The approach we propose outperforms other procedures for large-scaled instances (up to 2000 variables and constraints). A extended abstract of this paper appeared in LNCS 4362, pp. 456–464, 2007.     

A Branch and Bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation

Let \((MQP)\) be a general mixed-integer quadratic program that consists of minimizing a quadratic function \(f(x) = x^TQx +c^Tx\) subject to linear constraints. Our approach to solve \((MQP)\) is first to consider an equivalent general mixed-integer quadratic problem. This equivalent problem has additional variables \(y_{ij}\) , additional quadratic constraints \(y_{ij}=x_ix_j\) , a convex objective function, and a set of valid inequalities. Contrarily to the reformulation proposed in Billionnet et al. (Math Program 131(1):381–401, 2012), the equivalent problem cannot be directly solved by a standard solver. Here, we propose a new Branch and Bound process based on the relaxation of the non-convex constraints \(y_{ij}=x_ix_j\) to solve \((MQP)\) . Computational experiences are carried out on pure- and mixed-integer quadratic instances. The results show that the solution time of most of the considered instances with up to 60 variables is improved by our Branch and Bound algorithm in comparison with the approach of Billionnet et al. (2012) and with the general mixed-integer nonlinear solver BARON (Sahinidis and Tawarmalani, Global optimization of mixed-integer nonlinear programs, user’s manual, 2010).