Arrow Research search

Author name cluster

Matthew J. Streeter

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers
2 author rows

Possible papers

5

UAI Conference 2008 Conference Paper

New Techniques for Algorithm Portfolio Design

  • Matthew J. Streeter
  • Stephen F. Smith

We present and evaluate new techniques for designing algorithm portfolios. In our view, the problem has both a scheduling aspect and a machine learning aspect. Prior work has largely addressed one of the two aspects in isolation. Building on recent work on the scheduling aspect of the problem, we present a technique that addresses both aspects simultaneously and has attractive theoretical guarantees. Experimentally, we show that this technique can be used to improve the performance of state-of-the-art algorithms for Boolean satisfiability, zero-one integer programming, and A.I. planning.

Details

ICAPS Conference 2007 Conference Paper

Using Decision Procedures Efficiently for Optimization

  • Matthew J. Streeter
  • Stephen F. Smith

Optimization problems are often solved by making repeated calls to a decision procedure that answers questions of the form "Does there exist a solution with cost at most k? ". In general the time required by the decision procedure varies widely as a function of k, so it is natural to seek a query strategy that minimizes the time required to find an (approximately) optimal solution. We present a simple query strategy with attractive theoretical guarantees. In case the same decision procedure is used for multiple optimization problems, we discuss how to tailor the query strategy to the sequence of problems encountered. We demonstrate the power of our query strategy by using it to create (i) a modified version of SatPlan that finds provably approximately optimal plans quickly and (ii) a modified branch and bound algorithm for job shop scheduling that yields improved upper and lower bounds.

Details

ICAPS Conference 2006 Conference Paper

Exploiting the Power of Local Search in a Branch and Bound Algorithm for Job Shop Scheduling

  • Matthew J. Streeter
  • Stephen F. Smith

This paper presents three techniques for using an iterated local search algorithm to improve the performance of a state-of-the-art branch and bound algorithm for job shop scheduling. We use iterated local search to obtain (i) sharpened upper bounds, (ii) an improved branch-ordering heuristic, and (iii) and improved variable-selection heuristic. On randomly-generated instances, our hybrid of iterated local search and branch and bound outperforms either algorithm in isolation by more than an order of magnitude, where performance is measured by the median amount of time required to find a globally optimal schedule. We also demonstrate performance gains on benchmark instances from the OR library.

Details

ICAPS Conference 2005 Conference Paper

Charecterizing the Distribution of Low-Makespan Schedules in the Job Shop Scheduling Problem

  • Matthew J. Streeter
  • Stephen F. Smith

We characterize the search landscape of the job shop scheduling problem (JSSP), with a focus on schedules whose makespan is optimal or near-optimal. Building on previous work on the 'big valley' distribution of local optima, we use special branch and bound algorithms to examine in greater detail the extent to which JSSP search spaces conform to the intuitive picture conveyed by the words 'big valley'. We also examine how this changes as a function of the job: machine ratio. We find that for square JSSPs, low-makespan schedules are tightly clustered in a small region of the search space, and the size of this region decreases as the makespan gets closer to optimality. As the job: machine ratio increases beyond 1, however, low-makespan schedules become dispersed throughout the search space. We discuss the reasons for this and provide analytical results for two limiting cases. We close with an examination of neighborhood exactness in the JSSP, which illustrates some limitations of the big valley picture for JSSP landscapes.

Details
v2026.09.13