We consider a broad class of bilevel linear programs in which the follower’s decisions are all continuous, while the leader’s decisions may include integrality restrictions. Solving such problems to optimality is known to be NP-hard. A classical approach in bilevel optimization for constructing lower and upper bounds is based on a single-level relaxation, in which … Read more
We address the problem of optimal route planning for competitive orien- teering on real terrain. A Geographic Information System (GIS) pipeline transforms orienteering map data and digital terrain models into a fully asymmetric cost matrix that captures directional slope costs (via the Minetti metabolic model) and cumulative athlete fatigue. The resulting problem, the Asymmetric Orienteering … Read more
Live reoptimization of operating room schedules is required to cope with disruptions such as emergency arrivals and deviations in surgery durations under strict time limits. The resulting problem can be formulated as a large-scale Resource Constrained Project Scheduling Problem (RCPSP). While exact optimization methods are attractive in this context due to their ability to provide … Read more
Classical optimization methods determine a single optimal or near-optimal solution for a decision problem. In many applications, however, the decision maker is interested in evaluating a pool of high-quality solutions, to encode fairness-oriented criteria or to obtain a portfolio of alternatives to use in case of unexpected scenarios. In this paper, we consider the problem … Read more
The length-constrained cycle partition problem (LCCP) is a graph optimization problem in which a set of nodes must be partitioned into a minimum number of cycles. Every node is associated with a critical time and the length of every cycle must not exceed the critical time of any node in the cycle. We formulate LCCP … Read more
We study energy-efficient operation of underground train networks by integrating power profile optimization with timetable design in a single mixed-integer optimization framework. The model minimizes traction energy by synchronizing braking and acceleration across trains sharing a power subnetwork to exploit regenerative energy and flexibly allocating running times to promote coasting. Unlike timetable-only approaches with fixed … Read more
Imagine that you are in front of a cockpit with several on–off buttons. If you were to thoroughly test it, you would need to try a prohibitive number of configurations. But since most bugs in practice can be isolated to interactions among few components, having tests that cover every possible pairwise configuration is a good … Read more
Primal heuristics for finding high-quality feasible solutions are an important component in mixed-integer optimization (MIO) solvers. Recent advances in GPU-accelerated optimization algorithms show the potential of GPU acceleration for continuous optimization. In this paper, we introduce the Parallel Node Generation and Exploration Algorithm (PaNGEA), a GPU-friendly MIO primal heuristic. PaNGEA explores restricted subproblems by combining … Read more
Tracking targets in undersea warfare requires successful detection by an active search asset. Maximizing detection likelihood requires strategic placement and routing of the search assets in the search region over the planning horizon. We develop a two-stage stochastic integer programming model that maximizes the expected total reward for target detections under uncertainty in target motion … Read more
This research introduces the Stochastic Sequential Queens Elimination Problem, where on the \(n\)-queens board, each activated queen simultaneously attempts to eliminate all queens in her unblocked neighborhood, each independently succeeding with probability \(p\). The objective is to minimize the expected cumulative conflict count over the trajectory. This research proposes a Markov decision process for this … Read more