An arc-search interior-point method is a type of interior-point method that approximates the central path by an ellipsoidal arc, and it can often reduce the number of iterations. In this work, to further reduce the number of iterations and the computation time for solving linear programming problems, we propose two arc-search interior-point methods using Nesterov’s … Read more
We study a mixed-integer set \(\mathcal{S}:=\{(x,t) \in \{0,1\}^n \times \mathbb{R}: f(x) \ge t\}\) arising in the submodular maximization problem, where \(f\) is a submodular function defined over \(\{0,1\}^n\). We use intersection cuts to tighten a polyhedral outer approximation of \(\mathcal{S}\). We construct a continuous extension \(\mathsf{F}\) of \(f\), which is convex and defined over the … Read more
Quadratic programs with box constraints involve minimizing a possibly nonconvex quadratic function subject to lower and upper bounds on each variable. This is a well-known NP-hard problem that frequently arises in various applications. We focus on two convex relaxations, namely the RLT (Reformulation-Linearization Technique) relaxation and the SDP-RLT relaxation obtained by adding semidefinite constraints to … Read more
Globally optimizing a nonconvex quadratic over the intersection of $m$ balls in $\mathbb{R}^n$ is known to be polynomial-time solvable for fixed $m$. Moreover, when $m=1$, the standard semidefinite relaxation is exact. When $m=2$, it has been shown recently that an exact relaxation can be constructed using a disjunctive semidefinite formulation based essentially on two copies … Read more
In this study, we investigate the connection between the efficient frontier (EF) of a general multiobjective mixed integer linear optimization problem (MILP) and the so-called restricted value function (RVF) of a closely related single-objective MILP. In the first part of the paper, we detail the mathematical structure of the RVF, including characterizing the set of … Read more
We investigate some graph parameters dealing with biindependent pairs $(A,B)$ in a bipartite graph $G=(V_1\cup V_2,E)$, i.e., pairs $(A,B)$ where $A\subseteq V_1$, $B\subseteq V_2$ and $A\cup B$ is independent. These parameters also allow to study bicliques in general graphs. When maximizing the cardinality $|A\cup B|$ one finds the stability number $\alpha(G)$, well-known to be polynomial-time … Read more
We use sensitivity analysis to design optimality-based discretization (cutting-plane) methods for the global optimization of nonconvex semi-infinite programs (SIPs). We begin by formulating the optimal discretization of SIPs as a max-min problem and propose variants that are more computationally tractable. We then use parametric sensitivity theory to design an efficient method for solving these max-min … Read more
We study a system in which a common delivery fleet provides service to both same-day delivery (SDD) and next-day delivery (NDD) orders placed by e-retail customers who are sensitive to delivery prices. We develop a model of the system and optimize with respect to two separate objectives. First, empirical research suggests that fulfilling e-retail orders … Read more