Search

Semidefinite Programming (SDP) is a powerful technique to compute tight lower bounds for Optimal Power Flow (OPF) problems. Even using clique decomposition techniques, semidefinite relaxations are still computationally demanding. However, there are many different clique decompositions for the same SDP problem and they are not equivalent in terms of computation time. In this paper, we propose a new strategy to compute efficient clique decompositions with a clique merging heuristic. This heuristic is based on two different estimates of the computational burden of an SDP problem: the size of the problem and an estimation of a per-iteration cost for a state-of-the-art interior-point algorithm. We compare our strategy with other algorithms on MATPOWER instances and we show a significant decrease in solver time. [ABSTRACT FROM AUTHOR]

This work considers the graph partitioning problem known as maximum k -cut. It focuses on investigating features of a branch-and-bound method to obtain global solutions. An exhaustive experimental study is carried out for the two main components of a branch-and-bound algorithm: Computing bounds and branching strategies. In particular, we propose the use of a variable neighborhood search metaheuristic to compute good feasible solutions, the k -chotomic strategy to split the problem, and a branching rule based on edge weights to select variables. Moreover, we analyze a linear relaxation strengthened by semidefinite-based constraints, a cutting plane algorithm, and node selection strategies. Computational results show that the resulting method outperforms the state-of-the-art approach and discovers the solution of several instances, especially for problems with k ≥ 5. [ABSTRACT FROM AUTHOR]

Despite the many advantages of interior-point algorithms over active-set methods for linear optimization, one of the remaining practical challenges is their current limitation to efficiently solve series of related problems by an effective warmstarting strategy. As a remedy, in this paper we present a new infeasible-interior-point approach to quickly reoptimize an initial problem instance after data perturbations, or a new linear programming relaxation after adding cutting planes for discrete or combinatorial problems. Based on the detailed complexity analysis of the underlying algorithm, we perform a comparative analysis to coldstart initialization schemes and present encouraging computational results with iteration savings of around 50% on average for perturbations of the Netlib linear programs (LPs) and successive linear programming relaxations of max-cut and the traveling salesman problem. [ABSTRACT FROM AUTHOR]

In VLSI layout, floorplanning refers to the task of placing macrocells on a chip without overlap while minimizing design objectives such as timing, congestion, and wire length. Experienced VLSI designers have traditionally been able to produce more efficient floorplans than automated methods. However, with the increasing complexity of modern circuits, manual design flows have become infeasible. An efficient top-down strategy for overlap removal which repairs overlaps in floorplans produced by placement algorithms or rough floorplanning methodologies is presented in this article. The algorithmic framework proposed incorporates a novel geometric shifting technique coupled with topological constraint graphs and linear programming within a top-down flow. The effectiveness of this framework is quantified across a broad range of floorplans produced by multiple tools. The method succeeds in producing valid placements in almost all cases; moreover, compared with leading methods, it requires only one-fifth of the run-time and produces placements with 4-13% less wire length and up to 43% less cell movement. [ABSTRACT FROM AUTHOR]

The article focuses on several studies related to the concepts of satisfiability, Boolean modeling and computation. One study described disjunctive normal form (DNF) tautologies with terms conflicting in one or two variables pairwise and possessing a tree-like structure. Another study proposed a semidefinite programming relaxation for the satisfiability problem. A third study discussed theoretical and experimental results on the use of satisfiability problem (SAT) algorithms for colouring special classes of graphs.

We revisit a regularization technique of Mészáros for handling free variables within interior-point methods for conic linear optimization. We propose a simple computational strategy, supported by a global convergence analysis, for handling the regularization. Using test problems from benchmark suites and recent applications, we demonstrate that the modern code SDPT3 modified to incorporate the proposed regularization is able to achieve the same or significantly better accuracy over standard options of splitting variables, using a quadratic cone, and solving indefinite systems. [ABSTRACT FROM AUTHOR]

The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such an instance, the SAT problem asks whether there is a truth assignment to the variables such that the formula is satisfied. It is well known that SAT is in general NP-complete, although several important special cases can be solved in polynomial time. Semidefinite programming (SDP) refers to the class of optimization problems where a linear function of a matrix variableXis maximized (or minimized) subject to linear constraints on the elements ofXand the additional constraint thatXbe positive semidefinite. We are interested in the application of SDP to satisfiability problems, and in particular in how SDP can be used to detect unsatisfiability. In this paper we introduce a new SDP relaxation for the satisfiability problem. This SDP relaxation arises from the recently introduced paradigm of “higher liftings” for constructing semidefinite programming relaxations of discrete optimization problems. To derive the SDP relaxation, we first formulate SAT as an optimization problem involving matrices. Relaxing this formulation yields an SDP which significantly improves on the previous relaxations in the literature. The important characteristics of the SDP relaxation are its ability to prove that a given SAT formula is unsatisfiable independently of the lengths of the clauses in the formula, its potential to yield truth assignments satisfying the SAT instance if a feasible matrix of sufficiently low rank is computed, and the fact that it is more amenable to practical computation than previous SDPs arising from higher liftings. We present theoretical and computational results that support these claims. [ABSTRACT FROM AUTHOR]

This paper is concerned with the analysis and comparison of semidefinite programming (SDP) relaxations for the satisfiability (SAT) problem. Our presentation is focussed on the special case of 3-SAT, but the ideas presented can in principle be extended to any instance of SAT specified by a set of boolean variables and a propositional formula in conjunctive normal form. We propose a new SDP relaxation for 3-SAT and prove some of its theoretical properties. We also show that, together with two SDP relaxations previously proposed in the literature, the new relaxation completes a trio of linearly sized relaxations with increasing rank-based guarantees for proving satisfiability. A comparison of the relative practical performances of the SDP relaxations shows that, among these three relaxations, the new relaxation provides the best tradeoff between theoretical strength and practical performance within an enumerative algorithm. [ABSTRACT FROM AUTHOR]

The floorplanning (or facility layout) problem consists in finding the optimal positions for a given set of modules of fixed area (but perhaps varying height and width) within a facility such that the distances between pairs of modules that have a positive connection cost are minimized. This is a hard combinatorial optimization problem; even the restricted version where the shapes of the modules are fixed and the optimization is taken over a fixed finite set of possible module locations is NP-hard. In this paper, we extend the concept of target distance introduced by Etawil and Vannelli and apply it to derive the AR (Attractor-Repeller) model which is designed to improve upon the NLT method of van Camp et al. This new model is designed to find a good initial point for the Stage-3 NLT solver and has the advantage that it can be solved very efficiently using a suitable optimization algorithm. Because the AR model is not a convex optimization problem, we also derive a convex version of the model and explore the generalized target distances that arise in this derivation. Computational results demonstrating the potential of our approach are presented. [ABSTRACT FROM AUTHOR]