Efficient Benders decomposition for distance-based critical node detection problem

This paper addresses the critical node detection problem which seeks a subset of nodes for removal in order to maximize the disconnectivity of the residual graph with respect to a specific distance-based measure, namely the Wiener index. Such a measure is defined based on the all-pair shortest path distances in the residual graph so that the longer the total length of shortest paths, the greater the value of the disconnectivity measure. In the literature, a mixed integer linear programming model and an exact iterative-based method have been presented for this problem; however, both approaches become very time-consuming on graphs having large diameter and non-unit edge lengths. To overcome this shortcoming, in this paper, we present a new formulation for the problem and solve it by Benders decomposition algorithm. We improve the performance of Benders algorithm by several techniques (including analytical calculation of dual variables, generation of good-quality initial optimality cuts, considering master's optimality cuts as lazy constraints, etc.) to reduce the total running time. The extensive computational experiments on instances, taken from the literature or generated randomly, confirm the effectiveness of the new approaches.     

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.     

Benders decomposition for a strategic network design problem under NAFTA local content requirements

Global production and sourcing strategies of multinational corporations are strongly influenced by the increasing number of Free Trade Agreements (FTAs). Based on the special local content requirements of the North American Free Trade Agreement (NAFTA) for automotive goods, the impact on strategic network design decisions is investigated. The presented model explicitly integrates the different NAFTA legal options to calculate the local content for automotive goods. Furthermore, it considers the possibility to underachieve the local content requirement and to pay penalty duties for NAFTA cross-border deliveries instead. Plant fixed costs have a significant impact on the local content fulfillment and have to be allocated in accordance with the actual plant utilization and the different local content calculation options. Due to the resulting non-linearity of the mixed-integer program, a solution algorithm based on Benders decomposition is presented. In addition, we introduce multiple Benders cuts to improve the efficiency and applicability to real-world planning problems. Compared to piecewise linearization approaches, the run-time can be improved significantly. In a numerical study, the impact of local content requirements on the strategic network design is shown and the different NAFTA options to calculate the local content for automotive goods are compared with each other. Furthermore, computational experiments are performed to evaluate the applicability and efficiency of Benders decomposition.     

A set covering approach to bus stop location

This paper considers the problem of locating bus stops in the context of a set covering problem. Zero-one integer programming models are suggested for use in the location of bus stops on new routes and for use in the location of express bus stops on current routes. The models may be used to locate the minimum number of (express) bus stops required to ensure that no passenger need walk more than a specified distance to reach an (express) bus stop. A modified version of the model is presented which enables the router to locate a specified number of (express) bus stops in such a manner that the total distance walked by all boarders is minimized.     

Distance-d independent set problems for bipartite and chordal graphs

The paper studies a generalization of the Independent Set problem (IS for short). A distance- $d$ independent set for an integer $d\ge 2$ in an unweighted graph $G = (V, E)$ is a subset $S\subseteq V$ of vertices such that for any pair of vertices $u, v \in S$ , the distance between $u$ and $v$ is at least $d$ in $G$ . Given an unweighted graph $G$ and a positive integer $k$ , the Distance- $d$ Independent Set problem (D $d$ IS for short) is to decide whether $G$ contains a distance- $d$ independent set $S$ such that $|S| \ge k$ . D2IS is identical to the original IS. Thus D2IS is $\mathcal{NP}$ -complete even for planar graphs, but it is in $\mathcal{P}$ for bipartite graphs and chordal graphs. In this paper we investigate the computational complexity of D $d$ IS, its maximization version MaxD $d$ IS, and its parameterized version ParaD $d$ IS( $k$ ), where the parameter is the size of the distance- $d$ independent set: (1) We first prove that for any $\varepsilon >0$ and any fixed integer $d\ge 3$ , it is $\mathcal{NP}$ -hard to approximate MaxD $d$ IS to within a factor of $n^{1/2-\varepsilon }$ for bipartite graphs of $n$ vertices, and for any fixed integer $d\ge 3$ , ParaD $d$ IS( $k$ ) is $\mathcal{W}[1]$ -hard for bipartite graphs. Then, (2) we prove that for every fixed integer $d\ge 3$ , D $d$ IS remains $\mathcal{NP}$ -complete even for planar bipartite graphs of maximum degree three. Furthermore, (3) we show that if the input graph is restricted to chordal graphs, then D $d$ IS can be solved in polynomial time for any even $d\ge 2$ , whereas D $d$ IS is $\mathcal{NP}$ -complete for any odd $d\ge 3$ . Also, we show the hardness of approximation of MaxD $d$ IS and the $\mathcal{W}[1]$ -hardness of ParaD $d$ IS( $k$ ) on chordal graphs for any odd $d\ge 3$ .     

Modeling and optimizing an agro-supply chain considering different quality grades and storage systems for fresh products: a Benders decomposition solution approach

This paper proposes a mathematical model in the context of agro-supply chain management, considering specific characteristics of agro-products to assist purchase, storage, and transportation decisions. In addition, a new method for determining the required quality score of different types of products is proposed based on their loss factors and purchasing costs. The model aims to minimize total cost imposed by purchasing fresh products, opening warehouses, holding inventories, operational activities, and transportation. Two sets of examples, including small and medium-sized problems, are implemented by general algebraic modeling language (GAMS) software to evaluate the model. Then, Benders decomposition (BD) algorithm is applied to tackle the complexity of solving large-sized instances. The results of both GAMS and BD are compared in terms of objective function values and computational time to demonstrate the efficiency of the BD algorithm. Finally, the model is applied in a real case study involving an apple supply chain to obtain managerial insights.

     

Approximation hardness of edge dominating set problems

We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, MINIMUM EDGE DOMINATING SET and MINIMUM MAXIMAL MATCHING. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than . The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs. An extended abstract of this paper was accepted at the 14th Annual International Symposium on Algorithms and Computation, ISAAC 2003.     

Applications of sequential set partitioning: a set of technical information systems problems

Many problems that appear in different contexts are conceptually similar and so are amenable to solution by a common technique. Three such technical Information Systems (IS) problems are: (1) segmentation of computer programs; (2) attribute discretization for decision tree induction; and (3) design of hash tables in database systems. In this paper we show how each of these seemingly different problems can be formulated as a sequential (set) partitioning problem, and solved using a parametric linear programming (LP) procedure. This approach provides optimal solutions unlike previous solution approaches which were either greedy heuristics or limited to solving only a specific problem situation. Given the likelihood that other applications of the sequential partitioning problem exist in IS, the material presented here could be useful to other researchers in formulating the problem at an appropriate level of abstraction so that available optimal solution approaches can be identified. In addition to providing a common solution method, parametric LP frees the user from having to make premature decisions regarding the number of groups for the partition, and this decision can be delayed post solution.     

Solving constrained optimization problems by solution-based decomposition search

Solving constrained optimization problems (COPs) is a challenging task. In this paper we present a new strategy for solving COPs called solve and decompose (or \( S \& D\) for short). The proposed strategy is a systematic iterative depth-first strategy that is based on problem decomposition. \( S \& D\) uses a feasible solution of the COP, found by any exact method, to further decompose the original problem into a bounded number of subproblems which are considerably smaller in size. It also uses the value of the feasible solution as a bound that we add to the created subproblems in order to strengthen the cost-based filtering. Furthermore, the feasible solution is exploited in order to create subproblems that have more promise in finding better solutions which are explored in a depth-first manner. The whole process is repeated until we reach a specified depth where we do not decompose the subproblems anymore but we solve them to optimality using any exact method like Branch and Bound. Our initial results on two benchmark problems show that \( S \& D\) may reach improvements of up to three orders of magnitude in terms of runtime when compared to Branch and Bound.     

基于Benders分解算法的跨区互联电力系统协调规划模型

研究跨区互联电力系统的协调规划,对于提高投资效率实现更大范围的资源配置具有较强现实意义。本文首先描述多区域电力系统扩张规划问题,并建立多区域扩张规划模型,旨在寻求最优的扩容方案,以最小投入来满足多区域电力系统负荷增长需求;其次,采用Benders分解算法将多区域扩张规划问题分解为一个规划主问题和一个运行子问题,通过主子问题之间的迭代求解,获得最终的最优解;最后,对某个典型的包含7个区域的多区域电力系统进行模拟仿真,验证了本文所构建模型及算法的有效性。     

Online covering salesman problem

Given a graph \(G=(V,E,D,W)\), the generalized covering salesman problem (CSP) is to find a shortest tour in G such that each vertex \(i\in D\) is either on the tour or within a predetermined distance L to an arbitrary vertex \(j\in W\) on the tour, where \(D\subset V\),\(W\subset V\). In this paper, we propose the online CSP, where the salesman will encounter at most k blocked edges during the traversal. The edge blockages are real-time, meaning that the salesman knows about a blocked edge when it occurs. We present a lower bound \(\frac{1}{1 + (k + 2)L}k+1\) and a CoverTreeTraversal algorithm for online CSP which is proved to be \(k+\alpha \)-competitive, where \(\alpha =0.5+\frac{(4k+2)L}{OPT}+2\gamma \rho \), \(\gamma \) is the approximation ratio for Steiner tree problem and \(\rho \) is the maximal number of locations that a customer can be served. When \(\frac{L}{\texttt {OPT}}\rightarrow 0\), our algorithm is near optimal. The problem is also extended to the version with service cost, and similar results are derived.     

The connected disk covering problem

Let P be a convex polygon with n vertices. We consider a variation of the K-center problem called the connected disk covering problem (CDCP), i.e., finding K congruent disks centered in P whose union covers P with the smallest possible radius, while a connected graph is generated by the centers of the K disks whose edge length can not exceed the radius. We give a 2.81-approximation algorithm in O(Kn) time.     

A PTAS for a disc covering problem using width-bounded separators

In this paper, we study the following disc covering problem: Given a set of discs of various radii on the plane and centers on the grid points, find a subset of discs to maximize the area covered by exactly one disc. This problem originates from the application in digital halftoning, with the best known approximation factor being 5.83 (Asano et al., 2004). We show that if their radii are between two positive constants, then there exists a polynomial time approximation scheme. Our techniques are based on the width-bounded geometric separator recently developed in Fu and Wang (2004), Fu (2006). This research is supported by Louisiana Board of Regents fund under contract number LEQSF(2004-07)-RD-A-35.     

Minimum covering with travel cost

Given a polygon and a visibility range, the Myopic Watchman Problem with Discrete Vision (MWPDV) asks for a closed path P and a set of scan points $\mathcal{S}$ , such that (i) every point of the polygon is within visibility range of a scan point; and (ii) path length plus weighted sum of scan number along the tour is minimized. Alternatively, the bicriteria problem (ii??) aims at minimizing both scan number and tour length. We consider both lawn mowing (in which tour and scan points may leave?P) and milling (in which tour, scan points and visibility must stay within P) variants for the MWPDV; even for simple special cases, these problems are NP-hard. We show that this problem is NP-hard, even for the special cases of rectilinear polygons and L _?? scan range 1, and negligible small travel cost or negligible travel cost. For rectilinear MWPDV milling in grid polygons we present a 2.5-approximation with unit scan range; this holds for the bicriteria version, thus for any linear combination of travel cost and scan cost. For grid polygons and circular unit scan range, we describe a bicriteria 4-approximation. These results serve as stepping stones for the general case of circular scans with scan radius r and arbitrary polygons of feature size a, for which we extend the underlying ideas to a $\pi(\frac{r}{a}+\frac{r+1}{2})$ bicriteria approximation algorithm. Finally, we describe approximation schemes for MWPDV lawn mowing and milling of grid polygons, for fixed ratio between scan cost and travel cost.     

The P-Hub maximal covering problem and extensions for gradual decay functions

The p-hub maximal covering problem aims to find the best locations for hubs so as to maximize demands within a coverage distance with a predetermined number of hubs. Classically, the problem is defined in the framework of binary coverage only; an origin–destination pair is covered if the cost (time, etc.) is lower than the critical value, and not covered at all if the cost is greater than the critical value. In this paper, we extend the definition of coverage, introducing “partial coverage”, which changes with distance. We present new and efficient mixed-integer programming models that are also valid for partial coverage for single and multiple allocations. We present and discuss the computational results with different data sets.     

A decomposition technique for quantifying real process performance

A decomposition technique for quantifying the impacts of changes in product mix and process performance on aggregate process-related indicators is presented. Through application of the technique, the real performance of a process can be quantified. Changes in real performance over time can be monitored to provide useful information for process evaluation and production planning. Two case studies, one related to the aggregate defective rate for an assembly line of an integrated circuit fabrication plant and the other to the aggregate inventory turnover for a tyre distribution company, are presented to illustrate the application of the technique.