Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

CATS 2.0 User Guide Galen Andrew 1 Compiling CATS You will probably have to edi

CATS 2.0 User Guide Galen Andrew 1 Compiling CATS You will probably have to edit the Makeﬁle to get CATS to compile on your system. If there are compilation problems, check the library and include directories in the Makeﬁle. The current Makeﬁle is conﬁgured to compile in Linux. To compile on UNIX, remove the -DLINUX ﬂags. To compile on Windows systems, remove the -DLINUX ﬂags and add -DWIN32 and -D WIN32. These instructions are also in the Makeﬁle. To solve linear programming problems, CATS uses a free library called lp solve 4.0 by default, which is included with the distribution. If you have access to CPLEX 8.0, we strongly recommend using it in place of lp solve 4.0. This requires only commenting out one section of the Makeﬁle and uncommenting another. Precise instructions are included in the Makeﬁle. 2 CATS command line 2.1 Required Parameters CATS requires three pieces of information in the command line: the type of distribution, the number of bids, and the number of goods. A single built-in distribution from which all instances are to be generated is selected with the -d ﬂag and can be any of the following: arbitrary, arbitrary-npv, arbitrary-upv, matching, paths, regions, regions-npv, regions-upv, scheduling, L1, L2, L3, L4, L5, L6, L7, and L8. The distributions are deﬁned in [1]. The optional suﬃxes -npv and -upv available for the regions and arbi- trary distributions specify that valuations are to be drawn from either a normal or uniform distribution, respectively. If a suﬃx is omitted, the valuation distribution is selected at random for each instance. The -uniform hybrid ﬂag can be used in place of the -d ﬂag to produce instances by ﬁrst choosing a built-in distribution uniformly at random for each instance,1 then generating from it. The -dist dist ﬂag, described in section 3.1, can also be used in place of -d. The number of goods and bids must also be speciﬁed for each run. If every instance is to have the same number of goods and bids, the -goods and -bids ﬂags are used to provide these numbers. It is also possible to choose the numbers of goods and bids separately for each instance from a uniform distribution over a speciﬁed range. This is done with the -random goods and -random bids ﬂags. Both are followed by two integers specifying the minimum and maximum values of the range. If the -default hard ﬂag is used (see section 3.5), all of the above parameters take on default values and are not required. A speciﬁc distribution can still be chosen, but the number of bids and goods, if they are (redundantly) entered, must be 1000 and 256, respectively, since our hardness models are based on this problem size. The 2.1 release of CATS may allow variable problem sizes. 1L1 and L5 are excluded because it is impossible to generate large numbers of non-dominated bids with them. Regions and arbitrary are given equal weight to the other distributions before a valuation type is chosen. 1 2.2 Optional Parameters CATS can be given several optional parameters that are listed and described here, with their default values: • -n [1]: number of instance ﬁles that you want CATS to generate • -seed [taken from clock]: random seed • -seed2 [taken from clock]: random seed 2: used only for normal distributions • -bid alpha [1000]: multiply prices by this before rounding, when -int prices is set • -num weighted samples [50]: number of samples to take in generating from distribution over fea- tures (see section 3) 2.3 Optional Flags The following optional ﬂags also alter CATS’ behavior. The ones with arguments have no default values. • -cplex: write a CPLEX-compatible .lp ﬁle as well as a CATS data ﬁle • -no dom check: turn oﬀremoval of dominated bids. The default CATS behavior is to keep gener- ating bids until the speciﬁed number of non-dominated bids have been generated. • -int prices: write integer prices in bids instead of real-valued prices • -filename: set ﬁlename preﬁx for generated instances • -no output: do not write unnecessary output to the screen • -random parameters: choose distribution parameters uniformly from their ranges independently for each instance • -model filenames: ﬁle containing ﬁlenames of polynomially deﬁned distributions over distribution parameters and/or polynomial functions of instance features for weighted sampling (see section 3) • -model file help: print help screen for model ﬁle features • -no normalization: turns oﬀnormalization of all polynomially deﬁned distributions. If the polyno- mials do not represent proper probability density functions over their ranges, behavior is undeﬁned. • -default hard: weight problems for hardness using the built-in hardness model (see section 3) • -help, -h, -?: print a usage screen. If a distribution is selected with -d, help speciﬁc to that distribution is also printed. 3 Advanced Features CATS 2.0 has several advanced features over CATS 1.0 as described in [1], related to the work of Kevin Leyton-Brown, Eugene Nudelman, Galen Andrew, Jim McFadden and Yoav Shoham during 2002- 2003 [2] [3]. They enable the creation of new distributions by skewing the built-in distributions to emphasize desired regions of the problem space. The features are ﬁrst described, and an explanation of how to use them in a run of CATS follows. In the discussion, we will refer to the built-in distributions and the uniform hybrid distribution using either constant or uniformly randomized parameter settings as simple distributions. 2 3.1 Arbitrary hybrid distributions It is possible to generate instances from a user-speciﬁed hybrid distribution that, for each instance, ﬁrst selects one of the built-in distributions with probabilities speciﬁed by the user, and then generates a set of bids from that distribution. This is done with the -dist dist ﬂag. The argument to this ﬂag is the name of a ﬁle containing a list of numbers specifying the probability of choosing each distribution. The ﬁle must contain one number for each of the built-in distributions (excluding regions and arbitrary, exactly 15 in all) in the order listed in section 2.1, separated by whitespace. The regions and arbitrary distributions are omitted because they are redundant: any probability assigned to them can be divided directly into the -npv and -upv probabilities. If the entries do not sum to 1, they will be normalized. 3.2 Specifying Parameter Distributions Every CATS distribution has from 1 to 7 parameters. These parameters can be used with their default values, can be individually set at the beginning of a run, or can be chosen for each instance uniformly from their ranges with the -random parameters ﬂag. They can also be chosen according to a polynomially deﬁned joint distribution. CATS will interpret the polynomial (which must have the same number of variables as the distribution has parameters) as a pdf and choose the parameter settings for each instance by sampling from it. Unless the -no normalization ﬂag is used, CATS will ﬁrst normalize the distribution to ensure that it is non-negative on the ranges of the parameters and integrates to one. In fact, CATS will not only raise the polynomial to be non-negative everywhere, it will also lower the polynomial, if necessary, to ensure that the minimum is zero. At present, the only way to specify a distribution with minimum value greater than zero is to use -no normalization. 3.3 Specifying Feature Weighting CATS is equipped with procedures for calculating 32 features of instances that are predictive of instance hardness. It is possible to provide a polynomial function of these features that is used to do weighted sampling from instances. CATS then generates from the product of a simple distribution and the feature polynomial, reinterpreted as a pdf. This essentially skews the simple distribution to emphasize instances that are weighted more heavily by the feature polynomial. If this feature is enabled, for each instance generated, ﬁrst a certain number of samples are created (the default is 50) according to a simple distribution. Their feature values are calculated, and then one is sampled for output after weighting the samples according to the feature polynomial evaluated at the calculated feature vectors. The number of samples can be changed with the -num weighted samples ﬂag. There is no way to determine exactly how many samples are necessary for accurate sampling, but it should be likely that a few highly weighted instances are generated within the given number of samples. Several feature polynomials may be entered (up to a maximum of 10), in which case it is their minimum that is used as the weight for sampling. The original purpose of this feature was to weight instances according to their estimated hardness when solved using an algorithm portfolio [2], which is the minimum estimated run-time of the portfolio’s constituent algorithms. 3.4 Interaction of Parameter Distributions and Feature Weighting Both parameter distributions and feature weighting can be used during the same run of CATS. This will not, as might be expected, generate from the distribution using the parameter model skewed according to the feature model.2 Problems will still be generated from the product of uploads/Philosophie/ cats-2-0-user-guide.pdf