Strong branching is an effective branching technique that can significantly reduce the size of the branch-and-bound tree for solving Mixed Integer Nonlinear Programming (MINLP) problems. The focus of this paper is to demonstrate how to effectively use discarded information from strong branching to strengthen relaxations of MINLP problems. Valid inequalities such as branching-based linearizations, various … Read more
We consider a class of infeasible, path-following methods for convex quadratric programming. Our methods are designed to be effective for solving both nondegerate and degenerate problems, where degeneracy is understood to mean the failure of strict complementarity at a solution. Global convergence and a polynomial bound on the number of iterations required is given. An … Read more
This paper presents some strong valid inequalities for the Maximum Common Induced Subgraph Problem (MCIS) and the proofs that the inequalities are facet-defining under certain conditions. The MCIS is an NP-hard problem and, therefore, no polynomial time algorithm is known to solve it. In this context, the study of its polytope can help in the … Read more
We present an approach to estimate adjoint sensitivities of economic metrics of relevance in the power grid with respect to physical weather variables using numerical weather prediction models. We demonstrate that this capability can significantly enhance planning and operations. We illustrate the method using a large-scale computational study where we compute sensitivities of the regional … Read more
Designing a network able to route a set of non-simultaneous demand vectors is an important problem arising in telecommunications. The problem can be seen a two-stage robust program where the recourse function consists in choosing the routing for each demand vector. Allowing the routing to change arbitrarily as the demand varies yields a very difficult … Read more
Large-sized extended formulations have the potential for providing high-quality bounds on some combinatorial optimization problems where the natural formulations perform poorly. This chapter discusses the use of some families of cuts that have been recently applied on extended formulations that are obtained by the discretization of the continuous variables occurring in the natural formulation of … Read more
We introduce and study the Split Common Null Point Problem (SCNPP) for set-valued maximal monotone mappings in Hilbert space. This problem generalizes our Split Variational Inequality Problem (SVIP) [Y. Censor, A. Gibali and S. Reich, Algorithms for the split variational inequality problem, Numerical Algorithms, accepted for publication, DOI 10.1007/s11075-011-9490-5]. The SCNPP with only two set-valued … Read more
The alternating direction method (ADM) is classical for solving a linearly constrained separable convex programming problem (primal problem), and it is well known that ADM is essentially the application of a concrete form of the proximal point algorithm (PPA) (more precisely, the Douglas-Rachford splitting method) to the corresponding dual problem. This paper shows that an … Read more
Farkas’ lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix inequalities. We provide nonlinear algebraic certificates for all infeasible linear matrix inequalities in the spirit of real algebraic geometry: A linear matrix inequality … Read more
Many derivative-free methods for constrained problems are not efficient for minimizing functions on “thin” domains. Other algorithms, like those based on Augmented Lagrangians, deal with thin constraints using penalty-like strategies. When the constraints are computationally inexpensive but highly nonlinear, these methods spend many potentially expensive objective function evaluations motivated by the difficulties of improving feasibility. … Read more