Convex approximations for complete integer recourse models

We consider convex approximations of the expected value function of a two-stage integer recourse problem. The convex approximations are obtained by perturbing the distribution of the random right-hand side vector. It is shown that the approximation is optimal for the class of problems with totally unimodular recourse matrices. For problems not in this class, the result is a convex lower bound that is strictly better than the one obtained from the LP relaxation.This research has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences.Key words.integer recourse – convex approximationMathematics Subject Classification (1991):90C15, 90C11     

Parametric error bounds for convex approximations of two-stage mixed-integer recourse models with a random second-stage cost vector

We consider two-stage recourse models with integer restrictions in the second stage. These models are typically non-convex and hence, hard to solve. There exist convex approximations of these models with accompanying error bounds. However, it is unclear how these error bounds depend on the distributions of the second-stage cost vector q. In this paper, we derive parametric error bounds whose dependence on the distribution of q is explicit: they scale linearly in the expected value of the ${?}_1$-norm of q.     

A loose Benders decomposition algorithm for approximating two-stage mixed-integer recourse models

We propose a new class of convex approximations for two-stage mixed-integer recourse models, the so-called generalized alpha-approximations. The advantage of these convex approximations over existing ones is that they are more suitable for efficient computations. Indeed, we construct a loose Benders decomposition algorithm that solves large problem instances in reasonable time. To guarantee the performance of the resulting solution, we derive corresponding error bounds that depend on the total variations of the probability density functions of the random variables in the model. The error bounds converge to zero if these total variations converge to zero. We empirically assess our solution method on several test instances, including the SIZES and SSLP instances from SIPLIB. We show that our method finds near-optimal solutions if the variability of the random parameters in the model is large. Moreover, our method outperforms existing methods in terms of computation time, especially for large problem instances.

     

Statistical approximations for recourse constrained stochastic programs

The two stage stochastic program with recourse is known to have numerous applications in financial planning, energy modeling, telecommunications systems etc. Notwithstanding its applicability, the two stage stochastic program is limited in its ability to incorporate a decision maker's attitudes towards risk. In this paper we present an extension via the inclusion of a recourse constraint. This results in a convex integrated chance constraint (ICC), which inherits the convexity properties of two stage programs. However, it also inherits some of the difficulties associated with the evaluation of recourse functions. This motivates our study of conditions that may be applicable to algorithms using statistical approximations of such ICC. We present a set of sufficient conditions that these approximations may satisfy in order to assure convergence. Our conditions are satisfied by a wide range of statistical approximations, and we demonstrate that these approximations can be generated within standard algorithmic procedures.This work was supported in part by Grant No. NSF-DDM-9114352 from the National Science Foundation.     

Quantitative stability of fully random two-stage stochastic programs with mixed-integer recourse

Optimization Letters - The quantitative stability and empirical approximation of two-stage stochastic programs with mixed-integer recourse are investigated. We first study the boundedness of...     

Branch-and-price for a class of nonconvex mixed-integer nonlinear programs

This work attempts to combine the strengths of two major technologies that have matured over the last three decades: global mixed-integer nonlinear optimization and branch-and-price. We consider a class of generally nonconvex mixed-integer nonlinear programs (MINLPs) with linear complicating constraints and integer linking variables. If the complicating constraints are removed, the problem becomes easy to solve, e.g. due to decomposable structure. Integrality of the linking variables allows us to apply a discretization approach to derive a Dantzig-Wolfe reformulation and solve the problem to global optimality using branch-andprice. It is a remarkably simple idea; but to our surprise, it has barely found any application in the literature. In this work, we show that many relevant problems directly fall or can be reformulated into this class of MINLPs. We present the branch-and-price algorithm and demonstrate its effectiveness (and sometimes ineffectiveness) in an extensive computational study considering multiple large-scale problems of practical relevance, showing that, in many cases, orders-of-magnitude reductions in solution time can be achieved.

     

Convex quadratic relaxations for mixed-integer nonlinear programs in power systems

This paper presents a set of new convex quadratic relaxations for nonlinear and mixed-integer nonlinear programs arising in power systems. The considered models are motivated by hybrid discrete/continuous applications where existing approximations do not provide optimality guarantees. The new relaxations offer computational efficiency along with minimal optimality gaps, providing an interesting alternative to state-of-the-art semidefinite programming relaxations. Three case studies in optimal power flow, optimal transmission switching and capacitor placement demonstrate the benefits of the new relaxations.     

Continuity and stability of fully random two-stage stochastic programs with mixed-integer recourse

In order to derive continuity and stability of two-stage stochastic programs with mixed-integer recourse when all coefficients in the second-stage problem are random, we first investigate the quantitative continuity of the objective function of the corresponding continuous recourse problem with random recourse matrices. Then by extending derived results to the mixed-integer recourse case, the perturbation estimate and the piece-wise lower semi-continuity of the objective function are proved. Under the framework of weak convergence for probability measure, the epi-continuity and joint continuity of the objective function are established. All these results help us to prove a qualitative stability result. The obtained results extend current results to the mixed-integer recourse with random recourse matrices which have finitely many atoms.     

An outer-approximation algorithm for a class of mixed-integer nonlinear programs

An outer-approximation algorithm is presented for solving mixed-integer nonlinear programming problems of a particular class. Linearity of the integer (or discrete) variables, and convexity of the nonlinear functions involving continuous variables are the main features in the underlying mathematical structure. Based on principles of decomposition, outer-approximation and relaxation, the proposed algorithm effectively exploits the structure of the problems, and consists of solving an alternating finite sequence of nonlinear programming subproblems and relaxed versions of a mixed-integer linear master program. Convergence and optimality properties of the algorithm are presented, as well as a general discussion on its implementation. Numerical results are reported for several example problems to illustrate the potential of the proposed algorithm for programs in the class addressed in this paper. Finally, a theoretical comparison with generalized Benders decomposition is presented on the lower bounds predicted by the relaxed master programs.     

A note on second-order stochastic dominance constraints induced by mixed-integer linear recourse

We introduce stochastic integer programs with second-order dominance constraints induced by mixed-integer linear recourse. Closedness of the constraint set mapping with respect to perturbations of the underlying probability measure is derived. For discrete probability measures, large-scale, block-structured, mixed- integer linear programming equivalents to the dominance constrained stochastic programs are identified. For these models, a decomposition algorithm is proposed and tested with instances from power optimization.     

Continuity of parametric mixed-integer quadratic programs and its application to stability analysis of two-stage quadratic stochastic programs with mixed-integer recourse

For mixed-integer quadratic program where all coefficients in the objective function and the right-hand sides of constraints vary simultaneously, we show locally Lipschitz continuity of its optimal value function, and derive the corresponding global estimation; furthermore, we also obtain quantitative estimation about the change of its optimal solutions. Applying these results to two-stage quadratic stochastic program with mixed-integer recourse, we establish quantitative stability of the optimal value function and the optimal solution set with respect to the Fortet-Mourier probability metric, when the underlying probability distribution is perturbed. The obtained results generalize available results on continuity properties of mixed-integer quadratic programs and extend current results on quantitative stability of two-stage quadratic stochastic programs with mixed-integer recourse.     

On multiple simple recourse models

We consider multiple simple recourse (MSR) models, both continuous and integer versions, which generalize the corresponding simple recourse (SR) models by allowing for a refined penalty cost structure for individual shortages and surpluses. It will be shown that (convex approximations of) such MSR models can be represented as explicitly specified continuous SR models, and thus can be solved efficiently by existing algorithms. This research has been made possible by a fellowship of the Royal Netherlands Academy of Arts and Sciences.     

Supernode processing of mixed-integer models

This paper discusses processing software for large scale mixed-integer optimization models. The software is part of the Mathematical OPtimization System MOPS [18] which contains algorithms for solving large-scale LP and mixed-integer programs. The processing techniques are implemented in such a way that they can be applied not only initially but also during the branch-and-bound algorithm.This paper discusses only a subset of the processing techniques included in MOPS. Algorithmic and software design aspects of the branch-and-bound process are not part of this paper.Dedicated to Professor George B. Dantzig on the occasion of his eightieth birthday.     

Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems

Numerous planning problems can be formulated as multi-stage stochastic programs and many possess key discrete (integer) decision variables in one or more of the stages. Progressive hedging (PH) is a scenario-based decomposition technique that can be leveraged to solve such problems. Originally devised for problems possessing only continuous variables, PH has been successfully applied as a heuristic to solve multi-stage stochastic programs with integer variables. However, a variety of critical issues arise in practice when implementing PH for the discrete case, especially in the context of very difficult or large-scale mixed-integer problems. Failure to address these issues properly results in either non-convergence of the heuristic or unacceptably long run-times. We investigate these issues and describe algorithmic innovations in the context of a broad class of scenario-based resource allocation problem in which decision variables represent resources available at a cost and constraints enforce the need for sufficient combinations of resources. The necessity and efficacy of our techniques is empirically assessed on a two-stage stochastic network flow problem with integer variables in both stages.     

Diffusive approximations for a class of nonlinear parabolic equations

We study a class of discrete velocity type approximations to nonlinear parabolic equations with source. After proving existence results and estimates on the solution to the relaxation system, we pass into the limit towards a weak solution, which is the unique entropy solution if the coefficients of the parabolic equation are constant.     

Product approximations for a class of quantum anharmonic oscillators

In this article, we investigate analytically and numerically a class of non-autonomous Schrödinger equations in one space dimension describing the dynamics of quantum anharmonic oscillators driven by time-dependent quartic interactions. We do so within a suitably constructed Faedo–Galerkin scheme by analyzing several product approximations for their solutions, which involve various exponential operator splittings. Our main objective is to study the convergence rates and the accuracy of such approximations, among which there are extensions of the Trotter–Kato product formula and several other variants. Crucial to our analysis is the knowledge of the lowest energy level and of the corresponding eigensolution to the associated time-independent problem, which we also compute within the very same framework.     

Higher-order total variation bounds for expectations of periodic functions and simple integer recourse approximations

We derive bounds on the expectation of a class of periodic functions using the total variations of higher-order derivatives of the underlying probability density function. These bounds are a strict improvement over those of Romeijnders et al. (Math Program 157:3–46, 2016b), and we use them to derive error bounds for convex approximations of simple integer recourse models. In fact, we obtain a hierarchy of error bounds that become tighter if the total variations of additional higher-order derivatives are taken into account. Moreover, each error bound decreases if these total variations become smaller. The improved bounds may be used to derive tighter error bounds for convex approximations of more general recourse models involving integer decision variables.