Approximability of partitioning graphs with supply and demand

Suppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive “power” from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C either has no supply vertex or has exactly one supply vertex whose supply is at least the sum of demands in C, and wishes to maximize the fulfillment, that is, the sum of demands in all components with supply vertices. This maximization problem is known to be NP-hard even for trees having exactly one supply vertex and strongly NP-hard for general graphs. In this paper, we focus on the approximability of the problem. We first show that the problem is MAXSNP-hard and hence there is no polynomial-time approximation scheme (PTAS) for general graphs unless $\mathrm{P}=\mathrm{NP}$. We then present a fully polynomial-time approximation scheme (FPTAS) for series-parallel graphs having exactly one supply vertex.     

Optimum service capacity and demand management with price incentives

Service firms periodically face fluctuating demand levels. They incur high costs to handle peak demand and pay for under-utilized capacity during low demand periods. In this paper, we develop a mixed integer programming (MIP) model based on the real life experience of a Brazilian telecommunications firm. The model determines the optimum staffing requirements with different seniority levels for employees, as well as the distribution and balancing of workload utilizing flexibility of some customers in their service completion day. The proposed MIP uses monetary incentives to smooth the workload by redistributing some of the peak demand, thereby increasing capacity utilization. Due to the intractable nature of optimizing the proposed MIP model, we present a heuristic solution approach. The MIP model is applied to the case of the examined Brazilian Telecommunications firm. The computational work on this base case and its extensions shows that the proposed MIP model is of merit, leading to approximately seventeen percent reduction in the base case operating costs. Extensive computational work demonstrates that our heuristic provides quality solutions in very short computational times. The model can also be used to select new customers based on the workload, the revenue potential of these new customers and their flexibility in accepting alternate service completion dates. The generic structure of the proposed approach allows for its application to a wide variety of service organizations facing similar capacity and demand management challenges. Such wide applicability enhances the value of our work and its expected benefits.     

Optimal infrastructure design and expansion of broadband wireless access networks

This paper investigates the important infrastructure design and expansion problem for broadband wireless access networks subject to user demand constraints and system capacity constraints. For the problem, an integer program is derived and a heuristic solution procedure is proposed based on Lagrangean relaxation. In the computational experiments, our Lagrangean relaxation based algorithm can solve this complex design and expansion problem quickly and near optimally. Based on the test results, it is suggested that the proposed algorithm may be practically used for the infrastructure design and expansion problem for broadband wireless access networks.     

Network flow interdiction on planar graphs

The network flow interdiction problem asks to reduce the value of a maximum flow in a given network as much as possible by removing arcs and vertices of the network constrained to a fixed budget. Although the network flow interdiction problem is strongly NP-complete on general networks, pseudo-polynomial algorithms were found for planar networks with a single source and a single sink and without the possibility to remove vertices. In this work, we introduce pseudo-polynomial algorithms that overcome various restrictions of previous methods. In particular, we propose a planarity-preserving transformation that enables incorporation of vertex removals and vertex capacities in pseudo-polynomial interdiction algorithms for planar graphs. Additionally, a new approach is introduced that allows us to determine in pseudo-polynomial time the minimum interdiction budget needed to remove arcs and vertices of a given network such that the demands of the sink node cannot be completely satisfied anymore. The algorithm works on planar networks with multiple sources and sinks satisfying that the sum of the supplies at the sources equals the sum of the demands at the sinks. A simple extension of the proposed method allows us to broaden its applicability to solve network flow interdiction problems on planar networks with a single source and sink having no restrictions on the demand and supply. The proposed method can therefore solve a wider class of flow interdiction problems in pseudo-polynomial time than previous pseudo-polynomial algorithms and is the first pseudo-polynomial algorithm that can solve non-trivial planar flow interdiction problems with multiple sources and sinks. Furthermore, we show that the k-densest subgraph problem on planar graphs can be reduced to a network flow interdiction problem on a planar graph with multiple sources and sinks and polynomially bounded input numbers.     

A compact optimization model for the tail assignment problem

This paper investigates a new model for the so-called Tail Assignment Problem, which consists in assigning a well-identified airplane to each flight leg of a given flight schedule, in order to minimize total cost (cost of operating the flights and possible maintenance costs) while complying with a number of operational constraints. The mathematical programming formulation proposed is compact (i.e., involves a number of $0?1$ decision variables and constraints polynomial in the problem size parameters) and is shown to be of significantly reduced dimension as compared with previously known compact models. Computational experiments on series of realistic problem instances (obtained by random sampling from real-world data set) are reported. It is shown that with the proposed model, current state-of-the art MIP solvers can efficiently solve to exact optimality large instances representing 30-day flight schedules with typically up to 40 airplanes and 1500 flight legs connecting as many as 21 airports. The model also includes the main existing types of maintenance constraints, and extensive computational experiments are reported on problem instances of size typical of practical applications.     

Weakly bipartite graphs and the Max-cut problem

A new class of graphs, called weakly bipartite graphs, is introduced. A graph is called weakly bipartite if its bipartite subgraph polytope coincides with a certain polyhedron related to odd cycle constraints. The class of weakly bipartite graphs contains for instance the class of bipartite graphs and the class of planar graphs. It is shown that the max-cut problem can be solved in polynomial time for weakly bipartite graphs. The polynomical algorithm presented is based on the ellipsoid method and an algorithm that computes a shortest path of even length.     

面向供应恢复时效性的弹性分销网络研究

关于供应链的弹性,供应能力恢复时效性的重要程度丝毫不亚于供应能力的恢复程度。本文研究了面向供应恢复时效性的弹性分销网络设计问题。考虑一个三级分销网络,其中各分销中心互为各自的备用分销中心。当一个分销中心因发生失效事件而不能接受制造商的供货时,制造商通过其他分销中心向失效的分销中心供货。分销中心需要保持一定量的应急库存以满足在应急供应到达之前的顾客需求。针对该问题建立了混合整数规划模型。该模型包含的大M约束使得直接使用优化软件求解需要很长的计算时间,并对计算平台的硬件配置有较高要求。为了更高效地求解该模型,提出了改进的MILP分解算法。通过对比实验,证明了所提算法的效率和有效性。进行了模型的敏感性分析,研究了各项参数对分销网络结构和成本的影响。     

Discovering implied constraints in precedence graphs with alternatives

During automated problem solving it may happen that some knowledge that is known at the user level is lost in the formal model. As this knowledge might be important for efficient problem solving, it seems useful to re-discover it in order to improve the efficiency of the solving procedure. This paper compares three methods for discovering certain implied constraints in the constraint models describing manufacturing (and other) processes with serial, parallel, and alternative operations. In particular, we focus on identifying equivalent nodes in the precedence graph with parallel and alternative branches. Equivalent nodes correspond to operations that either must be all simultaneously present or none of them can be present in the schedule. Such information is frequently known at the user level, but it is lost in the formal model. The paper shows that identifying equivalent nodes is an NP-hard problem in general, but it is tractable if the graph has a nested structure. As the nested structure is typical for real-life processes and workflows, we use the nested graphs to experimentally compare the proposed methods.     

An efficient computational method for a stochastic dynamic lot-sizing problem under service-level constraints

We provide an efficient computational approach to solve the mixed integer programming (MIP) model developed by Tarim and Kingsman [8] for solving a stochastic lot-sizing problem with service level constraints under the static-dynamic uncertainty strategy. The effectiveness of the proposed method hinges on three novelties: (i) the proposed relaxation is computationally efficient and provides an optimal solution most of the time, (ii) if the relaxation produces an infeasible solution, then this solution yields a tight lower bound for the optimal cost, and (iii) it can be modified easily to obtain a feasible solution, which yields an upper bound. In case of infeasibility, the relaxation approach is implemented at each node of the search tree in a branch-and-bound procedure to efficiently search for an optimal solution. Extensive numerical tests show that our method dominates the MIP solution approach and can handle real-life size problems in trivial time.     

Production planning via scenario modelling

Several Linear Programming (LP) and Mixed Integer Programming (MIP) models for the production and capacity planning problems with uncertainty in demand are proposed. In contrast to traditional mathematical programming approaches, we use scenarios to characterize the uncertainty in demand. Solutions are obtained for each scenario and then these individual scenario solutions are aggregated to yield a nonanticipative or implementable policy. Such an approach makes it possible to model nonstationarity in demand as well as a variety of recourse decision types. Two scenario-based models for formalizing implementable policies are presented. The first model is a LP model for multi-product, multi-period, single-level production planning to determine the production volume and product inventory for each period, such that the expected cost of holding inventory and lost demand is minimized. The second model is a MIP model for multi-product, multi-period, single-level production planning to help in sourcing decisions for raw materials supply. Although these formulations lead to very large scale mathematical programming problems, our computational experience with LP models for real-life instances is very encouraging.     

Qualitative chain graphs and their application

For many problem domains, such as medicine, chain graphs are more attractive than Bayesian networks as they support representing interactions between variables that have no natural direction. In particular, interactions between variables that result from certain feedback mechanisms can be represented by chain graphs. Using qualitative abstractions of probabilistic interactions is also of interest, as these allow focusing on patterns in the interactions rather than on the numerical detail. Such patterns are often known by experts and sufficient for making decisions. So far, qualitative abstractions of probabilistic interactions have only been developed for Bayesian networks in the form of qualitative probabilistic networks. In this paper, such qualitative abstractions are developed for chain graphs with the practical aim of using qualitative knowledge as constraints on the hyperspace of probability distributions. The usefulness of qualitative chain graphs is explored for modelling and reasoning about the interactions between diseases.     

A heuristic approach for dividing graphs into bi-connected components with a size constraint

In this paper we propose a new problem of finding the maximal bi-connected partitioning of a graph with a size constraint (MBCPG-SC). With the goal of finding approximate solutions for the MBCPG-SC, a heuristic method is developed based on the open ear decomposition of graphs. Its essential part is an adaptation of the breadth first search which makes it possible to grow bi-connected subgraphs. The proposed randomized algorithm consists of growing several subgraphs in parallel. The quality of solutions generated in this way is further improved using a local search which exploits neighboring relations between the subgraphs. In order to evaluate the performance of the method, an algorithm for generating pseudo-random unit disc graphs with known optimal solutions is created. Computational experiments have also been conducted on graphs representing electrical distribution systems for the real-world problem of dividing them into a system of fault tolerant interconnected microgrids. The experiments show that the proposed method frequently manages to find optimal solutions and has an average error of only a few percent to known optimal solutions. Further, it manages to find high quality approximate solutions for graphs having up to 10,000 nodes in reasonable time.     

Box-threshold graphs

A graph is called box-threshold when all pairs of vertices with incomparable neighborhoods have the same degree. Several properties of box-threshold graphs, generalizing properties of threshold graphs, are proved. A transportation model with priority constraints is used to characterize their degree sequences. Further characterizations are given using the concept of the frame of a graph.     

Radial Moore graphs of radius three

The maximum number of vertices in a graph of specified degree and diameter cannot exceed the Moore bound. Graphs achieving this bound are called Moore graphs. Because Moore graphs are so rare, researchers have considered various relaxations of the Moore graph constraints. Since the diameter of a Moore graph is equal to its radius, one can consider graphs in which the condition on the diameter is relaxed, by one, while the condition on the radius is maintained. Such graphs are called radial Moore graphs. It has previously been shown that radial Moore graphs exist for all degrees when the radius is two. In this paper, we extend this result to radius three. We also construct examples that settle the existence question for a few new cases, and summarize the state of knowledge on the problem.     

Large neighborhood search for LNG inventory routing

Liquefied Natural Gas (LNG) is steadily becoming a common mode for commercializing natural gas. Due to the capital intensive nature of LNG projects, the optimal design of LNG supply chains is extremely important from a profitability perspective. Motivated by the need for a model that can assist in the design analysis of LNG supply chains, we address an LNG inventory routing problem where optimized ship schedules have to be developed for an LNG project. In this paper, we present an arc-flow formulation based on the MIP model of Song and Furman (Comput. Oper. Res., 2010). We also present a set of construction and improvement heuristics to solve this model efficiently. The heuristics are evaluated based on a set of realistic test instances that are very large relative to the problem instances seen in recent literature related to this problem. Extensive computational results indicate that the proposed methods are computationally efficient in finding optimal or near optimal solutions and are substantially faster than state-of-the-art commercial optimization software.     

Processor interconnection networks from Cayley graphs

Cayley graphs of groups are presently being considered by the computer science community as models of architectures for large scale parallel processor computers. In the first section of this paper we discuss Cayley graphs and show how they may be used as a tool for the design and analysis of network architectures for these types of computers.

Observing that routing on a Cayley graph is equivalent to a certain factoring problem in the associated group, we have been able to use a known powerful factoring technique in computational group theory to produce a fast efficient routing algorithm on the associated Cayley graph. In the second section of this paper we present this work. This research can be regarded as a first attempt to find general purpose routing algorithms for interconnection networks.

Believing that average diameter of a network for a large scale MIMD machine is the predominant factor in determining network performance, we designed Cayley graphs to be used in a special study performed at the Supercomputing Research Center (SRC). The importance of the average diameter in determining network performance was supported by the fact that the graphs found by us had the smallest average diameter and outperformed all other graphs evaluated in the study. In fact, before being driven into saturation, one of our graphs sustained 9.4% more network traffic than the next best candidate, a butterfly architecture, and 74.3% better than the bench mark 2-d mesh. The last section of our paper is devoted to this work.

This paper is divided into three sections. In the first section we discuss Cayley graphs and show how they may be used as a tool for the design and analysis of network architectures for parallel computers. In the second section we present our research on the routing problem. This research can be regarded as a first attempt to find general purpose routing algorithms for interconnection networks. In the last section we present some evidence that average diameter of a network for a large scale MIMD machine is the predominant factor in determining network performance.     

Constraint programming for computing non-stationary (R, S) inventory policies

This paper proposes a constraint programming model for computing the finite horizon single-item inventory problem with stochastic demands in discrete time periods with service-level constraints under the non-stationary version of the “periodic review, order-up-to-level” policy (i.e., non-stationary (R, S) or, simply (R_n, S_n)). It is observed that the modeling process is more natural and the required number of variables is smaller compared to the MIP formulation of the same problem. The computational tests show that the CP approach is more tractable than the conventional MIP formulation. Two different domain reduction methods are proposed to improve the computational performance of solution algorithms. The numerical experiments confirmed the effectiveness of these methods.     

Branch and cut algorithms for detecting critical nodes in undirected graphs

In this paper we deal with the critical node problem, where a given number of nodes has to be removed from an undirected graph in order to maximize the disconnections between the node pairs of the graph. We propose an integer linear programming model with a non-polynomial number of constraints but whose linear relaxation can be solved in polynomial time. We derive different valid inequalities and some theoretical results about them. We also propose an alternative model based on a quadratic reformulation of the problem. Finally, we perform many computational experiments and analyze the corresponding results.     

Node-searching problem on block graphs

The node-searching problem, introduced by Kirousis and Papadimitriou, is equivalent to several important problems, such as the interval thickness problem, the path-width problem, the vertex separation problem, and so on. In this paper, we generalize the avenue concept, originally proposed for trees, to block graphs whereby we design an efficient algorithm for computing both the search numbers and optimal search strategies for block graphs. It answers the question proposed by Peng et al. of whether the node-searching problem on block graphs can be solved in polynomial time.