1,720,974 research outputs found
Critical node/edge detection problems on trees
Full text linkWe consider the problem of removing a limited subset of nodes and/or edges from a graph in order to minimize the so-called pairwise connectivity of the residual graph, which is defined as the total cost of the pairs of nodes still connected by a path. This is a well-studied version of a family of problems known as critical node or edge detection problems. However, while most of the literature focuses on deleting nodes or edges separately, we allow the simultaneous removal of nodes and edges. We consider both the case in which the nodes and edges removed must satisfy a joint weight limit, and the case in which two separate weight limits are given for nodes and edges. We study the complexity of several problems of this type when the given graph is a tree, providing NP-hardness results or polynomial-time algorithms for the different cases that we analyze
Balas formulation for the union of polytopes is optimal
No full textA celebrated theorem of Balas gives a linear mixed-integer formulation for the union of two nonempty polytopes whose relaxation gives the convex hull of this union. The number of inequalities in Balas formulation is linear in the number of inequalities that describe the two polytopes and the number of variables is doubled. In this paper we show that this is best possible: in every dimension there exist two nonempty polytopes such that if a formulation for the convex hull of their union has a number of inequalities that is polynomial in the number of inequalities that describe the two polytopes, then the number of additional variables is at least linear in the dimension of the polytopes. We then show that this result essentially carries over if one wants to approximate the convex hull of the union of two polytopes and also in the more restrictive setting of lift-and-project
Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective
Full text linkWe consider the integer points in a unimodular cone K ordered by a lexicographic rule defined by a lattice basis. To each integer point x in K we associate a family of inequalities (lex-inequalities) that define the convex hull of the integer points in K that are not lexicographically smaller than x. The family of lex-inequalities contains the Chvátal–Gomory cuts, but does not contain and is not contained in the family of split cuts. This provides a finite cutting plane method to solve the integer program min { cx: x∈ S∩ Zn} , where S⊂ Rn is a compact set and c∈ Zn. We analyze the number of iterations of our algorithm
Towards Lower Bounds on the Depth of ReLU Neural Networks
Full text linkWe contribute to a better understanding of the class of functions that is represented by a neural network with ReLU activations and a given architecture. Using techniques from mixed-integer optimization, polyhedral theory, and tropical geometry, we provide a mathematical counterbalance to the universal approximation theorems which suggest that a single hidden layer is sufficient for learning tasks. In particular, we investigate whether the class of exactly representable functions strictly increases by adding more layers (with no restrictions on size). This problem has potential impact on algorithmic and statistical aspects because of the insight it provides into the class of functions represented by neural hypothesis classes. However, to the best of our knowledge, this question has not been investigated in the neural network literature. We also present upper bounds on the sizes of neural networks required to represent functions in these neural hypothesis classes
Split cuts in the plane
Full text linkWe provide a polynomial time cutting plane algorithm based on split cuts to solve integer programs in the plane. We also prove that the split closure of a polyhedron in the plane has polynomial size
The role of rationality in integer-programming relaxations
Full text linkFor a finite set X⊂ Zd that can be represented as X= Q∩ Zd for some polyhedron Q, we call Q a relaxation of X and define the relaxation complexity rc (X) of X as the least number of facets among all possible relaxations Q of X. The rational relaxation complexity rc Q(X) restricts the definition of rc (X) to rational polyhedra Q. In this article, we focus on X= Δ d , the vertex set of the standard simplex, which consists of the null vector and the standard unit vectors in Rd . We show that rc (Δ d) ≤ d for every d≥ 5 . That is, since rc Q(Δ d) = d+ 1 , irrationality can reduce the minimal size of relaxations. This answers an open question posed by Kaibel and Weltge (Math Program 154(1):407–425, 2015). Moreover, we prove the asymptotic statement rc(Δd)∈O(dlog(d)) , which shows that the ratio rc(Δd)rcQ(Δd) goes to 0, as d→ ∞
Complexity of Branch-and-Bound and Cutting Planes in Mixed-Integer Optimization - II
Full text linkWe study the complexity of cutting planes and branching schemes from a theoretical point of view. We give some rigorous underpinnings to the empirically observed phenomenon that combining cutting planes and branching into a branch-and-cut framework can be orders of magnitude more efficient than employing these tools on their own. In particular, we give general conditions under which a cutting plane strategy and a branching scheme give a provably exponential advantage in efficiency when combined into branch-and-cut. The efficiency of these algorithms is evaluated using two concrete measures: number of iterations and sparsity of constraints used in the intermediate linear/convex programs. To the best of our knowledge, our results are the first mathematically rigorous demonstration of the superiority of branch-and-cut over pure cutting planes and pure branch-and-bound
An Outlook on the Future Marine Traffic Management System for Autonomous Ships
No full textIn the shipping digitalisation process, the peak will be reached with the advent of a wholly autonomous and at the same time safe and reliable ship. Full autonomy could be obtained by two linked Artificial-Intelligence systems representing the ship navigator and the ship engineer that possess sensing and analysis skills, situational awareness, planning, and control capabilities. Many efforts have been made in developing onboard systems; however, the shore facilities are not ready yet to deal with these new technologies. The paper aims to present the innovative technologies and methodologies needed to develop a futuristic Vessel Traffic System. The proposed systems will aim at faultless data acquisition and processing, provide input to decision-making systems, and suggest evasive manoeuvre; to deal with hazards and systems failure without human intervention onboard. The system is composed of three different and interacting layers. The first is an artificially intelligent tool to detect and control autonomous ships, thanks to situation recognition and obstacle avoidance strategies. The second is an orchestration and management platform designed to coordinate the sensing/actuation infrastructure and the AI algorithms' results made available by multiple ships, mustering edge, and distributed computing techniques to fulfil the specific harsh requirements of the sea environment. The final part is a holistic guidance-navigation-control framework to manage autonomous ships' navigation in a crowded area. Eventually, a cyber-physical scenario, using both a ship digital-twin and a real model-scale ship, is suggested to test and validate the innovative system without the availability of a full-scale scenario
- …
