J. Christopher Beck
YOU?
Author Swipe
View article: New Exact Methods for Solving Quadratic Traveling Salesman Problem
New Exact Methods for Solving Quadratic Traveling Salesman Problem Open
The Quadratic Traveling Salesman Problem (QTSP) is a generalization of the Traveling Salesman Problem (TSP) with important applications in robotics and bioinformatics. The QTSP objective value depends on pairs of consecutive edges in the t…
View article: Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming
Reinforcement Learning-based Heuristics to Guide Domain-Independent Dynamic Programming Open
Domain-Independent Dynamic Programming (DIDP) is a state-space search paradigm based on dynamic programming for combinatorial optimization. In its current implementation, DIDP guides the search using user-defined dual bounds. Reinforcement…
View article: Optimization Models for the Quadratic Traveling Salesperson Problem
Optimization Models for the Quadratic Traveling Salesperson Problem Open
The quadratic traveling salesperson problem (QTSP) is a generalization of the traveling salesperson problem, in which all triples of consecutive customers in a tour determine the travel cost. We propose compact optimization models for QTSP…
View article: Deriving Compact QUBO Models via Multilevel Constraint Transformation
Deriving Compact QUBO Models via Multilevel Constraint Transformation Open
With the advances in customized hardware for quantum annealing and digital/CMOS Annealing, Quadratic Unconstrained Binary Optimization (QUBO) models have received growing attention in the optimization literature. Motivated by an existing g…
View article: Determining pre-procedure fasting alert time using procedural and scheduling data
Determining pre-procedure fasting alert time using procedural and scheduling data Open
Before a medical procedure requiring anesthesia, patients are required to not eat or drink non-clear fluids for 6 h and not drink clear fluids for 2 h. Fasting durations in standard practice far exceed these minimum thresholds due to uncer…
View article: PRP Rebooted: Advancing the State of the Art in FOND Planning
PRP Rebooted: Advancing the State of the Art in FOND Planning Open
Fully Observable Non-Deterministic (FOND) planning is a variant of classical symbolic planning in which actions are nondeterministic, with an action's outcome known only upon execution. It is a popular planning paradigm with applications r…
View article: Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming
Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming Open
Domain-independent dynamic programming (DIDP), a model-based paradigm based on dynamic programming, has shown promising performance on multiple combinatorial optimization problems compared with mixed integer programming (MIP) and constrain…
View article: Domain-Independent Dynamic Programming and Constraint Programming Approaches for Assembly Line Balancing Problems with Setups
Domain-Independent Dynamic Programming and Constraint Programming Approaches for Assembly Line Balancing Problems with Setups Open
We propose domain-independent dynamic programming (DIDP) and constraint programming (CP) models to exactly solve type-1 and type-2 assembly line balancing problem with sequence-dependent setup times (SUALBP). The goal is to assign tasks to…
View article: Domain-Independent Dynamic Programming
Domain-Independent Dynamic Programming Open
For combinatorial optimization problems, model-based paradigms such as mixed-integer programming (MIP) and constraint programming (CP) aim to decouple modeling and solving a problem: the `holy grail' of declarative problem solving. We prop…
View article: PRP Rebooted: Advancing the State of the Art in FOND Planning
PRP Rebooted: Advancing the State of the Art in FOND Planning Open
Fully Observable Non-Deterministic (FOND) planning is a variant of classical symbolic planning in which actions are nondeterministic, with an action's outcome known only upon execution. It is a popular planning paradigm with applications r…
View article: Extracting and Exploiting Bounds of Numeric Variables for Optimal Linear Numeric Planning
Extracting and Exploiting Bounds of Numeric Variables for Optimal Linear Numeric Planning Open
In numeric AI planning, a state is represented by propositions and numeric variables, actions change the values of numeric variables in addition to adding and deleting propositions, and goals and preconditions of actions may include condit…
View article: Solving Domain-Independent Dynamic Programming Problems with Anytime Heuristic Search
Solving Domain-Independent Dynamic Programming Problems with Anytime Heuristic Search Open
Domain-independent dynamic programming (DIDP) is a recently proposed model-based paradigm for combinatorial optimization where a problem is formulated as dynamic programming (DP) and solved by a generic solver. In this paper, we develop an…
View article: Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization
Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization Open
For combinatorial optimization problems, model-based approaches such as mixed-integer programming (MIP) and constraint programming (CP) aim to decouple modeling and solving a problem: the `holy grail' of declarative problem solving. We pro…
View article: Symmetry Detection and Breaking in Linear Cost-Optimal Numeric Planning
Symmetry Detection and Breaking in Linear Cost-Optimal Numeric Planning Open
One of the main challenges of domain-independent numeric planning is the complexity of the search problem. The exploitation of structural symmetries in a search problem can constitute an effective method of pruning search branches that may…
View article: Privacy Attacks on Schedule-Driven Data
Privacy Attacks on Schedule-Driven Data Open
Schedules define how resources process jobs in diverse domains, reaching from healthcare to transportation, and, therefore, denote a valuable starting point for analysis of the underlying system. However, publishing a schedule may disclose…
View article: The LM-Cut Heuristic Family for Optimal Numeric Planning with Simple Conditions
The LM-Cut Heuristic Family for Optimal Numeric Planning with Simple Conditions Open
The LM-cut heuristic, both alone and as part of the operator counting framework, represents one of the most successful heuristics for classical planning. In this paper, we generalize LM-cut and its use in operator counting to optimal numer…
View article: Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization
Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization Open
For combinatorial optimization problems, model-based approaches such as mixed-integer programming (MIP) and constraint programming (CP) aim to decouple modeling and solving a problem: the 'holy grail' of declarative problem solving. We pro…
View article: Capacity Allocation for Clouds with Parallel Processing, Batch Arrivals, and Heterogeneous Service Requirements
Capacity Allocation for Clouds with Parallel Processing, Batch Arrivals, and Heterogeneous Service Requirements Open
Problem Definition: Allocating sufficient capacity to cloud services is a challenging task, especially when demand is time-varying, heterogeneous, contains batches, and requires multiple types of resources for processing. In this setting, …
View article: LM-Cut Heuristics for Optimal Linear Numeric Planning
LM-Cut Heuristics for Optimal Linear Numeric Planning Open
While numeric variables play an important, sometimes central, role in many planning problems arising from real world scenarios, most of the currently available heuristic search planners either do not support such variables or impose heavy …
View article: Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware
Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware Open
The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, sp…
View article: Biased Exploration for Satisficing Heuristic Search
Biased Exploration for Satisficing Heuristic Search Open
Satisficing heuristic search such as greedy best-first search (GBFS) suffers from local minima, regions where heuristic values are inaccurate and a good node has a worse heuristic value than other nodes. Search algorithms that incorporate …
View article: Decision Diagrams for Discrete Optimization: A Survey of Recent Advances
Decision Diagrams for Discrete Optimization: A Survey of Recent Advances Open
In the last decade, decision diagrams (DDs) have been the basis for a large array of novel approaches for modeling and solving optimization problems. Many techniques now use DDs as a key tool to achieve state-of-the-art performance within …
View article: Exploiting Hardware and Software Advances for Quadratic Models of Wind Farm Layout Optimization
Exploiting Hardware and Software Advances for Quadratic Models of Wind Farm Layout Optimization Open
A key aspect of the design of a wind farm is the wind farm layout optimization (WFLO) problem: given a wind farm site and information about the wind patterns, the problem is to decide the location of individual wind turbines to maximize en…
View article: A Hybrid Quantum-Classical Approach to Solving Scheduling Problems
A Hybrid Quantum-Classical Approach to Solving Scheduling Problems Open
An effective approach to solving complex problems is to decompose them and integrate dedicated solvers for those subproblems. We introduce a hybrid decomposition that incorporates: (1) a quantum annealer that samples from the configuration…
View article: Cost-Based Heuristics and Node Re-Expansions across the Phase Transition
Cost-Based Heuristics and Node Re-Expansions across the Phase Transition Open
Recent work aimed at developing a deeper understanding of suboptimal heuristic search has demonstrated that the use of a cost-based heuristic function in the presence of large operator cost ratio and the decision to allow re-opening of vis…
View article: Invited Speakers
Invited Speakers Open
s of the invited speaker talks Modeling, Global Constraints, and Decomposition by J. Christopher Beck and Applications of Graph Search in Group Theory and Proteomics by Gene Cooperman, presented that the 2013 SoCS Symposium.
View article: Counterfactual Explanations for Optimization-Based Decisions in the Context of the GDPR
Counterfactual Explanations for Optimization-Based Decisions in the Context of the GDPR Open
The General Data Protection Regulations (GDPR) entitle individuals to explanations for automated decisions. The form, comprehensibility, and even existence of such explanations remain open problems, investigated as part of explainable AI. …
View article: Relaxed BDDs: An Admissible Heuristic for Delete-Free Planning Based on a Discrete Relaxation
Relaxed BDDs: An Admissible Heuristic for Delete-Free Planning Based on a Discrete Relaxation Open
We investigate the use of relaxed binary decision diagrams (BDDs) as an alternative to linear programming (LP) for computing an admissible heuristic for the cost-optimal delete-free planning (DFP) problem. Our main contributions are the in…