We study the Knapsack Problem with Conflict Graph (KPCG), a generalization of the Knapsack Problem in which a conflict graph specifies pairs of items (vertices of the graph) which cannot be simultaneously selected in a solution. The KPCG asks for determining a maximum-profit subset of items of total weight no larger than the knapsack capacity … Read more
This work considers nonsmooth and nonconvex optimization problems whose objective and constraint functions are defined by difference-of-convex (DC) functions. We consider an infeasible bundle method based on the so-called improvement functions to compute critical points for problems of this class. Our algorithm neither employs penalization techniques nor solves subproblems with linearized constraints. The approach, which … Read more
JuMP is an open-source algebraic modeling language in the Julia language. In this work, we discuss a complete re-write of JuMP based on a novel abstract data structure, which we call \textit{MathOptInterface}, for representing instances of mathematical optimization problems. MathOptInterface is significantly more general than existing data structures in the literature, encompassing, for example, a … Read more
The scheduling of drilling and hydraulic fracturing of wells in an unconventional oil field plays an important role in the profitability of the field. A key challenge arising in this problem is the requirement that neither drilling nor oil production can be done at wells within a specified neighborhood of a well being fractured. We … Read more
Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems well-known to be NP-hard in general. In this paper we study sufficient conditions for a convex hull result that immediately implies that the standard semidefinite program (SDP) relaxation of a QCQP is tight. We begin by outlining a general framework for proving such … Read more
A hybrid projection-proximal point algorithm is proposed for variational inequality problems. Though the usual proximal point method and its variants require that the mapping involved be monotone, at least pseudomonotone, we assume only that the so-called Minty variational inequality has a solution, in order to ensure the global convergence. This assumption is less stringent than … Read more
In the growing field of autonomous driving, traffic-light controlled intersections as the nodes of large traffic networks are of special interest. We want to analyze how much an optimized coordination of vehicles and infrastructure can contribute to a more efficient transit through these bottlenecks. In addition, we are interested in sensitivity of the results with … Read more
We present a sequential convexification procedure to derive, in the limit, a set arbitrary close to the convex hull of $\epsilon$-feasible solutions to a general nonconvex continuous bilinear set. Recognizing that bilinear terms can be represented with a finite number nonlinear nonconvex constraints in the lifted matrix space, our procedure performs a sequential convexification with … Read more
We decompose the copositive cone $\copos{n}$ into a disjoint union of a finite number of open subsets $S_{\cal E}$ of algebraic sets $Z_{\cal E}$. Each set $S_{\cal E}$ consists of interiors of faces of $\copos{n}$. On each irreducible component of $Z_{\cal E}$ these faces generically have the same dimension. Each algebraic set $Z_{\cal E}$ is … Read more
For general large-scale optimization problems compact representations exist in which recursive quasi-Newton update formulas are represented as compact matrix factorizations. For problems in which the objective function contains additional structure, so-called structured quasi-Newton methods exploit available second-derivative information and approximate unavailable second derivatives. This article develops the compact representations of two structured Broyden-Fletcher-Goldfarb-Shanno update formulas. … Read more