Russell Bent

ICML Conference 2025 Conference Paper

LEVIS: Large Exact Verifiable Input Spaces for Neural Networks

• Mohamad Fares El Hajj Chehade
• Wenting Li
• Brian Wesley Bell
• Russell Bent
• Saif R. Kazi
• Hao Zhu

The robustness of neural networks is crucial in safety-critical applications, where identifying a reliable input space is essential for effective model selection, robustness evaluation, and the development of reliable control strategies. Most existing robustness verification methods assess the worst-case output under the assumption that the input space is known. However, precisely identifying a verifiable input space $ \mathcal{C} $, where no adversarial examples exist, is challenging due to the possible high dimensionality, discontinuity, and non-convex nature of the input space. To address this challenge, we propose a novel framework, LEVIS, comprising LEVIS-$\alpha$ and LEVIS-$\beta$. LEVIS-$\alpha$ identifies a single, large verifiable ball that intersects at least two boundaries of a bounded region $ \mathcal{C} $, while LEVIS-$\beta$ systematically captures the entirety of the verifiable space by integrating multiple verifiable balls. Our contributions are fourfold: we introduce a verification framework, LEVIS, incorporating two optimization techniques for computing nearest and directional adversarial points based on mixed-integer programming (MIP); to enhance scalability, we integrate complementary constrained (CC) optimization with a reduced MIP formulation, achieving up to a 17-fold reduction in runtime by approximating the verifiable region in a principled way; we provide a theoretical analysis characterizing the properties of the verifiable balls obtained through LEVIS-$\alpha$; and we validate our approach across diverse applications, including electrical power flow regression and image classification, demonstrating performance improvements and visualizing the geometric properties of the verifiable region.

AAAI Conference 2015 Conference Paper

HVAC-Aware Occupancy Scheduling

• BoonPing Lim
• Menkes van den Briel
• Sylvie Thiebaux
• Scott Backhaus
• Russell Bent

Energy consumption in commercial and educational buildings is impacted by group activities such as meetings, workshops, classes and exams, and can be reduced by scheduling these activities to take place at times and locations that are favorable from an energy standpoint. This paper improves on the effectiveness of energy-aware room-booking and occupancy scheduling approaches, by allowing the scheduling decisions to rely on an explicit model of the building’s occupancy-based HVAC control. The core component of our approach is a mixed-integer linear programming (MILP) model which optimally solves the joint occupancy scheduling and occupancy-based HVAC control problem. To scale up to realistic problem sizes, we embed this MILP model into a large neighbourhood search (LNS). We obtain substantial energy reduction in comparison with occupancy-based HVAC control using arbitrary schedules or using schedules obtained by existing heuristic energy-aware scheduling approaches.

AAAI Conference 2015 Conference Paper

Resilient Upgrade of Electrical Distribution Grids

• Emre Yamangil
• Russell Bent
• Scott Backhaus

Modern society is critically dependent on the services provided by engineered infrastructure networks. When natural disasters (e. g. Hurricane Sandy) occur, the ability of these networks to provide service is often degraded because of physical damage to network components. One of the most critical of these networks is the electrical distribution grid, with medium voltage circuits often suffering the most severe damage. However, well-placed upgrades to these distribution grids can greatly improve post-event network performance. We formulate an optimal electrical distribution grid design problem as a two-stage, stochastic mixed-integer program with damage scenarios from natural disasters modeled as a set of stochastic events. We develop and investigate the tractability of an exact and several heuristic algorithms based on decompositions that are hybrids of techniques developed by the AI and operations research communities. We provide computational evidence that these algorithms have significant benefits when compared with commercial, mixed-integer programming software.

AAAI Conference 2012 Conference Paper

Last-Mile Restoration for Multiple Interdependent Infrastructures

• Carleton Coffrin
• Pascal Van Hentenryck
• Russell Bent

AAAI Conference 2010 Conference Paper

Transmission Network Expansion Planning with Simulation Optimization

• Russell Bent
• Alan Berscheid
• G. Loren Toole

Within the electric power literature the transmission expansion planning problem (TNEP) refers to the problem of how to upgrade an electric power network to meet future demands. As this problem is a complex, non-linear, and non-convex optimization problem, researchers have traditionally focused on approximate models of power flows. Existing approaches are often tightly coupled to the approximation choice. Until recently, these approximations have produced results that are straight-forward to adapt to the more complex (real) problem. However, the power grid is evolving towards a state where the adaptations are no longer easy (e. g. large amounts of limited control, renewable generation) that necessitates new optimization techniques. In this paper, we propose a local search variation of the powerful Limited Discrepancy Search (LDLS) that encapsulates the complexity of power flows in a black box that may be queried for information about the quality of a proposed expansion. This allows the development of a new optimization algorithm that is independent of the underlying power model.

IJCAI Conference 2007 Conference Paper

• Russell Bent
• Pascal Van Hentenryck

This paper considers online stochastic multiple vehicle routing with time windows in which requests arrive dynamically and the goal is to maximize the number of serviced customers. Contrary to earlier algorithms which only move vehicles to known customers, this paper investigates waiting and relocation strategies in which vehicles may wait at their current location or relocate to arbitrary sites. Experimental results show that waiting and relocation strategies may dramatically improve customer service, especially for problems that are highly dynamic and contain many late requests. The decisions to wait and to relocate do not exploit any problem-specific features but rather are obtained by including choices in the online algorithm that are necessarily sub-optimal in an offline setting.

ICAPS Conference 2005 Conference Paper

Online Stochastic Optimization Without Distributions

• Russell Bent
• Pascal Van Hentenryck

This paper considers online stochastic scheduling problems where time constraints severely limit the number of optimizations which can be performed at decision time and/or in between decisions. Prior research has demonstrated that, whenever a distribution of the inputs is available for sampling, online stochatic algorithms may produce significant improvements in solution quality over oblivious approaches. However, the availability of an input distribution, although reasonable in many contexts, is too strong a requirement in a variety of applications. This paper broadens the applicability of online stochastic algorithms by relaxing this requirement and using machine learning techniques or historical data instead. In particular, it shows that machine learning techniques can be engineered to learn the distribution online, when its underlying structure is not available. Moreover, the paper presents the idea of historical sampling which provides a simple and effective way to leverage historical data in continuous and periodic online optimization. Experimental results on packet scheduling and vehicle routing indicate the potential of machine learning and historical sampling for online scheduling.

AAAI Conference 2004 Conference Paper

Regrets Only! Online Stochastic Optimization under Time Constraints

• Russell Bent
• Pascal Van Hentenryck

This paper considers online stochastic optimization problems where time constraints severely limit the number of offline optimizations which can be performed at decision time and/or in between decisions. It proposes a novel approach which combines the salient features of the earlier approaches: the evaluation of every decision on all samples (expectation) and the ability to avoid distributing the samples among decisions (consensus). The key idea underlying the novel algorithm is to approximate the regret of a decision d. The regret algorithm is evaluated on two fundamentally different applications: online packet scheduling in networks and online multiple vehicle routing with time windows. On both applications, it produces significant benefits over prior approaches.

ICAPS Conference 2004 Conference Paper

The Value of Consensus in Online Stochastic Scheduling

• Russell Bent
• Pascal Van Hentenryck

This paper reconsiders online packet scheduling in computer networks, where the goal is to minimize weighted packet loss and where the arrival distributions of packets, or approximations thereof, are available for sampling. Earlier work proposed an expectation approach, which chooses the next packet to schedule by approximating the expected loss of each decision over a set of scenarios. The expectation approach was shown to significantly outperform traditional approaches ignoring stochastic information. This paper proposes a novel stochastic approach for online packet scheduling, whose key idea is to select the next packet as the one which is scheduled first most often in the optimal solutions of the scenarios. This consensus approach is shown to outperform the expectation approach significantly whenever time constraints and the problem features limit the number of scenarios that can be solved before making a decision. More importantly perhaps, the paper shows that the consensus and expectation approaches can be integrated to combine the benefits of both approaches. These novel online stochastic optimization algorithms are generic and problem-independent, they apply to other online applications as well, and they shed new light on why existing online stochastic algorithms behave well.

IJCAI Conference 2003 Conference Paper

Dynamic Vehicle Routing with Stochastic Requests

• Russell Bent
• Pascal Van Hentenryck

This paper considers vehicle routing problems (VRP) where customer locations and service times are random variables that are realized dynamically during plan execution. It proposes a multiple scenario approach (MSA) that continuously generates plans consistent with past decisions and anticipating future requests. The approach, which combines Al and OR techniques in novel ways, is compared with the best available heuristics that model longdistance courier mail services [Larsen et al, 2002]. Experimental results shows that MSA may significantly decrease travel times and is robust wrt reasonably noisy distributions.