Search

Demand response (DR) has been increasingly growing in significance among the solutions to tackle climate change, by supporting the development of intermittent renewable energy sources in the smart grid. Many models based on mathematical optimization have been developed to address the challenge of supporting residential customers in providing flexibility services to the grid. However, comparing and applying those models is not always straightforward because of particular data handling or specific assumptions. In this work, we take advantage of the common aspects of DR models to build a metamodel, and hence an open source Python library that aims to unify the concepts and the data streaming in and out of the underlying mathematical optimization models. We demonstrate the effectiveness of the metamodel and of the Python library by using it to implement a task scheduler and to optimize the energy consumption for two dwellings. [ABSTRACT FROM AUTHOR]

The classical alternating current optimal power flow problem is highly nonconvex and generally hard to solve. Convex relaxations, in particular semidefinite, second-order cone, convex quadratic, and linear relaxations, have recently attracted significant interest. The semidefinite relaxation is the strongest among them and is exact for many cases. However, the computational efficiency for solving large-scale semidefinite optimization is lower than for second-order cone optimization. We propose a conic relaxation obtained by combining semidefinite optimization with the reformulation-linearization technique, commonly known as RLT. The proposed relaxation is stronger than the second-order cone relaxation and nearly as tight as the standard semidefinite relaxation. Computational experiments using standard test cases with up to 6515 buses show that the time to solve the new conic relaxation is up to one order of magnitude lower than for the chordal relaxation, a semidefinite relaxation technique that exploits the sparsity of power networks. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses articles in the issue on topics including global optimization, mathematical optimization, and linear optimization.

This paper provides new results on the application of semidefinite optimization to satisfiability by studying the connection between semidefinite optimization and minimal unsatisfiability. We use a semidefinite least squares problem to assign weights to the clauses of a propositional formula in conjunctive normal form. We then show that these weights are a measure of the necessity of each clause in rendering the formula unsatisfiable, the weight of a necessary clause is strictly greater than the weight of any unnecessary clause. In particular, we show the following results: first, if a formula is minimal unsatisfiable, then all of its clauses have the same weight; second, if a clause does not belong to any minimal unsatisfiable subformula, then its weight is zero. An additional contribution of this paper is a demonstration of how the infeasibility of a semidefinite optimization problem can be tested using a semidefinite least squares problem by extending an earlier result for linear optimization. The connection between the semidefinite least squares problem and Farkas’ Lemma for semidefinite optimization is also discussed. [ABSTRACT FROM AUTHOR]

Many important NP-hard combinatorial problems can be efficiently approximated using semidefinite programming relaxations. We propose a new hierarchy of semidefinite relaxations for classes of such problems that are based on graphs and for which the projection of the problem onto a subgraph shares the same structure as the original problem. This includes the well-studied max-cut and stable-set problems. Each level k of the proposed hierarchy consists of the basic semidefinite relaxation of the problem augmented by the constraints enforcing the structural projection condition on every k-node subgraph of the problem. This hierarchy has the distinguishing feature that all the relaxations are formulated in the space of the original semidefinite relaxation. Because the size of the relaxations increases rapidly with the number of subgraphs, we explore the possibility of adding the projection constraints only for selected subgraphs. Preliminary computational results show that the proposed hierarchy yields improved bounds when compared to the initial relaxation for benchmark instances of the max-cut and stable-set problems, and that the improved bounds result in significantly smaller enumeration trees when the relaxation is used in a branch-and-bound scheme. [ABSTRACT FROM AUTHOR]

This paper examines the polytope of feasible power generation schedules in the unit commitment (UC) problem. We provide computational results comparing formulations for the UC problem commonly found in the literature. We introduce a new class of inequalities, giving a tighter description of feasible operating schedules for generators. Computational results show that these inequalities can significantly reduce overall solution times. [ABSTRACT FROM PUBLISHER]

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]

This paper is concerned with the single-row facility layout problem (SRFLP). A globally optimal solution to the SRFLP is a linear placement of rectangular facilities with varying lengths that achieves the minimum total cost associated with the (known or projected) interactions between them. We demonstrate that the combination of a semidefinite programming relaxation with cutting planes is able to compute globally optimal layouts for large SRFLPs with up to 30 facilities. In particular, we report the globally optimal solutions for two sets of SRFLPs previously studied in the literature, some of which have remained unsolved since 1988. [ABSTRACT FROM AUTHOR]

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]

Abstract: The facility layout problem is concerned with the arrangement of a given number of rectangular facilities so as to minimize the total cost associated with the (known or projected) interactions between them. We consider the one-dimensional space-allocation problem (ODSAP), also known as the single-row facility layout problem, which consists in finding an optimal linear placement of facilities with varying dimensions on a straight line. We construct a semidefinite programming (SDP) relaxation providing a lower bound on the optimal value of the ODSAP. To the best of our knowledge, this is the first non-trivial global lower bound for the ODSAP in the published literature. This SDP approach implicitly takes into account the natural symmetry of the problem and, unlike other algorithms in the literature, does not require the use of any explicit symmetry-breaking constraints. Furthermore, the structure of the SDP relaxation suggests a simple heuristic procedure which extracts a feasible solution to the ODSAP from the optimal matrix solution to the SDP relaxation. Computational results show that this heuristic yields a solution which is consistently within a few percentage points of the global optimal solution. [Copyright &y& Elsevier]

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]