A common way to produce a convex relaxation of a Mixed Integer Quadratically Constrained Program (MIQCP) is to lift the problem into a higher dimensional space by introducing variables $Y_{ij}$ to represent each of the products $x_i x_j$ of variables appearing in a quadratic form. One advantage of such extended relaxations is that they can … Read more
Approximate proximal point algorithms (abbreviated as APPAs) are classical approaches for convex optimization problems and monotone variational inequalities. To solve the subproblems of these algorithms, the projection method takes the iteration in form of $u^{k+1} = P_{\Omega}[u^k-\alpha_k d^k]$. Interestingly, many of them can be paired such that $%\exists \tilde{u}^k, \tilde{u}^k = P_{\Omega}[u^k – \beta_kF(v^k)] = … Read more
We study minimizing the sum of weighted completion times in a concurrent open shop. We give a primal-dual 2-approximation algorithm for this problem. We also show that several natural linear programming relaxations for this problem have an integrality gap of 2. Finally, we show that this problem is inapproximable within a factor strictly less than … Read more
Assigning products to and retrieving them from proper storage locations in a unit-load warehouse are crucial in minimizing its operating cost. The problem becomes intractable when the warehouse faces uncertain demand in a dynamic setting. We assume a factor-based demand model in which demand for each product in each period is affinely dependent on some … Read more
This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim., 16(4):1110–1136, 2006). We introduce a kernel function in the algorithm. For $p\in[0,1)$, the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, … Read more
The Fibonacci index of a graph is the number of its stable sets. This parameter is widely studied and has applications in chemical graph theory. In this paper, we establish tight upper bounds for the Fibonacci index in terms of the stability number and the order of general graphs and connected graphs. Turan graphs frequently … Read more
We provide a proof point for the idea that matrix-based algorithms for discrete optimization problems, mainly conceived for proving theoretical efficiency, can be easily and efficiently implemented on massively-parallel architectures by exploiting scalable and efficient parallel implementations of algorithms for ultra high-precision dense linear algebra. We have successfully implemented our algorithm on the Blue Gene/L … Read more
Abstract: We present new valid inequalities for 0-1 programming problems that work in similar ways to well known cover inequalities. Discussion and analysis of these cuts is followed by their revision and use in integer programming as a new generation of cuts that excludes not only portions of polyhedra containing noninteger points, also parts with … Read more
This paper describes the first phase of a project attempting to construct an efficient general-purpose nonlinear optimizer using an augmented Lagrangian outer loop with a relative error criterion, and an inner loop employing a state-of-the art conjugate gradient solver. The outer loop can also employ double regularized proximal kernels, a fairly recent theoretical development that … Read more
In this paper we study linear optimization problems with multi-dimensional linear positive second-order stochastic dominance constraints. By using the polyhedral properties of the second- order linear dominance condition we present a cutting-surface algorithm, and show its finite convergence. The cut generation problem is a difference of convex functions (DC) optimization problem. We exploit the polyhedral … Read more