Abstract We consider a game-theoretic variant of maximizing a monotone increasing, submodular function under a cardinality constraint. Initially, a solution to this classic problem is determined. Subsequently, a predetermined number of elements from the ground set, not necessarily contained in the initial solution, are deleted, potentially reducing the solution’s cardinality. If any deleted elements were part of the initial solution, they are replaced with a set of at most equal cardinality. The objective is to maximize the value of the ultimate solution, with the deletion being maximally disadvantageous to the ultimate solution. When the submodular function is $${{\,\mathrm{ \text {M}^\natural }\,}}$$ M ♮ -concave, we prove that a simple greedy algorithm computes an optimal solution. When only one element may be deleted, we propose a polynomial running time algorithm with an approximation factor of at least $$\frac{1}{3}$$ 1 3 . When the number of deletions may become as large as the cardinality parameter, we present a polynomial running time algorithm that approximates an optimal ultimate solution in dependence on the curvature of the submodular function. Furthermore, assuming that the number of allowed deletions is upper bounded by a term of the order of $$\frac{k}{\log _2^2(k)}$$ k log 2 2 ( k ) , where k is the cardinality parameter, we adapt an algorithm from Bogunovic et al. and show that its approximation factor is at least 0.108.

Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations and also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well-studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, almost no tailored algorithms are known besides reformulations of the problem that allow us to apply general purpose mixed integer linear programming solvers. In this paper, we present, theoretically analyze, enhance, and test a novel branch-and-bound method for MILCPs. The main property of this method is that we do not “branch” on constraints as usual but by adding suitably chosen penalty terms to the objective function. By doing so, we can either provably compute an MILCP solution if one exists or compute an approximate solution that minimizes an infeasibility measure combining integrality and complementarity conditions. We enhance the method by MILCP-tailored valid inequalities, node selection strategies, branching rules, and warm-starting techniques. The resulting algorithm is shown to clearly outperform two benchmark approaches from the literature. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Funding: M. De Santis acknowledges support within the project RM120172A2970290, which has received funding from Sapienza, University of Rome. M. Schmidt thanks the Deutsche Forschungsgemeinschaft (DFG) for its support within project A05 and B08 in the “SFB TRR 154 Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks.” L. Winkel is supported by the DFG within the Research Training Group 2126: “Algorithmic Optimization.” Supplemental Material: The online supplementary material is available at https://doi.org/10.1287/ijoc.2022.1216 .

Abstract Cutting planes from the Boolean Quadric Polytope can be used to reduce the optimality gap of the $$\mathcal {NP}$$ NP -hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvátal–Gomory closure of the Boolean Quadric Polytope are A-odd cycle inequalities. We obtain a compact extended relaxation of allA-odd cycle inequalities, which allows to optimize over the Chvátal–Gomory closure without repeated calls to separation algorithms and has less inequalities than the formulation provided by Boros et al. (SIAM J Discrete Math 5(2):163–177, 1992) for sparse matrices. In a computational study, we confirm the strength of this relaxation and show that we can provide very strong bounds for the BoxQP, even with a plain linear program. The resulting bounds are significantly stronger than these from Bonami et al. (Math Program Comput 10(3):333–382, 2018), which arise from separating A-odd cycle inequalities heuristically.

Abstract The 1‐wheel inequalities for the stable set polytope were introduced by Cheng and Cunningham. In general, there is an exponential number of these inequalities. We present a new polynomial size extended formulation of the stable set relaxation that includes the odd cycle and 1‐wheel inequalities. This compact formulation allows one to polynomially optimize over a polyhedron instead of handling the separation problem for 1‐wheel inequalities by solving many shortest walk problems and relying on the ellipsoid method.

Ring structures in molecules belong to the most important substructures for many applications in Computational Chemistry. One typical task is to find an implicit description of the ring structure of a molecule. We present efficient algorithms for cyclic graph invariants that may serve as molecular descriptors to accelerate database searches. Another task is to construct a well‐defined set of rings of a molecular graph explicitly. We give a new algorithm for computing the set of relevant cycles of a graph. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(2), 116–131 2017

A very important ingredient for solving hard general integer programs are heuristics that try to quickly find good feasible solutions. One of these heuristics is Wedelin's algorithm, which works for the limited class of 0-1 integer programs. A big advantage of Wedelin's approach is that it does not depend on a solution of the linear programming (LP) relaxation as many other heuristics do. This makes it extremely fast in practice and makes it easy to use the parallelism of the upcoming multicore CPUs, as in an integer programming (IP) solver it could be applied in parallel to the traditional branch-and-bound algorithm. In this paper, we present several extensions and generalizations to Wedelin's algorithm (most can be handled in an implicit manner without much performance cost) and investigate different ways of improving it. We give all necessary details and parameters. We strive for an algorithm that is faster than other heuristics but achieves comparable solution quality. We evaluate the performance of the algorithm on a large set of more than 100 instances from different sources. The results indicate that our heuristic often finds solutions comparable to or even better than those found using current state-of-the-art heuristics while typically needing only a fraction of their running time. Additionally, we report positive findings on the application of the heuristic on feasibility instances from discrete tomography. Our algorithm always finds the IP optimum in less time than the simplex/barrier algorithms and often in less time than it takes the volume algorithm to find just the LP optimum.

Many auctions involve the sale of a variety of distinct assets. Examples are airport time slots, delivery routes, network routing, and furniture. Because of complementarities or substitution effects between the different assets, bidders have preferences not just for particular items but for sets of items. For this reason, economic efficiency is enhanced if bidders are allowed to bid on bundles or combinations of different assets. This paper surveys the state of knowledge about the design of combinatorial auctions and presents some new insights. Periodic updates of portions of this survey will be posted to this journal's Online Supplements web page at http://joc.pubs.informs.org/OnlineSupplements.html

A large class of facets is constructed for the stable set polytope. This class is a common generalization of wheel facets and of antiweb facets. The proof of their validity and facetness exploits graph operations which transform inequalities into more complicated ones. In an accompanying paper polynomial time separation-algorithms are presented for generalizations of these inequalities.