Search

The problem of packing a set of circles into the smallest surrounding container is considered. This problem arises in different application areas such as automobile, textile, food, and chemical industries. The so-called circle packing problem can be cast as a nonconvex quadratically constrained program, and is difficult to solve in general. An iterative solution approach based on a bisection-type algorithm on the radius of the larger circle is provided. The present algorithm discretizes the container into small cells and solves two different integer linear programming formulations proposed for a restricted and a relaxed version of the original problem. The present algorithm is enhanced with solution space reduction, bound tightening and variable elimination techniques. Then, a computational study is performed to evaluate the performance of the algorithm. The present algorithm is compared with BARON and Gurobi that solve the original nonlinear formulation and heuristic methods from literature, and obtain promising results.

The pooling problem is a classical NP-hard problem in the chemical process and petroleum industries. This problem is modeled as a nonlinear, nonconvex network flow problem in which raw materials with different specifications are blended in some intermediate tanks, and mixed again to obtain the final products with desired specifications. The analysis of the pooling problem is quite an active research area, and different exact formulations, relaxations and restrictions are proposed. In this paper, we focus on a recently proposed rank-one-based formulation of the pooling problem. In particular, we study a recurring substructure in this formulation defined by the set of nonnegative, rank-one matrices with bounded row sums, column sums, and the overall sum. We show that the convex hull of this set is second-order cone representable. In addition, we propose an improved compact-size polyhedral outer-approximation and families of valid inequalities for this set. We further strengthen these convexification approaches with the help of various bound tightening techniques specialized to the instances of the pooling problem. Our computational experiments show that the newly proposed polyhedral outer-approximation can improve upon the traditional linear programming relaxations of the pooling problem in terms of the dual bound. Furthermore, bound tightening techniques reduce the computational time spent on both the exact, linear programming and mixed-integer linear programming relaxations., Comment: 45 pages, 4 figures, including appendix

Maintenance planning plays a key role in power system operations under uncertainty by helping system operators ensure a reliable and secure power grid. This paper studies a short-term condition-based integrated maintenance planning with operations scheduling problem while considering the unexpected failure possibilities of generators as well as transmission lines. We formulate this problem as a two-stage stochastic mixed-integer program with failure scenarios sampled from the sensor-driven remaining lifetime distributions of the individual system elements whereas a joint chance-constraint consisting of Poisson Binomial random variables is introduced to account for failure risks. Because of its intractability, we develop a cutting-plane method to obtain an exact reformulation of the joint chance-constraint by proposing a separation subroutine and deriving stronger cuts as part of this procedure. To solve large-scale instances, we derive a second-order cone programming based safe approximation of this constraint. Furthermore, we propose a decomposition-based algorithm implemented in parallel fashion for solving the resulting stochastic program, by exploiting the features of the integer L-shaped method and the special structure of the maintenance and operations scheduling problem to derive stronger optimality cuts. We further present preprocessing steps over transmission line flow constraints to identify redundancies. To illustrate the computational performance and efficiency of our algorithm compared to more conventional maintenance approaches, we design a computational study focusing on a weekly plan with daily maintenance and hourly operational decisions involving detailed unit commitment subproblems. Our computational results on various IEEE instances demonstrate the computational efficiency of the proposed approach with reliable and cost-effective maintenance and operational schedules.

Unit Commitment (UC) and Optimal Power Flow (OPF) are two fundamental problems in short-term electric power systems planning that are traditionally solved sequentially. The state-of-the-art mostly uses a direct current flow approximation of the power flow equations in the UC-level and the generator commitments obtained are sent as input to the OPF-level. However, such an approach can yield infeasible or suboptimal generator schedules. In this paper, we aim to simultaneously solve the UC Problem with alternating current (AC) power flow equations, which combines the challenging nature of both UC and OPF problems. Due to the highly nonconvex nature of the AC flow equations, we utilize the mixed-integer second-order cone programming (MISOCP) relaxation of the UC Problem as the basis of our solution approach. For smaller instances, we develop two different algorithms that exploit the recent advances in the OPF literature and obtain high-quality feasible solutions with provably small optimality gaps. For larger instances, we propose a novel Lagrangian decomposition based approach that yields promising results.

The benefits of transmission line switching are well-known in terms of reducing operational cost and improving system reliability of power systems. However, finding the optimal power network configuration is a challenging task due to the combinatorial nature of the underlying optimization problem. In this work, we identify a certain "node-based" set that appears as substructure of the optimal transmission switching problem and then conduct a polyhedral study of this set. We construct an extended formulation of the integer hull of this set and present the inequality description of the integer hull in the original space in some cases. These inequalities in the original space can be used as cutting-planes for the transmission line switching problem. Finally, we present the results of our computational experiments using these cutting-planes on difficult test cases from the literature.

In this paper, we study the Multi-Period Optimal Power Flow problem (MOPF) with electric vehicles (EV) under emission considerations. We integrate three different real-world datasets: household electricity consumption, marginal emission factors, and EV driving profiles. We present a systematic solution approach based on second-order cone programming to find globally optimal solutions for the resulting nonconvex optimization problem. To the best of our knowledge, our paper is the first to propose such a comprehensive model integrating multiple real datasets and a promising solution method for the EV-aware MOPF problem. Our computational experiments on various instances with up to 2000 buses demonstrate that our solution approach leads to high-quality feasible solutions with provably small optimality gaps. In addition, we show the importance of coordinated EV charging to achieve significant emission savings and reductions in cost. In turn, our findings can provide insights to decision-makers on how to incentivize EV drivers depending on the trade-off between cost and emission., Comment: 10 pages, 6 figures, 2 tables

In this paper, we consider a distributionally robust optimization (DRO) model in which the ambiguity set is defined as the set of distributions whose Kullback-Leibler (KL) divergence to an empirical distribution is bounded. Utilizing the fact that KL divergence is an exponential cone representable function, we obtain the robust counterpart of the KL divergence constrained DRO problem as a dual exponential cone constrained program under mild assumptions on the underlying optimization problem. The resulting conic reformulation of the original optimization problem can be directly solved by a commercial conic programming solver. We specialize our generic formulation to two classical optimization problems, namely, the Newsvendor Problem and the Uncapacitated Facility Location Problem. Our computational study in an out-of-sample analysis shows that the solutions obtained via the DRO approach yield significantly better performance in terms of the dispersion of the cost realizations while the central tendency deteriorates only slightly compared to the solutions obtained by stochastic programming.

In this letter, we present an alternative mixed-integer non-liner programming formulation of the reactive optimal power flow (ROPF) problem. We utilize a mixed-integer second-order cone programming (MISOCP) based approach to find global optimal solutions of the proposed ROPF problem formulation. We strengthen the MISOCP relaxation via the addition of convex envelopes and cutting planes. Computational experiments on challenging test cases show that the MISOCP-based approach yields promising results compared to a semidefinite programming based approach from the literature.

We consider optimization problems involving the multiplication of variable matrices to be selected from a given family, which might be a discrete set, a continuous set or a combination of both. Such nonlinear, and possibly discrete, optimization problems arise in applications from biology and material science among others, and are known to be NP-Hard for a special case of interest. We analyze the underlying structure of such optimization problems for two particular applications and, depending on the matrix family, obtain compact-size mixed-integer linear or quadratically constrained quadratic programming reformulations that can be solved via commercial solvers. Finally, we present the results of our computational experiments, which demonstrate the success of our approach compared to heuristic and enumeration methods predominant in the literature.

It is well-known that the second-order cone can be outer-approximated to an arbitrary accuracy $\epsilon$ by a polyhedral cone of compact size defined by irrational data. In this paper, we propose two rational polyhedral outer-approximations of compact size retaining the same guaranteed accuracy $\epsilon$. The first outer-approximation has the same size as the optimal but irrational outer-approximation from the literature. In this case,we provide a practical approach to obtain such an approximation defined by the smallest integer coefficients possible, which requires solving a few, small-size integer quadratic programs. The second outer-approximation has a size larger than the optimal irrational outer-approximation by a linear additive factor in the dimension of the second-order cone. However, in this case, the construction is explicit, and it is possible to derive an upper bound on the largest coefficient, which is sublinear in $\epsilon$ and logarithmic in the dimension. We also propose a third outer-approximation, which yields the best possible approximation accuracy given an upper bound on the size of its coefficients. Finally, we discuss two theoretical applications in which having a rational polyhedral outer-approximation is crucial, and run some experiments which explore the benefits of the formulations proposed in this paper from a computational perspective.

The Golomb ruler problem is defined as follows: Given a positive integer n, locate n marks on a ruler such that the distance between any two distinct pair of marks are different from each other and the total length of the ruler is minimized. The Golomb ruler problem has applications in information theory, astronomy and communications, and it can be seen as a challenge for combinatorial optimization algorithms. Although constructing high quality rulers is well-studied, proving optimality is a far more challenging task. In this paper, we provide a computational comparison of different optimization paradigms, each using a different model (linear integer, constraint programming and quadratic integer) to certify that a given Golomb ruler is optimal. We propose several enhancements to improve the computational performance of each method by exploring bound tightening, valid inequalities, cutting planes and branching strategies. We conclude that a certain quadratic integer programming model solved through a Benders decomposition and strengthened by two types of valid inequalities performs the best in terms of solution time for small-sized Golomb ruler problem instances. On the other hand, a constraint programming model improved by range reduction and a particular branching strategy could have more potential to solve larger size instances due to its promising parallelization features.

We study sets defined as the intersection of a rank-1 constraint with different choices of linear side constraints. We identify different conditions on the linear side constraints, under which the convex hull of the rank-1 set is polyhedral or second-order cone representable. In all these cases, we also show that a linear objective can be optimized in polynomial time over these sets. Towards the application side, we show how these sets relate to commonly occurring substructures of a general quadratically constrained quadratic program. To further illustrate the benefit of studying quadratically constrained quadratic programs from a rank-1 perspective, we propose new rank-1 formulations for the generalized pooling problem and use our convexification results to obtain several new convex relaxations for the pooling problem. Finally, we run a comprehensive set of computational experiments and show that our convexification results together with discretization significantly help in improving dual bounds for the generalized pooling problem.

In this paper, we show that the subadditive dual of a feasible conic mixed-integer program (MIP) is a strong dual whenever it is feasible. Moreover, we show that this dual feasibility condition is equivalent to feasibility of the conic dual of the continuous relaxation of the conic MIP. In addition, we prove that all known conditions and other 'natural' conditions for strong duality, such as strict mixed-integer feasibility, boundedness of the feasible set or essentially strict feasibility imply that the subadditive dual is feasible. As an intermediate result, we extend the so-called 'finiteness property' from full-dimensional convex sets to intersections of full-dimensional convex sets and Dirichlet convex sets.

In this paper, we consider the basic problem of portfolio construction in financial engineering, and analyze how market-based and analytical approaches can be combined to obtain efficient portfolios. As a first step in our analysis, we model the asset returns as a random variable distributed according to a mixture of normal random variables. We then discuss how to construct portfolios that minimize the Conditional Value-at-Risk (CVaR) under this probabilistic model via a convex program. We also construct a second-order cone representable approximation of the CVaR under the mixture model, and demonstrate its theoretical and empirical accuracy. Furthermore, we incorporate the market equilibrium information into this procedure through the well-known Black-Litterman approach via an inverse optimization framework by utilizing the proposed approximation. Our computational experiments on a real dataset show that this approach with an emphasis on the market equilibrium typically yields less risky portfolios than a purely market-based portfolio while producing similar returns on average.

Alternating current optimal power flow (AC OPF) is one of the most fundamental optimization problems in electrical power systems. It can be formulated as a semidefinite program (SDP) with rank constraints. Solving AC OPF, that is, obtaining near optimal primal solutions as well as high quality dual bounds for this non-convex program, presents a major computational challenge to today's power industry for the real-time operation of large-scale power grids. In this paper, we propose a new technique for reformulation of the rank constraints using both principal and non-principal 2-by-2 minors of the involved Hermitian matrix variable and characterize all such minors into three types. We show the equivalence of these minor constraints to the physical constraints of voltage angle differences summing to zero over three- and four-cycles in the power network. We study second-order conic programming (SOCP) relaxations of this minor reformulation and propose strong cutting planes, convex envelopes, and bound tightening techniques to strengthen the resulting SOCP relaxations. We then propose an SOCP-based spatial branch-and-cut method to obtain the global optimum of AC OPF. Extensive computational experiments show that the proposed algorithm significantly outperforms the state-of-the-art SDP-based OPF solver and on a simple personal computer is able to obtain on average a 0.71% optimality gap in no more than 720 seconds for the most challenging power system instances in the literature.

As the modern transmission control and relay technologies evolve, transmission line switching has become an important option in power system operators' toolkits to reduce operational cost and improve system reliability. Most recent research has relied on the DC approximation of the power flow model in the optimal transmission switching problem. However, it is known that DC approximation may lead to inaccurate flow solutions and also overlook stability issues. In this paper, we focus on the optimal transmission switching problem with the full AC power flow model, abbreviated as AC OTS. We propose a new exact formulation for AC OTS and its mixed-integer second-order conic programming (MISOCP) relaxation. We improve this relaxation via several types of strong valid inequalities inspired by the recent development for the closely related AC Optimal Power Flow (AC OPF) problem. We also propose a practical algorithm to obtain high quality feasible solutions for the AC OTS problem. Extensive computational experiments show that the proposed formulation and algorithms efficiently solve IEEE standard and congested instances and lead to significant cost benefits with provably tight bounds.

This paper proposes three strong second order cone programming (SOCP) relaxations for the AC optimal power flow (OPF) problem. These three relaxations are incomparable to each other and two of them are incomparable to the standard SDP relaxation of OPF. Extensive computational experiments show that these relaxations have numerous advantages over existing convex relaxations in the literature: (i) their solution quality is extremely close to that of the SDP relaxations (the best one is within 99.96% of the SDP relaxation on average for all the IEEE test cases) and consistently outperforms previously proposed convex quadratic relaxations of the OPF problem, (ii) the solutions from the strong SOCP relaxations can be directly used as a warm start in a local solver such as IPOPT to obtain a high quality feasible OPF solution, and (iii) in terms of computation times, the strong SOCP relaxations can be solved an order of magnitude faster than standard SDP relaxations. For example, one of the proposed SOCP relaxations together with IPOPT produces a feasible solution for the largest instance in the IEEE test cases (the 3375-bus system) and also certifies that this solution is within 0.13% of global optimality, all this computed within 157.20 seconds on a modest personal computer. Overall, the proposed strong SOCP relaxations provide a practical approach to obtain feasible OPF solutions with extremely good quality within a time framework that is compatible with the real-time operation in the current industry practice.

It is well-known that optimizing network topology by switching on and off transmission lines improves the efficiency of power delivery in electrical networks. In fact, the USA Energy Policy Act of 2005 (Section 1223) states that the U.S. should "encourage, as appropriate, the deployment of advanced transmission technologies" including "optimized transmission line configurations". As such, many authors have studied the problem of determining an optimal set of transmission lines to switch off to minimize the cost of meeting a given power demand under the direct current (DC) model of power flow. This problem is known in the literature as the Direct-Current Optimal Transmission Switching Problem (DC-OTS). Most research on DC-OTS has focused on heuristic algorithms for generating quality solutions or on the application of DC-OTS to crucial operational and strategic problems such as contingency correction, real-time dispatch, and transmission expansion. The mathematical theory of the DC-OTS problem is less well-developed. In this work, we formally establish that DC-OTS is NP-Hard, even if the power network is a series-parallel graph with at most one load/demand pair. Inspired by Kirchoff's Voltage Law, we give a cycle-based formulation for DC-OTS, and we use the new formulation to build a cycle-induced relaxation. We characterize the convex hull of the cycle-induced relaxation, and the characterization provides strong valid inequalities that can be used in a cutting-plane approach to solve the DC-OTS. We give details of a practical implementation, and we show promising computational results on standard benchmark instances.

It has been recently proven that the semidefinite programming (SDP) relaxation of the optimal power flow problem over radial networks is exact under technical conditions such as not including generation lower bounds or allowing load over-satisfaction. In this paper, we investigate the situation where generation lower bounds are present. We show that even for a two-bus one-generator system, the SDP relaxation can have all possible approximation outcomes, that is (1) SDP relaxation may be exact or (2) SDP relaxation may be inexact or (3) SDP relaxation may be feasible while the OPF instance may be infeasible. We provide a complete characterization of when these three approximation outcomes occur and an analytical expression of the resulting optimality gap for this two-bus system. In order to facilitate further research, we design a library of instances over radial networks in which the SDP relaxation has positive optimality gap. Finally, we propose valid inequalities and variable bound tightening techniques that significantly improve the computational performance of a global optimization solver. Our work demonstrates the need of developing efficient global optimization methods for the solution of OPF even in the simple but fundamental case of radial networks.