Michael D. Moffitt

AAAI Conference 2022 Conference Paper

Search Strategies for Topological Network Optimization

• Michael D. Moffitt

We consider an application of combinatorial search to the optimization of topologies in series-parallel networks. We propose a recursive search over the space of decomposition trees, in which partial solutions are obtained by exploring k-way partitionings of expandable nodes. We present two complementary pruning techniques that bound the value of intermediate solutions from above and below, applying monotonic operations to the contents of unresolved leaves. We also develop a means to exploit the convexity of our objective function, so as to prevent the redundant recomputation of subcircuit configurations. Finally, we evaluate our approach on a parameterized benchmark suite of electrical circuits, demonstrating over an order of magnitude improvement in performance as compared to a baseline implementation.

IJCAI Conference 2013 Conference Paper

Search Strategies for Optimal Multi-Way Number Partitioning

• Michael D. Moffitt

The number partitioning problem seeks to divide a set of n numbers across k distinct subsets so as to minimize the sum of the largest partition. In this work, we develop a new optimal algorithm for multi-way number partitioning. A critical observation motivating our methodology is that a globally optimal k-way partition may be recursively constructed by obtaining suboptimal solutions to subproblems of size k − 1. We introduce a new principle of optimality that provides necessary and sufficient conditions for this construction, and use it to strengthen the relationship between sequential decompositions by enforcing upper and lower bounds on intermediate solutions. We also demonstrate how to further prune unpromising partial assignments by detecting and eliminating dominated solutions. Our approach outperforms the previous state-of-the-art by up to four orders of magnitude, reducing average runtime on the largest benchmarks from several hours to less than a second.

AIJ Journal 2011 Journal Article

On the modelling and optimization of preferences in constraint-based temporal reasoning

• Michael D. Moffitt

In this paper, we consider both the modelling and optimization of preferences in problems of constraint-based temporal reasoning. The Disjunctive Temporal Problems with Preferences (DTPP) – a formulation that combines the rich expressive power of the Disjunctive Temporal Problem with the introduction of metric preference functions – is studied, and transformed into a corresponding constraint system that we name the Valued DTP (VDTP). We show that for a broad family of optimization criteria, the VDTP can express the same solution space as the DTPP, under the assumption of arbitrary piecewise-constant preference functions. We then generalize the powerful search strategies from decision-based DTP literature to accomplish the efficient optimization of temporal preferences. In contrast to the previous state-of-the-art system (which addresses the optimization of temporal preferences using a SAT formulation), we instead employ a meta-CSP search space that has traditionally been used to solve DTPs without preferences. Our approach supports a variety of objective functions (such as utilitarian optimality or maximin optimality) and can accommodate any compliant valuation structure. We also demonstrate that key pruning techniques commonly used for temporal satisfiability (particularly, the removal of subsumed variables and semantic branching) are naturally suited to prevent the exploration of redundant search nodes during optimization that may otherwise be encountered when resolving a typical VDTP derived from a DTPP. Finally, we present empirical results showing that an implementation of our approach consistently outperforms prior algorithms by orders of magnitude.

ICAPS Conference 2011 Conference Paper

Scalable Scheduling for Hardware-Accelerated Functional Verification

• Michael D. Moffitt
• Gernot E. Günther

We consider an application of scheduling to hardware-accelerated functional verification, a massively-parallel computational paradigm used in the simulation of complex integrated circuits. Our domain requires the compilation of logical primitives into a set of instruction memories that optimize the concurrency and communication between tightly synchronized processing units. The scheduling process is burdened by a complex model in which all logical dependencies must be resolved by a dynamic network of routes that compete for sparsely distributed resources. We describe a series of optimization steps that cooperate to minimize simulation depth while scaling to problem sizes on the order of a billion gates. Our approach targets an industrial acceleration architecture containing 262, 144 parallel processors.

IJCAI Conference 2007 Conference Paper

• Michael D. Moffitt
• Martha E. Pollack

In this paper, we focus on extending the expressive power of constraint-based temporal reasoning formalisms. We begin with the well-known Simple Temporal Problem with Uncertainty, and incorporate three extensions: prior observability, in which the values of uncontrollable events become known prior to their actual occurrence; partial shrinkage, in which an observation event triggers the reduction of a contingent temporal interval; and a generalization of partial shrinkage to requirement links, making it possible to express certain types of uncertainty that may arise even when the time points in a problem are themselves fully controllable. We describe levels of controllability in the resulting formalism, the Generalized STPU, and relate this formalism to related developments in disjunctive temporal reasoning. Throughout, we motivate our approach with simple, real-world examples that illustrate the limitations of existing formalisms and the flexibility of our proposed extensions.

AAAI Conference 2007 Conference Paper

On the Partial Observability of Temporal Uncertainty

• Michael D. Moffitt

We explore a means to both model and reason about partial observability within the scope of constraintbased temporal reasoning. Prior studies of uncertainty in Temporal CSPs have required the realization of all exogenous processes to be made entirely visible to the agent. We relax this assumption and propose an extension to the Simple Temporal Problem with Uncertainty (STPU), one in which the executing agent is made aware of the occurrence of only a subset of uncontrollable events. We argue that such a formalism is needed to encode those complex environments whose external phenomena share a common, hidden source of temporal causality. After characterizing the levels of controllability in the resulting Partially Observable STPU and various special cases, we generalize a known family of reduction rules to account for this relaxation, introducing the properties of extended contingency and sufficient observability. We demonstrate that these modifications enable a polynomial filtering algorithm capable of determining a local form of dynamic controllability; however, we also show that there do remain some instances whose global controllability cannot yet be correctly identified by existing inference rules, leaving the true computational complexity of dynamic controllability an open problem for future research.

ICAPS Conference 2006 Conference Paper

Optimal Rectangle Packing: A Meta-CSP Approach

• Michael D. Moffitt
• Martha E. Pollack

We present a new approach to optimal rectangle packing, an NP-complete problem that can be used to model many simple scheduling tasks. Recent attempts at incorporating artificial intelligence search techniques to the problem of rectangle packing have focused on a CSP formulation, in which partial assignments are defined to be the fixed placement of a subset of rectangles. Our technique takes a significant departure from this search space, as we instead view partial assignments as subsets of relative pairwise relationships between rectangles. This approach recalls the meta-CSP commonly constructed in constraint-based temporal reasoning, and is thus a candidate for several pruning techniques that have been developed in that field. We apply these to the domain of rectangle packing, and develop a suite of new techniques that exploit both the symmetry and geometry present in this particular domain. We then provide experimental results demonstrating that our approach performs competitively compared to the previous state-of-the-art on a series of benchmarks, matching or surpassing it in speed on nearly all instances. Finally, we conjecture that our technique is particularly appropriate for problems containing large rectangles, which are difficult for the fixed-placement formulation to handle efficiently.

AAAI Conference 2006 Conference Paper

Temporal Preference Optimization as Weighted Constraint Satisfaction

• Michael D. Moffitt

We present a new efficient algorithm for obtaining utilitarian optimal solutions to Disjunctive Temporal Problems with Preferences (DTPPs). The previous state-of-the-art system achieves temporal preference optimization using a SAT formulation, with its creators attributing its performance to advances in SAT solving techniques. We depart from the SAT encoding and instead introduce the Valued DTP (VDTP). In contrast to the traditional semiring-based formalism that annotates legal tuples of a constraint with preferences, our framework instead assigns elementary costs to the constraints themselves. After proving that the VDTP can express the same set of utilitarian optimal solutions as the DTPP with piecewise-constant preference functions, we develop a method for achieving weighted constraint satisfaction within a meta-CSP search space that has traditionally been used to solve DTPs without preferences. This allows us to directly incorporate several powerful techniques developed in previous decision-based DTP literature. Finally, we present empirical results demonstrating that an implementation of our approach consistently outperforms the SAT-based solver by orders of magnitude.

IJCAI Conference 2005 Conference Paper

Applying Local Search to Disjunctive Temporal Problems

• Michael D. Moffitt
• Martha E

We present a method for applying local search to overconstrained instances of the Disjunctive Temporal Problem (DTP). Our objective is to generate high quality solutions (i. e. , solutions that violate few constraints) in as little time as possible. The technique presented here differs markedly from previous work on DTPs, as it operates within the total assignment space of the underlying CSP rather than the partial assignment space of the related meta-CSP. We provide experimental results demonstrating that the use of local search leads to substantially improved performance over systematic methods.

AAAI Conference 2005 Conference Paper

Augmenting Disjunctive Temporal Problems with Finite-Domain Constraints

• Michael D. Moffitt

We present a general framework for augmenting instances of the Disjunctive Temporal Problem (DTP) with finite-domain constraints. In this new formalism, the bounds of the temporal constraints become conditional on the finite-domain assignment. This hybridization makes it possible to reason simultaneously about temporal relationships between events as well as their nontemporal properties. We provide a special case of this hybridization that allows reasoning about a limited form of spatial constraints; namely, the travel time induced by the locations of a set of activities. We develop a least-commitment algorithm for efficiently finding solutions to this combined constraint system and provide empirical results demonstrating the effectiveness of our approach.

IJCAI Conference 2005 Conference Paper

Identifying Conflicts in Overconstrained Temporal Problems

• Mark H. Liffiton
• Michael D. Moffitt
• Martha E. Pollack
• Karem A

We describe a strong connection between maximally satisfiable and minimally unsatisfiable subsets of constraint systems. Using this relationship, we develop a two-phase algorithm, employing powerful constraint satisfaction techniques, for the identification of conflicting sets of constraints in infeasible constraint systems. We apply this technique to overconstrained instances of the Disjunctive Temporal Problem (DTP), an expressive form of temporal constraint satisfaction problems. Using randomly-generated benchmarks, we provide experimental results that demonstrate how the algorithm scales with problem size and constraint density.

ICAPS Conference 2005 Conference Paper

Solving Over-constrained Disjunctive Temporal Problems with Preferences

• Bart Peintner
• Michael D. Moffitt
• Martha E. Pollack

We present an algorithm and pruning techniques for efficiently finding optimal solutions to over-constrained instances of the Disjunctive Temporal Problem with Preferences (DTPP). Our goal is to remove the burden from the knowledge engineer who normally must reason about an inherent trade-off: including more events and tighter constraints in a DTP leads to higher-quality solutions, but decreases the chances that a solution will exist. Our method solves a potentially over-constrained DTPP by searching through the space of induced DTPPs, which are DTPPs that include a subset of the events in the original problem. The method incrementally builds an induced DTPP and uses a known DTPP algorithm to find the value of its optimal solution. Optimality is defined using an objective function that combines the value of a set of included events with the value of a DTPP induced by those events. The key element in our approach is the use of powerful pruning techniques that dramatically lower the time required to find an optimal solution. We present empirical results that show their effectiveness.