Solving the flight gate assignment problem using dynamic programming

This paper considers the problem of assigning flights to airport gates—a problem which is NP-hard in general. We focus on a special case in which the maximization of flight/gate preference scores is the only objective. We show that for a variable number of flights and gates, this problem is still NP-hard. For a fixed number of gates, we present a dynamic programming approach that solves the flight assignment problem in linear time with respect to the number of flights. Computational results using real life data from a major European airport prove the practical relevance of this approach.     

Solving the maximum vertex weight clique problem via binary quadratic programming

In recent years, the general binary quadratic programming (BQP) model has been widely applied to solve a number of combinatorial optimization problems. In this paper, we recast the maximum vertex weight clique problem (MVWCP) into this model which is then solved by a probabilistic tabu search algorithm designed for the BQP. Experimental results on 80 challenging DIMACS-W and 40 BHOSLIB-W benchmark instances demonstrate that this general approach is viable for solving the MVWCP problem.     

A heuristic approximation algorithm of minimum dominating set based on rough set theory

The minimum dominating set of graph has been widely used in many fields, but its solution is NP-hard. The complexity and approximation accuracy of existing algorithms need to be improved. In this paper, we introduce rough set theory to solve the dominating set of undirected graph. First, the adjacency matrix of undirected graph is used to establish an induced decision table, and the minimum dominating set of undirected graph is equivalent to the minimum attribute reduction of its induced decision table. Second, based on rough set theory, the significance of attributes (i.e., vertices) based on the approximate quality is defined in induced decision table, and a heuristic approximation algorithm of minimum dominating set is designed by using the significance of attributes (i.e., vertices) as heuristic information. This algorithm uses forward and backward search mechanism, which not only ensures to find a minimal dominating set, but also improves the approximation accuracy of minimum dominating set. In addition, a cumulative strategy is used to calculate the positive region of induced decision table, which effectively reduces the computational complexity. Finally, the experimental results on public datasets show that our algorithm has obvious advantages in running time and approximation accuracy of the minimum dominating set.

     

Algorithmic aspect on the minimum (weighted) doubly resolving set problem of graphs

Journal of Combinatorial Optimization - Let G be a simple graph, where each vertex has a nonnegative weight. A vertex subset S of G is a doubly resolving set (DRS) of G if for every pair of...     

Algorithms for the minimum weight k-fold (connected) dominating set problem

In this paper, we study the problem of computing a minimum weight k-fold dominating set (MWkDS) or a minimum weight k-fold connected dominating set (MWkCDS) in a unit ball graph (UBG). Using slab decomposition and dynamic programming, we give two exact algorithms for the computation of MWkDS and MWkCDS which can be executed in polynomial time if the thickness of the graph is bounded above.     

A greedy algorithm for the minimum 2-connected m-fold dominating set problem

To save energy and alleviate interference in a wireless sensor network, connected dominating set (CDS) has been proposed as the virtual backbone. Since nodes may fail due to accidental damage or energy depletion, it is desirable to construct a fault tolerant CDS, which can be modeled as a \(k\)-connected \(m\)-fold dominating set \(((k,m)\)-CDS for short): a subset of nodes \(C\subseteq V(G)\) is a \((k,m)\)-CDS of \(G\) if every node in \(V(G)\setminus C\) is adjacent with at least \(m\) nodes in \(C\) and the subgraph of \(G\) induced by \(C\) is \(k\)-connected.In this paper, we present an approximation algorithm for the minimum \((2,m)\)-CDS problem with \(m\ge 2\). Based on a \((1,m)\)-CDS, the algorithm greedily merges blocks until the connectivity is raised to two. The most difficult problem in the analysis is that the potential function used in the greedy algorithm is not submodular. By proving that an optimal solution has a specific decomposition, we managed to prove that the approximation ratio is \(\alpha +2(1+\ln \alpha )\), where \(\alpha \) is the approximation ratio for the minimum \((1,m)\)-CDS problem. This improves on previous approximation ratios for the minimum \((2,m)\)-CDS problem, both in general graphs and in unit disk graphs.     

A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs

In the minimum weighted dominating set problem (MWDS), we are given a unit disk graph with non-negative weight on each vertex. The MWDS seeks a subset of the vertices of the graph with minimum total weight such that each vertex of the graph is either in the subset or adjacent to some nodes in the subset. A?weight function is called smooth, if the ratio of the weights of any two adjacent nodes is upper bounded by a constant. MWDS is known to be NP-hard. In this paper, we give the first polynomial time approximation scheme (PTAS) for MWDS with smooth weights on unit disk graphs, which achieves a (1+ε)-approximation for MWDS, for any ε>0.     

一种基于粗糙集理论的规则获取算法

获取规则是数据挖掘中的一项重要技术 ,根据粗糙集理论及决策值归纳函数的概念 ,可以把不相容的决策系统转化为相容的决策系统 ,并提出规则参数的合并方法 .在此基础上 ,利用决策矩阵和决策函数 ,提出了一种在决策系统中获取规则的算法 .同传统的算法相比 ,该算法得出的规则集没有信息丢失的现象发生 .最后以例子作了说明 .     

The resource constrained multi-item inventory problem with price discount: a geometric programming approach

In this paper we present a geometric programming approach for determining the inventory policy for multiple items having price discount and a limit on the total average inventory of all the items. An example is solved to illustrate the method.     

Allocation and optimization of shared self-service check-in system based on integer programming model

Journal of Combinatorial Optimization - The shared self-service check-in system can effectively alleviate the tension of airport caused by limited resources in the future. The effective allocation...     

Some results on the target set selection problem

In this paper we consider a fundamental problem in the area of viral marketing, called Target Set Selection problem. We study the problem when the underlying graph is a block-cactus graph, a chordal graph or a Hamming graph. We show that if G is a block-cactus graph, then the Target Set Selection problem can be solved in linear time, which generalizes Chen’s result (Discrete Math. 23:1400–1415, 2009) for trees, and the time complexity is much better than the algorithm in Ben-Zwi et al. (Discrete Optim., 2010) (for bounded treewidth graphs) when restricted to block-cactus graphs. We show that if the underlying graph G is a chordal graph with thresholds θ(v)≤2 for each vertex v in G, then the problem can be solved in linear time. For a Hamming graph G having thresholds θ(v)=2 for each vertex v of G, we precisely determine an optimal target set S for (G,θ). These results partially answer an open problem raised by Dreyer and Roberts (Discrete Appl. Math. 157:1615–1627, 2009).     

Path packing and a related optimization problem

Let G be a supply graph, with the node set N and edge set E, and (T,S) be a demand graph, with T?N, S∩E=?. Observe paths whose end-vertices form pairs in S (called S-paths). The following path packing problem for graphs is fundamental: what is the maximal number of S-paths in G? In this paper this problem is studied under two assumptions: (a) the node degrees in N?T are even, and (b) any three distinct pairwise intersecting maximal stable sets A,B,C of (T,S) satisfy A∩B=B∩C=A∩C (this condition was defined by A. Karzanov in Linear Algebra Appl. 114–115:293–328, 1989). For any demand graph violating (b) the problem is known to be NP-hard even under (a), and only a few cases satisfying (a) and (b) have been solved. In each of the solved cases, a solution and an optimal dual object were defined by a certain auxiliary “weak” multiflow optimization problem whose solutions supply constructive elements for S-paths and concatenate them into an S-path packing by a kind of matching. In this paper the above approach is extended to all demand graphs satisfying (a) and (b), by proving existence of a common solution of the S-path packing and its weak counterpart. The weak problem is very interesting for its own sake, and has connections with such topics as Mader’s edge-disjoint path packing theorem and b-factors in graphs.     

Solving the part families problem in discrete-parts manufacture by simulated annealing

In the production planning and control of discrete-parts manufacture, aggregation of parts into families, on the basis of similarity, is carried out to ease both long-horizon planning and short-horizon scheduling. Additional advantages are related to those of group technology (GT), such as simplifying the flow of parts and tools and reducing both set-up and production costs. The problem of formally forming part families is presented and discussed. Previous work is reviewed and assessed. Two solution approaches, one based on a location model, the other on simulated annealing, are presented and compared along with test results. The location formulation, which results in an integer programming model solved by Lagrangian relaxation, proved capable of producing solutions of excellent quality, but only for relatively small problem instances. In contrast, simulated annealing, which is a general heuristic approach to combinatorial optimization, produced solutions of comparable quality and could handle realistically large problem instances. However, careful design of the simulated annealing algorithm is crucially important. An effective design is presented.     

Production planning of mixed-model assembly lines: a heuristic mixed integer programming based approach

Process technology capabilities are becoming increasingly important as flexible manufacturing continues to be more prevalent, and as competition compels companies to provide expanded variety, at ever lower cost, so introducing plant and processes technological constraints. Model flexibility can also benefit from an appropriate production planning process, especially concerning mixed-model assembly lines, since it can facilitate master scheduling and line balancing activities, which are essential aspects of flexibility. Robust and practical planning approaches have to take into account two different aspects: the first consists in ensuring that the elaborated aggregate plan can be disaggregated into at least one detailed feasible plan for the realised demand, whereas the second in ensuring that this detailed plan is feasible at the operational level. This article faces the model flexibility challenge, reviewing and discussing the planning problem of a real world assembly manufacturing system, producing high volume and a variety of agricultural tractors and machines, analysing and resolving some important issues related to technological, organisational and managerial constraints. This article illustrates the implementation of an Advanced Planning System integrated with a mixed integer-programming model, which is solved by a new iterative heuristic approach capable of achieving interesting planning improvements for model-flexibility management.     

A complexity dichotomy and a new boundary class for the dominating set problem

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.