An official website of the United States government
Decision diagrams (DDs) are widely used in system verification to compute and store the state space of finite discrete events dynamic systems (DEDSs). DDs are organized into levels, and it is well known that the size of a DD encoding a given set may be very sensitive to the order in which the variables capturing the state of the system are mapped to levels. Computing optimal orders is NP-hard. Several heuristics for variable order computation have been proposed, and metrics have been introduced to evaluate these orders. However, we know of no published evaluation that compares the actual predictive power for all these metrics. We propose and apply a methodology to carry out such an evaluation, based on the correlation between the metric value of a variable order and the size of the DD generated with that order. We compute correlations for several metrics from the literature, applied to many variable orders built using different approaches, for 40 DEDSs taken from the literature. Our experiments show that these metrics have correlations ranging from "very weak or nonexisting" to "strong." We show the importance of highly correlating metrics on variable order heuristics, by defining and evaluating two new heuristics (an improvement of the well-known Force heuristic and a metric-based simulated annealing), as well as a meta-heuristic (that uses a metric to select the "best" variable order among a set of different variable orders).
more »
« less
Decision-Tree Learning-Inspired Dynamic Variable Ordering for the Weighted CSP
The weighted constraint satisfaction problem (WCSP) is a powerful mathematical framework for combinatorial optimization. The branch-and-bound search paradigm is very successful in solving the WCSP but critically depends on the ordering in which variables are instantiated. In this paper, we introduce a new framework for dynamic variable ordering for solving the WCSP. This framework is inspired by regression decision tree learning. Variables are ordered dynamically based on samples of random assignments of values to variables as well as their corresponding total weights. Within this framework, we propose four variable ordering heuristics (sdr, inv-sdr, rr and inv-rr). We compare them with many state-of-the-art dynamic variable ordering heuristics, and show that sdr and rr outperform them on many real-world and random benchmark instances.
more »
« less
- Award ID(s):
- 1724392
- PAR ID:
- 10179954
- Date Published:
- Journal Name:
- Symposium on Combinatorial Search (SoCS)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
SDR 2.0 Cotton File: Cumulative List of Variables in the Surveys of the SDR Database is a comprehensive data dictionary, in Microsoft Excel format. Its main purpose is to facilitate the overview of 88118 variables (i.e. variable names, values, and labels) available in the original (source) data files that we retrieved automatically for harmonization purposes in the SDR Project. Information in the Cotton File comes from 215 source data files that comprise ca. 3500 national surveys administered between 1966 and 2017 in 169 countries or territories, as part of 23 international survey projects.more » « less
-
In this paper, we adopt a new perspective on the Multi-Agent Path Finding (MAPF) problem and view it as a Constraint Satisfaction Problem (CSP). A variable corresponds to an agent, its domain is the set of all paths from the start vertex to the goal vertex of the agent, and the constraints allow only conflict-free paths for each pair of agents. Although the domains and constraints are only implicitly defined, this new CSP perspective allows us to use successful techniques from CSP search. With the concomitant idea of using matrix computations for calculating the size of the reduced domain of an uninstantiated variable, we apply Dynamic Variable Ordering and Rapid Random Restarts to the MAPF problem. In our experiments, the resulting simple polynomial-time MAPF solver, called Matrix MAPF solver, either outperforms or matches the performance of many state-of-the-art solvers for the MAPF problem and its variants.more » « less
-
ABSTRACT We explore the synergy between photometric and spectroscopic surveys by searching for periodic variable stars among the targets observed by the Apache Point Observatory Galactic Evolution Experiment (APOGEE) using photometry from the All-Sky Automated Survey for Supernovae (ASAS-SN). We identified 1924 periodic variables among more than $$258\, 000$$ APOGEE targets; 465 are new discoveries. We homogeneously classified 430 eclipsing and ellipsoidal binaries, 139 classical pulsators (Cepheids, RR Lyrae, and δ Scuti), 719 long-period variables (pulsating red giants), and 636 rotational variables. The search was performed using both visual inspection and machine learning techniques. The light curves were also modelled with the damped random walk stochastic process. We find that the median [Fe/H] of variable objects is lower by 0.3 dex than that of the overall APOGEE sample. Eclipsing binaries and ellipsoidal variables are shifted to a lower median [Fe/H] by 0.2 dex. Eclipsing binaries and rotational variables exhibit significantly broader spectral lines than the rest of the sample. We make ASAS-SN light curves for all the APOGEE stars publicly available and provide parameters for the variable objects.more » « less
-
In supervised learning, we leverage a labeled dataset to design methods for function estimation. In many practical situations, we are able to obtain alternative feedback, possibly at a low cost. A broad goal is to understand the usefulness of, and to design algorithms to exploit, this alternative feedback. We focus on a semi-supervised setting where we obtain additional ordinal (or comparison) information for potentially unlabeled samples. We consider ordinal feedback of varying qualities where we have either a perfect ordering of the samples, a noisy ordering of the samples or noisy pairwise comparisons between the samples. We provide a precise quantification of the usefulness of these types of ordinal feedback in non-parametric regression, showing that in many cases it is possible to accurately estimate an underlying function with a very small labeled set, effectively escaping the curse of dimensionality. We develop an algorithm called Ranking-Regression (RR) and analyze its accuracy as a function of size of the labeled and unlabeled datasets and various noise parameters. We also present lower bounds, that establish fundamental limits for the task and show that RR is optimal in a variety of settings. Finally, we present experiments that show the efficacy of RR and investigate its robustness to various sources of noise and model-misspecification.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
