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 standard SDP relaxation (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 the standard SDP relaxation. 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.
While many classes of cutting-planes are at the disposal of integer programming solvers, our scientific understanding is far from complete with regards to cutting-plane selection, i.e., the task of ...selecting a portfolio of cutting-planes to be added to the LP relaxation at a given node of the branch-and-bound tree. In this paper we review the different classes of cutting-planes available, known theoretical results about their relative strength, important issues pertaining to cut selection, and discuss some possible new directions to be pursued in order to accomplish cutting-plane selection in a more principled manner. Finally, we review some lines of work that we undertook to provide a preliminary theoretical underpinning for some of the issues related to cut selection.
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 2-bus 1-generator system, the SDP relaxation can have all possible approximation outcomes, that is 1) SDP relaxation may be exact, 2) SDP relaxation may be inexact, or 3) SDP relaxation may be feasible while the optimal power flow (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 2-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.
Training a one-node neural network with the ReLU activation function via optimization, which we refer to as the ON-ReLU problem, is a fundamental problem in machine learning. In this paper, we begin ...by proving the NP-hardness of the ON-ReLU problem. We then present an approximation algorithm to solve the ON-ReLU problem, whose running time is <inline-formula><tex-math notation="LaTeX">\mathcal {O}(n^k)</tex-math></inline-formula> where <inline-formula><tex-math notation="LaTeX">n</tex-math></inline-formula> is the number of samples, and <inline-formula><tex-math notation="LaTeX">k</tex-math></inline-formula> is a predefined integral constant as an algorithm parameter. We analyze the performance of this algorithm under two regimes and show that: (1) given any arbitrary set of training samples, the algorithm guarantees an <inline-formula><tex-math notation="LaTeX">(n/k)</tex-math></inline-formula>-approximation for the ON-ReLU problem - to the best of our knowledge, this is the first time that an algorithm guarantees an approximation ratio for arbitrary data scenario; thus, in the ideal case (i.e., when the training error is zero) the approximation algorithm achieves the globally optimal solution for the ON-ReLU problem; and (2) given training sample with Gaussian noise, the same approximation algorithm achieves a much better asymptotic approximation ratio which is independent of the number of samples <inline-formula><tex-math notation="LaTeX">n</tex-math></inline-formula>. Extensive numerical studies show that our approximation algorithm can perform better than the gradient descent algorithm. Our numerical results also show that the solution of the approximation algorithm can provide a good initialization for gradient descent, which can significantly improve the performance.
Mixed-integer quadratic programming
is the problem of optimizing a quadratic function over points in a polyhedral set where some of the components are restricted to be integral. In this paper, we ...prove that the decision version of mixed-integer quadratic programming is in NP, thereby showing that it is NP-complete. This is established by showing that if the decision version of mixed-integer quadratic programming is feasible, then there exists a solution of polynomial size. This result generalizes and unifies classical results that quadratic programming is in NP (Vavasis in Inf Process Lett 36(2):73–77
17
) and integer linear programming is in NP (Borosh and Treybig in Proc Am Math Soc 55:299–304
1
, von zur Gathen and Sieveking in Proc Am Math Soc 72:155–158
18
, Kannan and Monma in Lecture Notes in Economics and Mathematical Systems, vol. 157, pp. 161–172. Springer
9
, Papadimitriou in J Assoc Comput Mach 28:765–768
15
).
This article tries to map the gender element in Bengali Vaiṣṇavism by focusing on the evolution of the image of Viṣnupriyā, Caitanya’s second wife, as it progressed from the pre-colonial hagiographic ...tradition to the novel theorization of Gaura–Viṣnupriyā dual worship in the colonial period. It explores the varied ways in which certain segments of educated Bengali intelligentsia actively involved in reassessing Vaiṣṇavism in colonial times disseminated the idea that Viṣnupriyā was not just a symbol of unwavering devotion, of resolute penance, and (after Caitanya’s death) of ideal widowhood, but also deserved to be worshiped by Bengalis along with Caitanya as a divine couple. The article contends that while the ways of biographic imaging of Viṣnupriyā reveals the fissures and frictions within the colonial Vaiṣṇava reform process, it also highlights various continuities with pre-colonial strands of Vaiṣṇava thought.
Improving the Integer L-Shaped Method Angulo, Gustavo; Ahmed, Shabbir; Dey, Santanu S
INFORMS journal on computing,
06/2016, Letnik:
28, Številka:
3
Journal Article
Recenzirano
Odprti dostop
We consider the integer L-shaped method for two-stage stochastic integer programs. To improve the performance of the algorithm, we present and combine two strategies. First, to avoid time-consuming ...exact evaluations of the second-stage cost function, we propose a simple modification that alternates between linear and mixed-integer subproblems. Next, to better approximate the shape of the second-stage cost function, we present a general framework to generate optimality cuts via a cut-generating linear program that considers information from all solutions found up to any given stage of the method. To address the impact of the proposed approaches, we report computational results on two classes of stochastic integer problems.
The
pq
-relaxation for the pooling problem can be constructed by applying McCormick envelopes for each of the bilinear terms appearing in the so-called
pq
-formulation of the pooling problem. This ...relaxation can be strengthened by using piecewise-linear functions that over- and under-estimate each bilinear term. Although there is a significant amount of empirical evidence to show that such piecewise-linear relaxations, which can be written as mixed-integer linear programs (MILPs), yield good bounds for the pooling problem, to the best of our knowledge, no formal result regarding the quality of these relaxations is known. In this paper, we prove that the ratio of the upper bound obtained by solving piecewise-linear relaxations (objective function is maximization) to the optimal objective function value of the pooling problem is at most
n
, where
n
is the number of output nodes. Furthermore for any
ϵ
> 0 and for any piecewise-linear relaxation, there exists an instance where the ratio of the relaxation value to the optimal value is at least
n
−
ϵ
. This analysis naturally yields a polynomial-time
n
-approximation algorithm for the pooling problem. We also show that if there exists a polynomial-time approximation algorithm for the pooling problem with guarantee better than
n
1−
ϵ
for any
ϵ
> 0, then NP-complete problems have randomized polynomial-time algorithms. Finally, motivated by the approximation algorithm, we design a heuristic that involves solving an MILP-based restriction of the pooling problem. This heuristic is guaranteed to provide solutions within a factor of
n
. On large-scale test instances and in significantly lesser time, this heuristic provides solutions that are often orders of magnitude better than those given by commercial local and global optimization solvers.
Full strong-branching (henceforth referred to as strong-branching) is a well-known variable selection rule that is known experimentally to produce significantly smaller branch-and-bound trees in ...comparison to all other known variable selection rules. In this paper, we attempt an analysis of the performance of the strong-branching rule both from a theoretical and a computational perspective. On the positive side for strong-branching, we identify vertex cover as a class of instances where this rule provably works well. In particular, for vertex cover we present: (1) an upper bound on the size of the branch-and-bound tree using strong-branching as a function of the additive integrality gap; (2) show how the Nemhauser-Trotter property of persistency, which can be used as a pre-solve technique for vertex cover, is being recursively and consistently used throughout the strong-branching tree; (3) and finally provide an example of a vertex cover instance where not using strong-branching leads to a tree that has at least exponentially more nodes than the branch-and-bound tree based on strong-branching. On the negative side for strong-branching, we identify another class of instances where the strong-branching tree is exponentially larger than another branch-and-bound tree for solving these instances. On the computational side, we conduct experiments on various types of instances, like the lot-sizing problem and its variants, packing integer programs (IP), covering IPs, chance constrained IPs, vertex cover, etc., to understand how much larger is the size of the strong-branching based branch-and-bound tree in comparison to the optimal branch-and-bound tree. The main take-away from these experiments (on small instances) is that for all these instances the size of the strong-branching tree is within a factor of two of the size of the optimal branch-and-bound tree.
PDF
