Spatial frequency estimation from a mixture of noisy sinusoids finds applications in various fields. The widely used subspace-based methods provide super-resolution parameter estimation at a low computational cost. However, they require an accurate array calibration, which is difficult for large antenna arrays. Sparsity-based methods have been shown to be more robust than subspace-based methods in difficult scenarios, e.g., in the case with a small number of snapshots and/or correlated sources. In this paper, we consider the direction-of-arrival (DOA) estimation in partly calibrated rectangular arrays comprising several calibrated and identical subarrays. We derive a gridless sparse formulation for DOA estimation based on the shift-invariance properties of the array and develop an efficient algorithm in the alternating direction method of multipliers (ADMM) framework. Numerical simulations show the superior error performance of our proposed method compared to subspace-based methods.

This paper investigates linear programming based branch-and-bound using general disjunctions, also known as stabbing planes, for solving integer programs. We derive the first sub-exponential lower bound (in the encoding length L of the integer program) for the size of a general branch-and-bound tree for a particular class of (compact) integer programs, namely 2Ω(L1/12-ɛ) for every ɛ > 0. This is achieved by showing that general branch-and-bound admits quasi-feasible monotone real interpolation, which allows us to utilize sub-exponential lower-bounds for monotone real circuits separating the so-called clique-coloring pair. The same ideas also prove that refuting Θ(log(n))-CNFs requires size 2nΩ(1) branch-and-bound trees with high probability by considering the closely related notion of infeasibility certificates introduced by Hrubeš and Pudlák [18]. One important ingredient of the proof of our interpolation result is that for every general branch-and-bound tree proving integer-freeness of a product P × Q of two polytopes P and Q, there exists a closely related branch-and-bound tree for showing integer-freeness of P or one showing integer-freeness of Q. Moreover, we prove that monotone real circuits can perform binary search efficiently.

Cutting-planes are one of the most important building blocks for solving large-scale integer programming (IP) problems to (near) optimality. The majority of cutting plane approaches rely on explicit rules to derive valid inequalities that can separate the target point from the feasible set. Local cuts, on the other hand, seek to directly derive the facets of the underlying polyhedron and use them as cutting planes. However, current approaches rely on solving Linear Programming (LP) problems in order to derive such a hyperplane. In this paper, we present a novel generic approach for learning the facets of the underlying polyhedron by accessing it implicitly via an enumeration oracle in a reduced dimension. This is achieved by embedding the oracle in a variant of the Frank-Wolfe algorithm which is capable of generating strong cutting planes, effectively turning the enumeration oracle into a separation oracle. We demonstrate the effectiveness of our approach with a case study targeting the multidimensional knapsack problem (MKP).

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP . The focus of this article is on the role of the SCIP Optimization Suite in supporting research. SCIP ’s main design principles are discussed, followed by a presentation of the latest performance improvements and developments in version 8.0, which serve both as examples of SCIP ’s application as a research tool and as a platform for further developments. Furthermore, this article gives an overview of interfaces to other programming and modeling languages, new features that expand the possibilities for user interaction with the framework, and the latest developments in several extensions built upon SCIP .

This paper investigates the problem of estimating the size of branch-and-bound (B&B) trees for solving mixed-integer programs. We first prove that the size of the B&B tree cannot be approximated within a factor of 2 for general binary programs, unless [Formula: see text]. Second, we review measures of progress of the B&B search, such as the well-known gap and the often-overlooked tree weight, and propose a new measure, which we call leaf frequency. We study two simple ways to transform these progress measures into B&B tree-size estimates, either as a direct projection or via double-exponential smoothing, a standard time-series forecasting technique. We then combine different progress measures and their trends into nontrivial estimates using machine learning techniques, which yield more precise estimates than any individual measure. The best method that we have identified uses all individual measures as features of a random forest model. In a large computational study, we train and validate all methods on the publicly available MIPLIB and Coral general purpose benchmark sets. On average, the best method estimates B&B tree sizes within a factor of 3 on the set of unseen test instances, even during the early stage of the search, and improves in accuracy as the search progresses. It also achieves a factor of 2 over the entire search on each of the six additional sets of homogeneous instances that we tested. All techniques are available in version 7 of the branch-and-cut framework SCIP. Summary of Contribution: This manuscript develops a method for online estimation of the size of branch-and-bound trees, thereby combining methods of mixed-integer programming and machine learning. We show that high-quality estimations can be obtained using the presented techniques. The methods are also useful in everyday use of branch-and-bound algorithms to obtain approximate search-completion information. The manuscript is accompanied by an extensive online supplement comprising the code used for our simulations and an implementation of all discussed methods in the academic solver SCIP, together with the tools and instructions to train estimators for custom instance sets.

Abstract Potential‐based flows constitute a basic model to represent physical behavior in networks. Under natural assumptions, the flow in such networks must be acyclic. The goal of this article is to exploit this property for the solution of corresponding optimization problems. To this end, we introduce several combinatorial models for acyclic flows, based on binary variables for flow directions. We compare these models and introduce a particular model that tries to capture acyclicity together with the supply/demand behavior. We analyze properties of this model, including variable fixing rules. Our computational results show that the usage of the corresponding constraints speeds up solution times by about a factor of 3 on average and a speed‐up of a factor of almost 5 for the time to prove optimality.

Recently non-convex optimization approaches for solving machine learning problems have gained significant attention. In this paper we explore non-convex boosting in classification by means of integer programming and demonstrate real-world practicability of the approach while circumvent- ing shortcomings of convex boosting approaches. We report results that are comparable to or better than the current state-of-the-art.

Abstract We consider a general class of binary packing problems with a convex quadratic knapsack constraint. We prove that these problems are $$\mathsf {APX}$$ APX -hard to approximate and present constant-factor approximation algorithms based upon two different algorithmic techniques: a rounding technique tailored to a convex relaxation in conjunction with a non-convex relaxation, and a greedy strategy. We further show that a combination of these techniques can be used to yield a monotone algorithm leading to a strategyproof mechanism for a game-theoretic variant of the problem. Finally, we present a computational study of the empirical approximation of these algorithms for problem instances arising in the context of real-world gas transport networks.

Abstract Potential‐based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize the flow between two designated nodes. We show that these problems can be solved for the single source and sink case by reducing the network to a single arc. However, if we additionally consider switches that allow to force the flow to 0 and decouple the potentials, these problems are NP‐hard. Nevertheless, for particular series‐parallel networks, one can use algorithms for the subset sum problem. Moreover, applying network presolving based on generalized series‐parallel structures allows to significantly reduce the size of realistic energy networks.

We present an equivalent, compact reformulation of the ℓ2,1mixed-norm minimization problem for joint sparse signal reconstruction from multiple measurement vectors (MMVs). The reformulation builds upon a compact parameterization, which models the row-norms of the sparse signal representation as parameters of interest, resulting in a significant reduction of the MMV problem size. Given the sparse vector of row-norms, the joint sparse signal can be computed from the MMVs in closed form. For the special case of uniform linear sampling, we present an extension of the compact formulation for gridless parameter estimation by means of semidefinite programming. Furthermore, we derive in this case from our compact problem formulation the exact equivalence between the ℓ2,1mixed-norm minimization and the atomic-norm minimization.

Infeasible network flow problems with supplies and demands can be characterized via violated cut‐inequalities of the classical Gale‐Hoffman theorem. Written as a linear program, irreducible infeasible subsystems (IISs) provide a different means of infeasibility characterization. In this article, we answer a question left open in the literature by showing a one‐to‐one correspondence between IISs and Gale‐Hoffman‐inequalities in which one side of the cut has to be weakly connected. We also show that a single max‐flow computation allows one to compute an IIS. Moreover, we prove that finding an IIS of minimal cardinality in this special case of flow networks is strongly ‐hard. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(2), 121–129 2016

The problem of finding a minimum ℓ 1 -norm solution to an underdetermined linear system is an important problem in compressed sensing, where it is also known as basis pursuit . We propose a heuristic optimality check as a general tool for ℓ 1 -minimization, which often allows for early termination by “guessing” a primal-dual optimal pair based on an approximate support. Moreover, we provide an extensive numerical comparison of various state-of-the-art ℓ 1 -solvers that have been proposed during the last decade, on a large test set with a variety of explicitly given matrices and several right-hand sides per matrix reflecting different levels of solution difficulty. The results, as well as improvements by the proposed heuristic optimality check, are analyzed in detail to provide an answer to the question which algorithm is the best.

The computational complexity of a problem arising in the context of sparse optimization is considered, namely, the projection onto the set of k-cosparse vectors w.r.t. some given matrix Ω. It is shown that this projection problem is (strongly) NP-hard, even in the special cases in which the matrix Ω contains only ternary or bipolar coefficients. Interestingly, this is in contrast to the projection onto the set of k-sparse vectors, which is trivially solved by keeping only the k largest coefficients.

This paper deals with the computational complexity of conditions which guarantee that the NP-hard problem of finding the sparsest solution to an underdetermined linear system can be solved by efficient algorithms. In the literature, several such conditions have been introduced. The most well-known ones are the mutual coherence, the restricted isometry property (RIP), and the nullspace property (NSP). While evaluating the mutual coherence of a given matrix is easy, it has been suspected for some time that evaluating RIP and NSP is computationally intractable in general. We confirm these conjectures by showing that for a given matrix${\mbi{A}}$and positive integer$k$, computing the best constants for which the RIP or NSP hold is, in general, NP-hard. These results are based on the fact that determining the spark of a matrix is NP-hard, which is also established in this paper. Furthermore, we also give several complexity statements about problems related to the above concepts.

Morse matchings capture the essential structural information of discrete Morse functions. We show that computing optimal Morse matchings is NP-hard and give an integer programming formulation for the problem. Then we present polyhedral results for the corresponding polytope and report on computational results.