Search

The increasing penetration of renewable energy sources in the electricity grid brings new operational challenges. This brings up the need for effective means to provide demand response in spite of its distributed nature throughout the grid. Aggregators can be created to manage a set of such demand response resources, but deciding how to allocate an aggregator’s resources is an important problem. One of the aspects that needs more attention is the impact of the transmission system on these decisions. In this paper, we propose a short-term optimization model for allocating demand response(DR) resources as well as generation resources to supply external demand that is offered after the scheduling decision is made. The DR resources will only be available for use after the scheduling decision is made. Finally, our work also considers the impact of congestion in the transmission system when allocating DR. We propose the use of a semidefinite relaxation to provide a good initial point to solve our model with the aim of guaranteeing that we will find an optimal solution. Results from numerical tests with the IEEE 96-RTS and the ACTIVSG500 test grids are reported. We found that DR resources mitigates congestion management, allowing the generators to supply more of the external demand that is offered. Besides that, we observe that using our proposed solution methodology, we were able to obtain optimal solution for both cases studies, which is not the case when solving the original formulation for the ACTIVSG500 grid. [ABSTRACT FROM AUTHOR]

Near-optimality robustness extends multilevel optimization with a limited deviation of a lower level from its optimal solution, anticipated by higher levels. We analyze the complexity of near-optimal robust multilevel problems, where near-optimal robustness is modelled through additional adversarial decision-makers. Near-optimal robust versions of multilevel problems are shown to remain in the same complexity class as the problem without near-optimality robustness under general conditions. [ABSTRACT FROM AUTHOR]

This paper introduces the algorithmic design and implementation of Tulip, an open-source interior-point solver for linear optimization. It implements a regularized homogeneous interior-point algorithm with multiple centrality corrections, and therefore handles unbounded and infeasible problems. The solver is written in Julia, thus allowing for a flexible and efficient implementation: Tulip's algorithmic framework is fully disentangled from linear algebra implementations and from a model's arithmetic. In particular, this allows to seamlessly integrate specialized routines for structured problems. Extensive computational results are reported. We find that Tulip is competitive with open-source interior-point solvers on the H. Mittelmann's benchmark of barrier linear programming solvers. Furthermore, we design specialized linear algebra routines for structured master problems in the context of Dantzig–Wolfe decomposition. These routines yield a tenfold speedup on large and dense instances that arise in power systems operation and two-stage stochastic programming, thereby outperforming state-of-the-art commercial interior point method solvers. Finally, we illustrate Tulip's ability to use different levels of arithmetic precision by solving problems in extended precision. [ABSTRACT FROM AUTHOR]

This is the editorial for the Special Issue on Energy Networks. [ABSTRACT FROM AUTHOR]

The facility layout problem is concerned with finding an arrangement of non-overlapping indivisible departments within a facility so as to minimize the total expected flow cost. In this paper we consider the special case of multi-row layout in which all the departments are to be placed in three or more rows, and our focus is on, for the first time, solutions for large instances. We first propose a new mixed integer linear programming formulation that uses continuous variables to represent the departments' location in both x and y coordinates, where x represents the position of a department within a row and y represents the row assigned to the department. We prove that this formulation always achieves an optimal solution with integer values of y, but it is limited to solving instances with up to 13 departments. This limitation motivates the application of a two-stage optimization algorithm that combines two mathematical optimization models by taking the output of the first-stage model as the input of the second-stage model. This algorithm is, to the best of our knowledge, the first one in the literature reporting solutions for instances with up to 100 departments. [ABSTRACT FROM AUTHOR]

With the increasing presence of renewable energy sources in the electrical power grid, demand response via thermostatic appliances such as electric water heaters is a promising way to compensate for the significant variability in renewable power generation. We propose a multistage stochastic optimization model that computes the optimal day-ahead target profile of the mean thermal energy contained in a large population of heaters, given various possible wind power production and uncontrollable load scenarios. This optimal profile is calculated to make the variable net demand as even as possible. [ABSTRACT FROM AUTHOR]

We study demand-side participation in an electricity market for an industrial consumer of electricity, with some flexibility to reduce demand, and capable of offering interruptible load reserve. Our consumer is a price maker, and the impact of its actions in the market is modelled via a bi-level optimization problem. We have extended a standard model for optimal strategic consumption, to the case where reserve offer curves need to be optimized simultaneously with consumption curves; our models provide intuition into this interaction. Furthermore, we provide tailor-made solution strategies for the resulting problems under uncertainty, and report numerical results of our implementation on instances over the full New Zealand network yielding a realistic and large problem set. [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.

We consider the maximum k-cut problem that consists in partitioning the vertex set of a graph into k subsets such that the sum of the weights of edges joining vertices in different subsets is maximized. We focus on identifying effective classes of inequalities to tighten the semidefinite programming relaxation. We carry out an experimental study of four classes of inequalities from the literature: clique, general clique, wheel and bicycle wheel. We considered 10 combinations of these classes and tested them on both dense and sparse instances for k∈{3,4,5,7}. Our computational results suggest that the bicycle wheel and wheel are the strongest inequalities for k=3, and that for k∈{4,5,7} the wheel inequalities are the strongest by far. Furthermore, we observe an improvement in the performance for all choices of k when both bicycle wheel and wheel are used, at the cost of 72% more CPU time on average when compared with using only one of them. [ABSTRACT FROM AUTHOR]

The minimum k-partition (M kP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. The main contribution of this paper is the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) for the M kP problem. The two key ingredients for this algorithm are: the combination of semidefinite programming with polyhedral results; and a novel iterative clustering heuristic (ICH) that finds feasible solutions for the M kP problem. We compare ICH to the hyperplane rounding techniques of Goemans and Williamson and of Frieze and Jerrum, and the computational results support the conclusion that ICH consistently provides better feasible solutions for the M kP problem. ICH is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-bound tree. The SBC algorithm computes globally optimal solutions for dense graphs with up to 60 vertices, for grid graphs with up to 100 vertices, and for different values of k, providing a fast exact approach for k≥3. [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]