Max-min matching problems with multiple assignments

In job assignment and matching problems, we may sometimes need to assign several jobs to one processor or several processors to one job with some limit on the number of permissible assignments. Some examples include the assignment of courses to faculty, consultants to projects, etc. In terms of objectives, we may wish to maximize profits or minimize costs, or maximize the minimal value (max-min criterion) of an attribute such as the performance rating of a processor in the matching, or combine the two goals into one composite objective function entailing time-cost tradeoffs. The regular bipartite matching algorithms cannot solve the matching problem, when upper and lower bounds are imposed on the number of assignments. In this paper, we present a method, referred to as the node-splitting method, that transforms the given problem into an assignment problem solvable by the Hungarian method.     

Guaranteed clustering and biclustering via semidefinite programming

Identifying clusters of similar objects in data plays a significant role in a wide range of applications. As a model problem for clustering, we consider the densest \(k\) -disjoint-clique problem, whose goal is to identify the collection of \(k\) disjoint cliques of a given weighted complete graph maximizing the sum of the densities of the complete subgraphs induced by these cliques. In this paper, we establish conditions ensuring exact recovery of the densest \(k\) cliques of a given graph from the optimal solution of a particular semidefinite program. In particular, the semidefinite relaxation is exact for input graphs corresponding to data consisting of \(k\) large, distinct clusters and a smaller number of outliers. This approach also yields a semidefinite relaxation with similar recovery guarantees for the biclustering problem. Given a set of objects and a set of features exhibited by these objects, biclustering seeks to simultaneously group the objects and features according to their expression levels. This problem may be posed as that of partitioning the nodes of a weighted bipartite complete graph such that the sum of the densities of the resulting bipartite complete subgraphs is maximized. As in our analysis of the densest \(k\) -disjoint-clique problem, we show that the correct partition of the objects and features can be recovered from the optimal solution of a semidefinite program in the case that the given data consists of several disjoint sets of objects exhibiting similar features. Empirical evidence from numerical experiments supporting these theoretical guarantees is also provided.     

Optimal multiple interval assignments in frequency assignment and traffic phasing

In this paper, we consider the optimal assignments of unions of intervals to the vertices of the compatibility graph G, which arises in connection with frequency assignment and traffic phasing problems. It is shown that the optimal multiple interval phasing numbers θ_J≥rx(G) and θ^J≥r_xN(G), are optimal solutions to linear programming problems whose variables correspond to maximal cliques of G. Efficient algorithms are given for determining the first number, θ_J≥rx(G), when G is a chordal graph or a transitively orientable graph.     

Lower bounds for the quadratic assignment problem

We investigate the classical Gilmore-Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore-Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem.     

Extending the disjoint‐representatives theorems of Hall,Halmos, and Vaughan to list‐multicolorings of graphs

Philip Hall's famous theorem on systems of distinct representatives and its not‐so‐famous improvement by Halmos and Vaughan (1950) can be regarded as statements about the existence of proper list‐colorings or list‐multicolorings of complete graphs. The necessary and sufficient condition for a proper “coloring” in these theorems has a rather natural generalization to a condition we call Hall's condition on a simple graph G, a vertex list assignment to G, and an assignment of nonnegative integers to the vertices of G. Hall's condition turns out to be necessary for the existence of a proper multicoloring of G under these assignments. The Hall‐Halmos‐Vaughan theorem may be stated: when G is a clique, Hall's condition is sufficient for the existence of a proper multicoloring. In this article, we undertake the study of the class HHV of simple graphs G for which Hall's condition is sufficient for the existence of a proper multicoloring. It is shown that HHV is contained in the class ℋ︁₀ of graphs in which every block is a clique and each cut‐vertex lies in exactly two blocks. On the other hand, besides cliques, the only connected graphs we know to be in HHV are (i) any two cliques joined at a cut‐vertex, (ii) paths, and (iii) the two connected graphs of order 5 in ℋ︁₀, which are neither cliques, paths, nor two cliques stuck together. In case (ii), we address the constructive aspect, the problem of deciding if there is a proper coloring and, if there is, of finding one. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 199–219, 2000     

Edge cover by connected bipartite subgraphs

We consider the problem of covering the edge set of an unweighted, undirected graph with the minimum number of connected bipartite subgraphs (where the subgraphs are not necessarily bicliques). We show that this is an NP-hard problem, provide lower bounds through an integer programming formulation, propose several constructive heuristics and a local search, and discuss computational results. Finally, we consider a constrained variant of the problem which we show to be NP-hard, and provide an integer programming formulation for the variant.     

The incorporation of fixed cost and multilevel capacities into the discrete and continuous single source capacitated facility location problem

In this study we investigate the single source location problem with the presence of several possible capacities and the opening (fixed) cost of a facility that is depended on the capacity used and the area where the facility is located. Mathematical models of the problem for both the discrete and the continuous cases using the Rectilinear and Euclidean distances are produced. Our aim is to find the optimal number of open facilities, their corresponding locations, and their respective capacities alongside the assignment of the customers to the open facilities in order to minimise the total fixed and transportation costs. For relatively large problems, two solution methods are proposed namely an iterative matheuristic approach and VNS-based matheuristic technique. Dataset from the literature is adapted to assess our proposed methods. To assess the performance of the proposed solution methods, the exact method is first applied to small size instances where optimal solutions can be identified or lower and upper bounds can be recorded. Results obtained by the proposed solution methods are also reported for the larger instances.

     

A Localized Implementation of the Iterative Proportional Scaling Procedure for Gaussian Graphical Models

In this article, we propose localized implementations of the iterative proportional scaling (IPS) procedure by the strategy of partitioning cliques for computing maximum likelihood estimations in large Gaussian graphical models. We first divide the set of cliques into several nonoverlapping and nonempty blocks, and then adjust clique marginals in each block locally. Thus, high-order matrix operations can be avoided and the IPS procedure is accelerated. We modify the Swendsen–Wang Algorithm and apply the simulated annealing algorithm to find an approximation to the optimal partition which leads to the least complexity. This strategy of partitioning cliques can also speed up the existing IIPS and IHT procedures. Numerical experiments are presented to demonstrate the competitive performance of our new implementations and strategies.     

Solving the Maximum Clique Problem with Symmetric Rank-One Non-negative Matrix Approximation

Finding complete subgraphs in a graph, that is, cliques, is a key problem and has many real-world applications, e.g., finding communities in social networks, clustering gene expression data, modeling ecological niches in food webs, and describing chemicals in a substance. The problem of finding the largest clique in a graph is a well-known difficult combinatorial optimization problem and is called the maximum clique problem. In this paper, we formulate a very convenient continuous characterization of the maximum clique problem based on the symmetric rank-one non-negative approximation of a given matrix and build a one-to-one correspondence between stationary points of our formulation and cliques of a given graph. In particular, we show that the local (resp. global) minima of the continuous problem corresponds to the maximal (resp. maximum) cliques of the given graph. We also propose a new and efficient clique finding algorithm based on our continuous formulation and test it on the DIMACS data sets to show that the new algorithm outperforms other existing algorithms based on the Motzkin–Straus formulation and can compete with a sophisticated combinatorial heuristic.     

Lower bounds for nonlinear assignment problems using many body interactions

This paper concerns lower bounding techniques for the general α-adic assignment problem. The nonlinear objective function is linearized by the introduction of additional variables and constraints, thus yielding a mixed integer linear programming formulation of the problem. The concept of many body interactions is introduced to strengthen this formulation and incorporated in a modified formulation obtained by lifting the original representation to a higher dimensional space. This process involves two steps — (i) addition of new variables and constraints and (ii) incorporation of the new variables in the objective function. If this lifting process is repeated β times on an α-adic assignment problem along with the incorporation of higher order interactions, it results in the mixed-integer formulation of an equivalent (α + β)-adic assignment problem. The incorporation of many body interactions in the higher dimensional formulation improves its degeneracy properties and is also critical to the derivation of decomposition methods for the solution of these large scale mathematical programs in the higher dimensional space. It is shown that a lower bound to the optimal solution of the corresponding linear programming relaxation can be obtained by dualizing a subset of constraints in this formulation and solving O(N^2(α+β−1)) linear assignment problems, whose coefficients depend on the dual values. Moreover, it is proved that the optimal solution to the LP relaxation is obtained if we use the optimal duals for the solution of the linear assignment problems. This concept of many body interactions could be applied in designing algorithms for the solution of formulations obtained by lifting general MILP's. We illustrate all these concepts on the quadratic assignment problems With these decomposition bounds, we have found the provably optimal solutions of two unsolved QAP's of size 32 and have also improved upon existing lower bounds for other QAP's.     

An improvement in the Gavish-Shlifer algorithm for a class of transportation scheduling problems

In [2] Gavish and Shlifer present an algorithm for solving a class of transportation scheduling problems which includes the delivery problem, the school bus problem, and others. Their algorithm is based on the ‘savings method’ of Clarke and Wright. By solving a sequence of assignment problems, upper bounds may be generated for the original problem and the optimal solution determined through a branch and bound procedure. However, for certain problems the CPU time becomes excessive. In this paper we show that the bounds may be improved by solving a related maximum matching problem instead of the assignment problem. The result is that fewer branches need to be investigated. Computational results are presented indicating that considerably less CPU time is needed to solve problems using this approach than with the approach of Gavish and Shlifer.     

Classes of graphs without star forests and related graphs

This work provides a structural characterisation of hereditary graph classes that do not contain a star forest, several graphs obtained from star forests by subset complementation, a union of cliques, and the complement of a union of cliques as induced subgraphs. This provides, for instance, structural results for graph classes not containing a matching and several complements of a matching. In terms of the speed of hereditary graph classes, our results imply that all such classes have at most factorial speed of growth.     

一类广义指派问题的有效解法

提出一类广义指派问题,这类问题研究的是m个人执行n项任务,每个人执行的任务数、执行每项任务的人数以及总的指派人项数均有限制,要求最优指派.对这类广义指派问题建立了数学模型,并找到一种转换方法,将这类问题转换为平衡指派问题,从而用传统方法,如匈牙利法求解.最后用一个箅例来说明这种转换方法的简便和有效性.     

Multiple bottleneck assignment problem

We consider the multiple bottleneck assignment problem which subsumes the well known min-sum and bottleneck assignment problems. The problem arises in the context of flexible manufacturing systems, where the objective is to maximize the throughput of a production system with several flow shops, running in parallel, to produce a product. The problem is known to be strongly NP-hard. We propose a new algorithm for obtaining sharp lower bounds to the optimal objective value. Computational experiments are conducted to show the improvement over existing methods.     

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.     

Disjoint cliques and disjoint maximal independent sets of vertices in graphs

In this paper, we find lower bounds for the maximum and minimum numbers of cliques in maximal sets of pairwise disjoint cliques in a graph. By complementation, these yield lower bounds for the maximum and minimum numbers of independent sets in maximal sets of pairwise disjoint maximal independent sets of vertices in a graph. In the latter context, we show by examples that one of our bounds is best possible.     

Lagrangian heuristics for instructor scheduling in executive development programmes

In this paper we present the problem of scheduling instructors in a university management development programme. Problems of similar structure arise in a number of scheduling applications like assigning officials to athletic competitions, inspectors to sites and maintenance crews to jobs. The problem is formulated as a zero-one linear integer programme but is difficult to solve in real life situations because of problem size. The bounds on total assignments for different nested time periods give sub-problems that can be solved as network flow problems. Four Lagrangian relaxation heuristics are developed using different relaxations of the problem. Computational results are reported on 1350 random problems. In over 85% of these problems, the heuristics find solutions within 1% of the optimal. Heuristic performance is also analyzed in terms of average percent deviation from optimal, percent of times optimal solution is found and the cpu time. Computational results on two significantly larger real problems indicate that the heuristics are capable of solving real sized problems with tolerable deviations of around 4% from the optimal. An integrated strategy utilizing the strengths of the optimal and heuristic approaches is described for schedule generation and updating.     

Clique trees of chordal graphs: leafage and 3-asteroidals

Chordal graphs were characterized as those graphs having a tree, called clique tree, whose vertices are the cliques of the graph and for every vertex in the graph, the set of cliques that contain it form a subtree of clique tree. In this work, we study the relationship between the clique trees of a chordal graph and its subgraphs. We will prove that clique trees can be described locally and all clique trees of a graph can be obtained from clique trees of subgraphs. In particular, we study the leafage of chordal graphs, that is the minimum number of leaves among the clique trees of the graph. It is known that interval graphs are chordal graphs without 3-asteroidals. We will prove a generalization of this result using the framework developed in the present article. We prove that in a clique tree that realizes the leafage, for every vertex of degree at least 3, and every choice of 3 branches incident to it, there is a 3−asteroidal in these branches.     

Models and algorithms for a staff scheduling problem

We present mathematical models and solution algorithms for a family of staff scheduling problems arising in real life applications. In these problems, the daily assignments to be performed are given and the durations (in days) of the working and rest periods for each employee in the planning horizon are specified in advance, whereas the sequence in which these working and rest periods occur, as well as the daily assignment for each working period, have to be determined. The main objective is the minimization of the number of employees needed to perform all daily assignments in the horizon. We decompose the problem into two steps: the definition of the sequence of working and rest periods (called pattern) for each employee, and the definition of the daily assignment to be performed in each working period by each employee. The first step is formulated as a covering problem for which we present alternative ILP models and exact enumerative algorithms based on these models. Practical experience shows that the best approach is based on the model in which variables are associated with feasible patterns and generated either by dynamic programming or by solving another ILP. The second step is stated as a feasibility problem solved heuristically through a sequence of transportation problems. Although in general this procedure may not find a solution (even if one exists), we present sufficient conditions under which our approach is guaranteed to succeed. We also propose an iterative heuristic algorithm to handle the case in which no feasible solution is found in the second step. We present computational results on real life instances associated with an emergency call center. The proposed approach is able to determine the optimal solution of instances involving up to several hundred employees and a working period of up to 6 months. Mathematics Subject Classification (2000): 90B70, 90C10, 90C27, 90C39, 90C57, 90C59