In this paper, we consider a fundamental problem in modern digital communications known as multi-input multi-output (MIMO) detection, which can be formulated as a complex quadratic programming problem subject to unit-modulus and discrete argument constraints. Various semidefinite relaxation (SDR) based algorithms have been proposed to solve the problem in the literature. In this paper, we … Read more
There is an undeniable global shortage of skillful nurses. This is a problem of high priority, which is correlated to workforce management issues. These issues can be palliated by increasing nurses’ satisfaction based on flexible rosters using automated nurse rostering. This paper in concerned with nurse rostering based on constraint programming by satisfying global constraints, … Read more
We propose a global optimization algorithm for stochastic nonlinear programs that uses a specialized spatial branch and bound (BB) strategy to exploit the nearly decomposable structure of the problem. In particular, at each node in the BB scheme, a lower bound is constructed by relaxing the so-called non-anticipativity constraints and an upper bound is constructed … Read more
We derive a closed form description of the convex hull of mixed-integer bilinear covering set with bounds on the integer variables. This convex hull description is determined by considering some orthogonal disjunctive sets defined in a certain way. This description does not introduce any new variables, but consists of exponentially many inequalities. An extended formulation … Read more
Given a non-convex optimization problem, we study conditions under which every Karush-Kuhn-Tucker (KKT) point is a global optimizer. This property is known as KT-invexity and allows to identify the subset of problems where an interior point method always converges to a global optimizer. In this work, we provide necessary conditions for KT-invexity in n-dimensions and … Read more
In this paper we study necessary optimality conditions for the optimization problem $$\textrm{infimum}f_0(x) \quad \textrm{ subject to } \quad x \in S,$$ where $f_0 \colon \mathbb{R}^n \rightarrow \mathbb{R}$ is a polynomial function and $S \subset \mathbb{R}^n$ is a set defined by polynomial inequalities. Assume that the problem is bounded below and has the Mangasarian–Fromovitz property … Read more
Cutting planes are derived from specific problem structures, such as a single linear constraint from an integer program. This paper introduces cuts that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set $S\cap P$, where $S$ is a closed set, … Read more
Convex hulls of monomials have been widely studied in the literature, and monomial convexifications are implemented in global optimization software for relaxing polynomials. However, there has been no study of the error in the global optimum from such approaches. We give bounds on the worst-case error for convexifying a monomial over subsets of $[0,1]^n$. This … Read more
We present a novel complex number formulation along with tight convex relaxations for the aircraft conflict resolution problem. Our approach combines both speed and heading control and provides global optimality guarantees despite non-convexities in the feasible region. As a side result, we present a new characterization of the conflict separation condition in the form of … Read more
We consider the problem of packing congruent circles with the maximum radius in a unit square. As a mathematical program, this problem is a notoriously difficult nonconvex quadratically constrained optimization problem which possesses a large number of local optima. We study several convexification techniques for the circle packing problem, including polyhedral and semi-definite relaxations and … Read more