Representability results for mixed-integer linear systems play a fundamental role in optimization since they give geometric characterizations of the feasible sets that can be formulated by mixed-integer linear programming. We consider a natural extension of mixed-integer linear systems obtained by adding just one ellipsoidal inequality. The set of points that can be described, possibly using … Read more
In this paper, we consider the Multilinear set defined as the set of binary points satisfying a collection of multilinear equations. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is … Read more
Concave Mixed-Integer Quadratic Programming is the problem of minimizing a concave quadratic polynomial over the mixed-integer points in a polyhedral region. In this work we describe an algorithm that finds an ε-approximate solution to a Concave Mixed-Integer Quadratic Programming problem. The running time of the proposed algorithm is polynomial in the size of the problem … Read more
One of the major issues in stochastic gradient descent (SGD) methods is how to choose an appropriate step size while running the algorithm. Since the traditional line search technique does not apply for stochastic optimization algorithms, the common practice in SGD is either to use a diminishing step size, or to tune a fixed step … Read more
In a Standard Quadratic Optimization Problem (StQP), a possibly indefinite quadratic form (the simplest nonlinear function) is extremized over the standard simplex, the simplest polytope. Despite this simplicity, the nonconvex instances of this problem class allow for remarkably rich patterns of coexisting local solutions, which are closely related to practical difficulties in solving StQPs globally. … Read more
In the context of global optimization and mixed-integer non-linear programming, generalizing a technique of D’Ambrosio, Fampa, Lee and Vigerske for handling the square-root function, we develop a virtuous smoothing method, using cubics, aimed at functions having some limited non-smoothness. Our results pertain to root functions ($w^p$ with $0
We propose to solve global optimal control problems with a new algorithm that is based on Bock’s direct multiple shooting method. We provide conditions and numerical evidence for a significant overall runtime reduction compared to the standard single shooting approach. CitationOptimal Control Applications and Methods, Vol. 39 (2), pp. 449–470, 2017 DOI 10.1002/oca.2324 Article online … Read more
This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An … Read more
This chapter examines the problem of packing tetris-like items, orthogonally, with the possibility of rotations, into a convex domain, in the presence of additional conditions. An MILP (Mixed Integer Linear Programming) and an MINLP (Mixed Integer Nonlinear Programming) models, previously studied by the author, are surveyed. An efficient formulation of the objective function, aimed at … 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