We present a prototype of a software tool for exploration of multiple combinatorial optimisation problems in large real-world and synthetic complex networks. Our tool, called GraphCombEx (an acronym of Graph Combinatorial Explorer), provides a unified framework for scalable computation of high-quality suboptimal solutions and bounds for a number of widely studied combinatorial optimisation problems in large graphs. The problems currently supported include: maximum clique, graph colouring, maximum independent set, minimum vertex clique covering, minimum dominating set, as well as the longest simple cycle problem. Suboptimal solutions and intervals for optimal objective values are estimated using scalable heuristics. GraphCombEx has previously or currently been tested in scenarios of exploring synthetic graph models, as well as real-world networks ranging from social network samples, biological networks, to very large networks from the SNAP network data repository. The tool has already been successfully used to support a number of recent studies and is particularly beneficial in exploring the combinatorial properties of previously unseen network data, before applying more sophisticated custom optimisation algorithms.
Another specific property of NP-hard combinatorial optimisation problems in networks is that these are often formulated as integer linear programs. Out-of-the-box mixed integer linear programming (MILP) software tools are increasingly used in solving these problems in practical applications @cite_44 @cite_3 . However, open-source MILP software and network exploration software still seem to be perceived in relative isolation, which is another interesting area of challenge.
@cite_44 @cite_3
2075779886 1500443963 1993119087 2519037599
We investigate the computational complexity of two closely related classes of combinatorial optimization problems for linear systems which arise in various fields such as machine learning, operations research and pattern recognition. In the first class (Min ULR) one wishes, given a possibly infeasible system of linear relations, to find a solution that violates as few relations as possible while satisfying all the others. In the second class (Min RVLS) the linear system is supposed to be feasible and one looks for a solution with as few nonzero variables as possible. For both Min ULR and Min RVLS the four basic types of relational operators =, ⩾, > and ≠ are considered. While Min RVLS with equations was mentioned to be NP-hard in (Garey and Johnson, 1979), we established in (Amaldi; 1992; Amaldi and Kann, 1995) that min ULR with equalities and inequalities are NP-hard even when restricted to homogeneous systems with bipolar coefficients. The latter problems have been shown hard to approximate in (, 1993). In this paper we determine strong bounds on the approximability of various variants of Min RVLS and min ULR, including constrained ones where the variables are restricted to take binary values or where some relations are mandatory while others are optional. The various NP-hard versions turn out to have different approximability properties depending on the type of relations and the additional constraints, but none of them can be approximated within any constant factor, unless P = NP. Particular attention is devoted to two interesting special cases that occur in discriminant analysis and machine learning. In particular, we disprove a conjecture of van Horn and Martinez (1992) regarding the existence of a polynomial-time algorithm to design linear classifiers (or perceptrons) that involve a close-to-minimum number of features. We propose a new approach for understanding the algorithm-specific empiricalh ardness of NP-Hard problems. In this work we focus on the empirical hardness of the winner determination problem--an optimization problem arising in combinatorial auctions--when solved by ILOG's CPLEX software. We consider nine widely-used problem distributions and sample randomly from a continuum of parameter settings for each distribution. We identify a large number of distribution-nonspecific features of data instances and use statisticalregression techniques to learn, evaluate and interpret a function from these features to the predicted hardness of an instance. Several important NP-hard combinatorial optimization problems can be posed as packing covering integer programs; the randomized rounding technique of Raghavan and Thompson is a powerful tool with which to approximate them well. We present one elementary unifying property of all these integer linear programs and use the FKG correlation inequality to derive an improved analysis of randomized rounding on them. This yields a pessimistic estimator, thus presenting deterministic polynomial-time algorithms for them with approximation guarantees that are significantly better than those known. Many NP-hard winner determination problems admit polynomial-time algorithms when restricting inputs to be single-peaked. Commonly, such algorithms employ dynamic programming along the underlying axis. We introduce a new technique: carefully chosen integer linear programming (IP) formulations for certain voting problems admit an LP relaxation which is totally unimodular if preferences are single-peaked, and which thus admits an integral optimal solution. This technique gives fast algorithms for finding optimal committees under the PAV and Chamberlin-Courant voting rules under single-peaked preferences, as well as for certain OWA-based rules. Under single-crossing preferences, Young scores can also be calculated. An advantage of this technique is that no special-purpose algorithm needs to be used to exploit structure in the input preferences: any standard IP solver will terminate in the first iteration if the input is single-peaked, and will continue to work otherwise.