DR-submodular functions encompass a broad class of functions which are generally non-convex and non-concave. We study the problem of minimizing any DR-submodular function, with continuous and general integer variables, under box constraints and possibly additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide … Read more
We investigate some optimization models for meal delivery that stem from a collaboration with an Italian company mainly operating in Rome. The focus of this company is on top-end customers, and the company pursues high Quality of Service through a careful management of delays. We then design optimization models and algorithms for dispatching orders to … Read more
We consider two-stage robust linear programs with uncertain righthand side. We develop a General Polyhedral Approximation (GPA), in which the uncertainty set $\mathcal{U}$ is substituted by a finite set of polytopes derived from the vertex set of an arbitrary polytope that dominates $\mathcal{U}$. The union of the polytopes need not contain $\mathcal{U}$. We analyse and … Read more
In this paper we study the Consistent Traveling Salesman Problem with positional consistency constraints (CTSP), where we seek to generate a set of routes with minimum cost, in which all the clients that are visited in several routes require total positional consistency, that is, they need to appear in the same relative position in all … Read more
Motivated by recent progress on online linear programming (OLP), we study the online decision making problem (ODMP) as a natural generalization of OLP. In ODMP, there exists a single decision maker who makes a series of decisions spread out over a total of \(T\) time stages. At each time stage, the decision maker makes a … Read more
DP is a complexity class that is the class of all languages that are the intersection of a language in NP and a language in co-NP, as coined by Papadimitriou and Yannakakis. In this paper, we will establish that, recognizing a facet for the knapsack polytope is DP-complete, as conjectured by Hartvigsen and Zemel in … Read more
In this paper, the symbol detection mean squared error (MSE) constrained hybrid analog and digital beamforming is proposed in millimeter wave (mmWave) system, and the reconfigurable intelligent surface (RIS) is proposed to assist the mmWave system. The inner majorization-minimization (iMM) method is proposed to obtain analog transmitter, RIS and analog receivers, and the alternating direction … Read more
We consider a class of Riemannian optimization problems where the objective is the sum of a smooth function and a nonsmooth function, considered in the ambient space. This class of problems finds important applications in machine learning and statistics such as the sparse principal component analysis, sparse spectral clustering, and orthogonal dictionary learning. We propose … Read more
We consider the projected gradient algorithm for the nonconvex best subset selection problem that minimizes a given empirical loss function under an \(\ell_0\)-norm constraint. Through decomposing the feasible set of the given sparsity constraint as a finite union of linear subspaces, we present two acceleration schemes with global convergence guarantees, one by same-space extrapolation and … Read more
Adjustable Robust Optimization (ARO) is a paradigm for facing uncertainty in a decision problem, in case some recourse actions are allowed after the actual value of all input parameters is revealed. While several approaches have been introduced for the linear case, little is known regarding exact methods for the convex case. In this work, we … Read more