Mohit Tawarmalani

Haisheng Zhu, Taotao He, Mohit Tawarmalani

We present a novel relaxation framework for general mixed-integer nonlinear programming (MINLP) grounded in computational geometry. Our approach constructs polyhedral relaxations by convexifying finite sets of strategically chosen points, iteratively refining the approximation to converge toward the simultaneous convex hull of factorable function graphs. The framework is underpinned by three key contributions: (i) a new class of explicit inequalities for products of functions that strictly improve upon standard factorable and composite relaxation schemes; (ii) a proof establishing that the simultaneous convex hull of multilinear functions over axis-aligned regions is fully determined by their values at corner points, thereby generalizing existing results from hypercubes to arbitrary axis-aligned domains; and (iii) the integration of computational geometry tools, specifically voxelization and QuickHull, to efficiently approximate feasible regions and function graphs. We implement this framework and evaluate it on randomly generated polynomial optimization problems and a suite of 619 instances from \texttt{MINLPLib}. Numerical results demonstrate significant improvements over state-of-the-art benchmarks: on polynomial instances, our relaxation closes an additional 20--25\% of the optimality gap relative to standard methods on half the instances. Furthermore, compared against an enhanced factorable programming baseline and Gurobi's root-node bounds, our approach yields superior dual bounds on approximately 30\% of \texttt{MINLPLib} instances, with roughly 10\% of cases exhibiting a gap reduction exceeding 50\%.

Riddhiman Bhattacharya, Thanh Nguyen, Will Wei Sun et al.

We explore an active learning approach for dynamic fair resource allocation problems. Unlike previous work that assumes full feedback from all agents on their allocations, we consider feedback from a select subset of agents at each epoch of the online resource allocation process. Despite this restriction, our proposed algorithms provide regret bounds that are sub-linear in number of time-periods for various measures that include fairness metrics commonly used in resource allocation problems and stability considerations in matching mechanisms. The key insight of our algorithms lies in adaptively identifying the most informative feedback using dueling upper and lower confidence bounds. With this strategy, we show that efficient decision-making does not require extensive feedback and produces efficient outcomes for a variety of problem classes.

Adarsh Barik, Jean Honorio, Mohit Tawarmalani

We analyze the necessary number of samples for sparse vector recovery in a noisy linear prediction setup. This model includes problems such as linear regression and classification. We focus on structured graph models. In particular, we prove that sufficient number of samples for the weighted graph model proposed by Hegde and others is also necessary. We use the Fano's inequality on well constructed ensembles as our main tool in establishing information theoretic lower bounds.