Using a metaprogramming technique and semialgebraic computations, we provide computer-based proofs for old and new cutting-plane theorems in Gomory–Johnson’s model of cut generating functions. Citationto be presented at ISCO 2016ArticleDownload View PDF
Mixed-integer semidefinite programs arise in many applications and several problem-specific solution approaches have been studied recently. In this paper, we investigate a generic branch-and-bound framework for solving such problems. We first show that strict duality of the semidefinite relaxations is inherited to the subproblems. Then solver components like dual fixing, branching rules, and primal heuristics … Read more
This work discusses the following general packing problem-class: given a finite collection of d-dimensional spheres with arbitrarily chosen radii, find the smallest sphere in R^d that contains the entire collection of these spheres in a non-overlapping arrangement. Generally speaking, analytical solution approaches cannot be expected to apply to this general problem-type, except for very small … Read more
Purpose: The development of iterative image reconstruction algorithms for cone-beam computed tomography (CBCT) remains an active and important research area. Even with hardware acceleration, the overwhelming majority of the available 3D iterative algorithms that implement nonsmooth regularizers remain computationally burdensome and have not been translated for routine use in time-sensitive applications such as image-guided radiation … Read more
The search for a better understanding of complex systems calls for quantitative model development. Within this development process, model fitting to observational data (calibration) often plays an important role. Traditionally, local optimization techniques have been applied to solve nonlinear (as well as linear) model calibration problems numerically: the limitations of such approaches in the nonlinear … Read more
The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic … Read more
This paper focuses on coordinate update methods, which are useful for solving problems involving large or high-dimensional datasets. They decompose a problem into simple subproblems, where each updates one, or a small block of, variables while fixing others. These methods can deal with linear and nonlinear mappings, smooth and nonsmooth functions, as well as convex … Read more
In this work, we present model development and numerical solution approaches to the general problem of packing a collection of ellipses into an optimized regular polygon. Our modeling and solution strategy is based on the concept of embedded Lagrange multipliers. This concept is applicable to a wide range of optimization problems in which explicit analytical … Read more
In this paper, we introduce an $O(nm)$ time algorithm to determine the minimum length directed cycle in a directed network with $n$ nodes and $m$ arcs and with no negative length directed cycles. This result improves upon the previous best time bound of $O(nm + n^2 \log\log n)$. Our algorithm first determines the cycle with … Read more
Multistage stochastic optimization leads to NLPs over scenario trees that become extremely large when many time stages or fine discretizations of the probability space are required. Interior-point methods are well suited for these problems if the arising huge, structured KKT systems can be solved efficiently, for instance, with a large scenario tree but a moderate … Read more