Search

We show algorithms for computing representative families for matroid intersections and use them in fixed-parameter algorithms for set packing, set covering, and facility location problems with multiple matroid constraints. We complement our tractability results by hardness results., Comment: Restructuring (focus on representative families instead of facility location), slight running time improvements, algorithms factored out

Significant progress has been made in the field of computer vision because of the development of supervised machine learning algorithms, which efficiently extract information from high-dimensional data such as images and videos. Such techniques are particularly effective at recognizing the presence or absence of entities in the domains where labeled data are abundant. However, supervised learning is not sufficient in applications where one needs to annotate each unique entity in crowded scenes respecting known domain-specific structures of those entities. This problem, known as data association, provides fertile ground for the application of combinatorial optimization. In this review paper, we present a unified framework based on column generation for some computer vision applications, namely multiperson tracking, multiperson pose estimation, and multicell segmentation, which can be formulated as set packing problems with a massive number of variables. To solve them, column generation algorithms are applied to circumvent the need to enumerate all variables explicitly. To enhance the solution process, we provide a general approach for applying subset-row inequalities to tighten the formulations and introduce novel dual-optimal inequalities to reduce the dual search space. The proposed algorithms and their enhancements are successfully applied to solve the three aforementioned computer vision problems and achieve superior performance over benchmark approaches. The common framework presented allows us to leverage operations research methodologies to efficiently tackle computer vision problems.

We design the first efficient sensitivity oracles and dynamic algorithms for a variety of parameterized problems. Our main approach is to modify the algebraic coding technique from static parameterized algorithm design, which had not previously been used in a dynamic context. We particularly build off of the "extensor coding" method of Brand, Dell and Husfeldt [STOC'18], employing properties of the exterior algebra over different fields. For the k-Path detection problem for directed graphs, it is known that no efficient dynamic algorithm exists (under popular assumptions from fine-grained complexity). We circumvent this by designing an efficient sensitivity oracle, which preprocesses a directed graph on n vertices in 2^k poly(k) n^{ω+o(1)} time, such that, given 𝓁 updates (mixing edge insertions and deletions, and vertex deletions) to that input graph, it can decide in time 𝓁² 2^kpoly(k) and with high probability, whether the updated graph contains a path of length k. We also give a deterministic sensitivity oracle requiring 4^k poly(k) n^{ω+o(1)} preprocessing time and 𝓁² 2^{ω k + o(k)} query time, and obtain a randomized sensitivity oracle for the task of approximately counting the number of k-paths. For k-Path detection in undirected graphs, we obtain a randomized sensitivity oracle with O(1.66^k n³) preprocessing time and O(𝓁³ 1.66^k) query time, and a better bound for undirected bipartite graphs. In addition, we present the first fully dynamic algorithms for a variety of problems: k-Partial Cover, m-Set k-Packing, t-Dominating Set, d-Dimensional k-Matching, and Exact k-Partial Cover. For example, for k-Partial Cover we show a randomized dynamic algorithm with 2^k poly(k)polylog(n) update time, and a deterministic dynamic algorithm with 4^k poly(k)polylog(n) update time. Finally, we show how our techniques can be adapted to deal with natural variants on these problems where additional constraints are imposed on the solutions., LIPIcs, Vol. 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), pages 9:1-9:19

The item-sharing and crowdshipping problem combines two concepts of the sharing economy, namely item-sharing and crowdshipping. Item-sharing is about renting items among members of a sharing community. Crowdshipping addresses the transportation of these items through private people on trips they make anyway. The considered problem is to decide (1.) which request for an item to fulfill through which of the supplied items and (2.) who is doing the transport of rented items from the supply-locations to the request-locations. We generalize this problem with regard to crowdshippers’ capacity, meaning that each crowdshipper can transport a given number of items along his/her intended route. This results in a detour routing problem, where crowdshippers are routed through intermediate locations on the way from their actual origin location to their intended destination. We propose an exact solution method based on a set packing formulation for which a label setting procedure generates feasible crowdshipper routes a priori. We also describe how to derive a heuristic from the exact approach. Our experiments identify to what extend higher capacities of crowdshippers lead to more profitable routes and under which conditions a heuristic reduction of the method is required to cope with the complexity of the problem. We also show that the new exact method clearly outperforms procedures that were developed earlier for a setting where each crowdshipper can transport at most one single item.

In recent years, hyper-heuristics have received massive attention from the research community as an alternative of meta-heuristics. In a hyper-heuristic, generation or selection of an effective heuristic among a pool of heuristics is an important and challenging task in the search process. At each iteration, a suitable heuristic can take the search process toward the global optimal solution . Moreover, some additional factors such as quality and the number of heuristics also affect the performance. In this paper, we propose an evolutionary algorithm based hyper-heuristic framework that incorporates dynamic selection of parameters. To test its generality, effectiveness and robustness, we apply this approach on two different NP -hard problems - set packing problem (SPP) and minimum weight dominating set (MWDS) problem. The proposed approach for the SPP and the MWDS problem has been evaluated respectively on their respective set of benchmark instances. Computational results show that the proposed approach for the SPP and MWDS problem perform much better than their respective state-of-the-art approaches in terms of the solution quality and computational time.

Surrogate and group relaxation have been used to compute bounds for various integer linear programming problems. We prove that (a) when only inequalities are surrogated, the surrogate dual is NP -hard, but solvable in pseudo-polynomial time under certain conditions; (b) when equations are surrogated, the surrogate dual exhibits unusual complexity behaviour; (c) the group relaxation is NP -hard for the integer and 0-1 knapsack problems, and strongly NP -hard for the set packing problem.

We introduce set packing games as an abstraction of situations in which n selfish players select disjoint subsets of a finite set of indivisible items, and analyze the quality of several equilibria for this basic class of games. Special attention is given to a subclass of set packing games, namely throughput scheduling games, where the items represent jobs, and the subsets that a player can select are those jobs that this player can schedule feasibly. We show that the quality of three types of equilibrium solutions is only moderately suboptimal. Specifically, the paper gives tight bounds on the price of anarchy for Nash equilibria, subgame perfect equilibria of games with sequential play, and k-collusion Nash equilibria. Under the assumption that players are allowed to play suboptimally and achieve an $$\alpha $$-approximate equilibrium, our tight price of anarchy bounds are $$\alpha +1$$ for Nash and subgame perfect equilibria, but less than $$\alpha +1/(e-1)$$ for subgame perfect equilibria when games are symmetric. For k-collusion Nash equilibria, the price of anarchy equals $$\alpha +(n-k)/(n-1)$$, where $$1\le k\le n$$.

In this paper we propose a dual ascent heuristic for solving the linear relaxation of the generalized set partitioning problem with convexity constraints, which often models the master problem of a column generation approach. The generalized set partitioning problem contains at the same time set covering, set packing and set partitioning constraints. The proposed dual ascent heuristic is based on a reformulation and it uses Lagrangian relaxation and subgradient method. It is inspired by the dual ascent procedure already proposed in literature, but it is able to deal with right hand side greater than one, together with under and over coverage. To prove its validity, it has been applied to the minimum sum coloring problem, the multi-activity tour scheduling problem, and some newly generated instances. The reported computational results show the effectiveness of the proposed method.

Bike-Sharing System (BSS) is a convenient service deployed in many big cities to alleviate the last-mile problem. However, the explosion of users in BSS causes the inconvenience of bike utilization. Much efforts have been devoted to performing resources prediction, redistribution to help with BSS operation. But there are only a few works focus on trip planning, and none of them notice the complete bike trip in BSS composes of three segments: from user’s start point to a start station, from the start station to a target station, and from the target station to user’s terminal point. To study the case, this paper addresses a static trip planning problem by considering the bike utilization conflict in BSS so as to maximize the number of the served users and minimize their trip time. The problem is formulated as the weighted k -set packing problem. We then design a Greedy Trip Planning algorithm (GTP) and a Humble Trip Planning algorithm (HTP) to solve it. For comparison, we design a Random Trip Planning algorithm (RTP) as a benchmark. Extensive simulation results show that GTP and HTP outperform RTP, and reveal the impact of different factors on the performance of our algorithms.

In this paper, a new variant of the Simple Plant Location Problem is proposed. We consider additional conditions in the classic location-allocation problem for clients and facilities. Namely, some pairs have to be served by a common plant. The resulting problem can be addressed with existing models for the case of single assignment. However, to the best of our knowledge, the proposed setting when each client must be assigned to a couple of facilities is still unexplored. We examine the implications of adding such new constraints to standard formulations of the SPLP with double assignment. We compare the resulting formulations from a theoretical point of view. After that, we focus on the study of one of the models, which turned out to be a set packing problem. All the clique facets are identified and a separation algorithm is devised. Although the separation problem is proved to be NP-hard, our computational experience shows that the separation algorithm is effective and efficient, reducing computational times and duality gaps for all the instances tested.

This paper proposes a Cross Entropy approach to shape constrained Hamiltonians by optimizing their energy penalty values. The results show a significantly improved solution quality when run on D-Wave’s quantum annealing hardware and the numerical computation of the eigenspectrum reveals that the solution quality is correlated with a larger minimum spectral gap. The experiments were conducted based on the Knapsack-, Minimum Exact Cover- and Set Packing Problem. For all three constrained optimization problems we could show a remarkably better solution quality compared to the conventional approach, where the energy penalty values have to be guessed.

This article treats the determination of the largest powerset lattice that can be order embedded into a complete lattice \(\mathbb {L}\). That’s a complexity measure for \(\mathbb {L}\) and can be seen as an inner dimension. We show that this embedding problem translates to a set packing problem on the level of formal contexts. From this point of view, similarities to graph theoretic parameters emerge, which lead to a lattice theoretical interpretation of the clique number of simple graphs, in terms of an inner dimension of complete ortholattices. Furthermore, behaviour of the tensor product of complete (ortho)lattices is studied w.r.t. these inner dimensions.

This chapter proposes four types of mathematical optimization modeling approaches to optimize the product design Verification and Validation (V&V) planning during the New Product Development (NPD) process. These four optimization models provide four risk mitigation strategies from perspectives of cost efficiency to the optimal selection of a set of V&V activities for maximizing the overall system reliability improvement. The proposed approaches not only incorporate the critical product development constraints in V&V planning, such as the cost, time, reliability improvement, and sequencing and effectiveness of V&V activities, but also consider the decay of the improvement effectiveness when tackling the V&V activities’ selecting and sequencing challenges. In addition, the concepts of set covering, set partition, and set packing are applied to assure that different levels of critical failure modes can be covered in different ways according to different risk mitigation requirements by the end of V&V execution. The application of the proposed optimization models and comparisons with existing methods for product V&V planning are illustrated through the product development of a power generation system within a diesel engine.

In this paper, we consider symmetric binary programs that contain set packing, partitioning, or covering inequalities. To handle symmetries as well as set packing, partitioning, or covering constraints simultaneously, we introduce constrained symresacks which are the convex hulls of all binary points that are lexicographically not smaller than their image w.r.t. a coordinate permutation and which fulfill packing, partitioning, or covering constraints. We show that linear optimization problems over constrained symresacks can be solved in cubic time. Furthermore, we derive complete linear descriptions of constrained symresacks for particular classes of symmetries. These inequalities can then be used as strong symmetry handling cutting planes in a branch-and-bound procedure. Numerical experiments show that we can benefit from incorporating set packing, partitioning, or covering constraints into symmetry handling inequalities.

The set packing problem (SPP) is a significant NP-hard combinatorial optimization problem with extensive applications. In this paper, we encode the set packing problem as the maximum weighted independent set (MWIS) problem and solve the encoded problem with an efficient algorithm designed to the MWIS problem. We compare the independent set-based method with the state-of-the-art algorithms for the set packing problem on the 64 standard benchmark instances. The experimental results show that the independent set-based method is superior to the existing algorithms in terms of the quality of the solutions and running time obtained the solutions.

The lexicographic method is a technique that was introduced by Hell and Huang [Journal of Graph Theory, 20(3): 361–374, 1995] as a way to simplify the problems of recognizing and obtaining representations of comparability graphs, proper circular-arc graphs and proper interval graphs. This method gives rise to conceptually simple recognition algorithms and leads to much simpler proofs for some characterization theorems for these classes. Threshold graphs are a class of graphs that have many equivalent definitions and have applications in integer programming and set packing problems. A graph is said to have a threshold cover of size k if its edges can be covered using k threshold graphs. Chvatal and Hammer conjectured in 1977 that given a graph G, a suitably constructed auxiliary graph \(G'\) has chromatic number equal to the minimum size of a threshold cover of G. Although this conjecture was shown to be false in the general case by Cozzens and Leibowitz, it was shown to be true for graphs having a threshold cover of size 2 by Raschle and Simon [Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC ’95, pages 650–661, 1995]. That is, a graph G has a threshold cover of size 2 if and only if \(G'\) is bipartite—this is the only known forbidden structure characterization of graphs having a threshold cover of size 2. We show how the lexicographic method can be used to obtain a completely new and much simpler proof for this result. This method also gives rise to a simple new LexBFS-based algorithm for recognizing graphs having a threshold cover of size 2. Although this algorithm is not the fastest known, it is a certifying algorithm that matches the time complexity of the fastest known certifying algorithm for this problem. The algorithm can also be easily adapted to give a certifying recognition algorithm for bipartite graphs that can be covered by two chain subgraphs.

Dantzig–Wolfe reformulation of an integer program convexifies a subset of the constraints, which yields an extended formulation with a potentially stronger linear programming (LP) relaxation. We would like to better understand the strength of such reformulations in general. As a first step we investigate the classical edge formulation for the stable set problem. We characterize weakest possible Dantzig–Wolfe reformulations (with LP relaxations not stronger than the edge formulation) and strongest possible reformulations (yielding the integer hull). We (partially) extend our findings to related problems such as the matching problem and the set packing problem. These are the first non-trivial general results about the strength of relaxations obtained from decomposition methods, after Geoffrion’s seminal 1974 paper about Lagrangian relaxation.

This paper studies two polytopes: the complete set packing and set partitioning polytopes, which are both associated with a binary n -row matrix having all possible columns. Cuts of rank 1 for the latter polytope play a central role in recent exact algorithms for many combinatorial problems, such as vehicle routing. We show the precise relation between the two polytopes studied, characterize the multipliers that induce rank 1 clique facets and give several families of multipliers that yield other facets.

In the field of parameterized counting complexity, the problems that are #W[1]-hard and admit fixed-parameter tractable randomized approximation scheme (FPTRAS) have attracted much attention in recent years. In this paper, we focus on the problems on parameterized counting matching and packing. These problems include counting set packing , counting matching , and counting subgraph packing (including both vertex-disjoint and edge-disjoint versions). We study the parameterized complexity on these problems. On the basis of some results for counting graph matchings, we show that a series of problems are #W[1]-hard. Furthermore, by extending the previous algorithm for counting 3- d matching , we obtain FPTRAS for each considered problem, respectively. Our results indicate that the problems on parameterized counting matching and packing form a large family of problems that are #W[1]-hard and admit FPTRAS.

We propose a set packing (SP) framework for joint headlight pairing and vehicle tracking. Given headlight detections, traditional nighttime vehicle tracking methods usually first pair headlights and then track these pairs. However, the poor photometric condition often introduces tremendous noises in headlight detection and pairing, which leads to unrecoverable errors for vehicle tracking. To overcome the challenge, we propose to jointly model these two tasks in a weighted SP framework. Specifically, a graph is built which takes candidate pair track hypotheses as nodes and encodes in edges both the disjoint constraints for tracking and the no-sharing-headlight constraints for pairing. Solving a weighted SP problem on such a graph produces vehicle trajectories, and facilitates pairing with temporal context and in turn produces high quality vehicle trajectories. The solution, however, raises the issue of unmanageable graph scale since the number of track hypotheses grows exponentially over time. To address this issue, pruning strategies are developed to solve the joint model efficiently. The proposed system is evaluated on two traffic data sets, including videos under various challenging conditions. Both quantitative and qualitative results show that our method outperforms other tested methods, both in nighttime vehicle tracking and in multi-target tracking, confirming the benefits of jointly modeling the two tasks.

In earlier versions of the community discovering problem, the overlap between communities was restricted by a simple count upper-bound. In this paper, we introduce the [Formula: see text]-Packing with [Formula: see text]-Overlap problem to allow for more complex constraints in the overlap region than those previously studied. Let [Formula: see text] be all possible subsets of vertices of [Formula: see text] each of size at most [Formula: see text], and [Formula: see text] be a function. The [Formula: see text]-Packing with [Formula: see text]-Overlap problem seeks at least [Formula: see text] induced subgraphs in a graph [Formula: see text] subject to: (i) each subgraph has at most [Formula: see text] vertices and obeys a property [Formula: see text], and (ii) for any pair [Formula: see text], with [Formula: see text], [Formula: see text] (i.e., the pair [Formula: see text] does not conflict). We also consider a variant that arises in clustering applications: each subgraph of a solution must contain a set of vertices from a given collection of sets [Formula: see text], and no pair of subgraphs may share vertices from the sets of [Formula: see text]. In addition, we propose similar formulations for packing hypergraphs. We give an [Formula: see text] algorithm for our problems where [Formula: see text] is the parameter and [Formula: see text] and [Formula: see text] are constants, provided that: (i) [Formula: see text] is computable in polynomial time in [Formula: see text] and (ii) the function [Formula: see text] satisfies specific conditions. Specifically, [Formula: see text] is hereditary, applicable only to overlapping subgraphs, and computable in polynomial time in [Formula: see text] and [Formula: see text]. Motivated by practical applications we give several examples of [Formula: see text] functions which meet those conditions.

We introduce the strongly NP-hard pagination problem, an extension of BIN PACKING where packing together two items may make them occupy less volume than the sum of their individual sizes. To achieve this property, an item is defined as a finite set of symbols from a given alphabet. While, in BIN PACKING, any two such sets would be disjoint, in PAGINATION, they can share zero, one or more symbols. After formulating the problem as an integer linear program, we try to approximate its solutions with several families of algorithms: from straightforward adaptations of classical BIN PACKING heuristics, to dedicated algorithms (greedy and non-greedy), to standard and grouping genetic algorithms. All of them are studied first theoretically, then experimentally on an extensive random test set. Based upon these data, we propose a predictive measure of the statistical difficulty of a given instance, and finally recommend which algorithm should be used in which case, depending on either time constraints or quality requirements.