The planning of chemical production often involves the optimization of the size of the tasks to be performed subject to unit capacity constraints, as well as inventory constraints for intermediate materials. While several mixed-integer programming (MIP) models have been proposed that account for these features, the development of tightening methods for these formulations has received … Read more
Binary programs with a quadratic objective function are NP-hard in general, even if the linear optimization problem over the same feasible set is tractable. In this paper, we address such problems by computing quadratic global underestimators of the objective function that are separable but not necessarily convex. Exploiting the binary constraint on the variables, a … Read more
The principal idea of this paper is to exploit Semidefinite Programming (SDP) relaxation within the framework provided by Mixed Integer Nonlinear Programming (MINLP) solvers when tackling Binary Quadratic Problems (BQP). SDP relaxation is well-known to provide strong bounds for BQP in practice. However, the method is not typically implemented in many state-of-the-art MINLP solvers based … Read more
When derivatives of a nonlinear objective function are unavailable, many derivative- free optimization algorithms rely on interpolation-based models of the function. But what if the function values are contaminated by noise, as in most of the simulation- based problems typically encountered in this area? We propose to obtain linear and quadratic models by using knowledge … Read more
We examine the problem of placing stationary monitors in a continuous space, with the goal of minimizing an adversary’s maximum probability of traversing an origin-destination route without being detected. The problem arises, for instance, in defending against the transport of illicit material through some area of interest. In particular, we consider the deployment of monitors … Read more
One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformulation of the problem of interest and solving the resulting problem by a fast First Order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when … Read more
We give an algorithm for testing the extremality of a large class of minimal valid functions for the two-dimensional infinite group problem. ArticleDownload View PDF
An automatic method for constructing linear relaxations of constrained global optimization problems is proposed. Such a construction is based on affine and interval arithmetics and uses operator overloading. These linear programs have exactly the same numbers of variables and of inequality constraints as the given problems. Each equality constraint is replaced by two inequalities. This … Read more
For a quadratic optimization problem (QOP) with linear equality constraints in continuous nonnegative variables and binary variables, we propose three relaxations in simplified forms with a parameter $\lambda$: Lagrangian, completely positive, and copositive relaxations. These relaxations are obtained by reducing the QOP to an equivalent QOP with a single quadratic equality constraint in nonnegative variables, … Read more
The expected utility knapsack problem is to pick a set of items whose values are described by random variables so as to maximize the expected utility of the total value of the items picked while satisfying a constraint on the total weight of items picked. We consider the following solution approach for this problem: (i) … Read more