Changes between Version 8 and Version 9 of WikiStart


Ignore:
Timestamp:
Feb 22, 2020 12:58:49 PM (8 months ago)
Author:
stefan
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • WikiStart

    v8 v9  
    1 = Welcome to the MOCHA page =
    2 This page is dedicated to the COIN-OR project MOCHA which stands for ''Matroid Optimization: Combinatorial Heuristics and Algorithms''. MOCHA provides heuristics and algorithms to solve problems in the burgeoning field of multicriteria matroid optimization. Besides specific algorithms and heuristics, matroid data structures are included in order to provide a foundation for old and new algorithms. MOCHA was initially developed for the paper "Computation in Multicriteria Matroid Optimization", accepted by the [http://www.jea.acm.org/ Journal of Experimental Algorithmics], 2009, and authored by J. De Loera, D. Haws, J. Lee, and A. O'Hair.
    3 
    4 = Project Manager =
    5 Dr. David Haws[[BR]]
    6 dchaws+MOCHA@gmail.com[[BR]]
    7 University of Kentucky[[BR]]
    8 Department of Statistics [[BR]]
    9 871 Patterson Office Tower[[BR]]
    10 Lexington, KY 40506-0027
    11 
    12 = Installation =
    13 svn co https://projects.coin-or.org/svn/MOCHA/stable/1.0 MOCHA[[BR]]
    14 cd MOCHA[[BR]]
    15 ./configure[[BR]]
    16 make[[BR]]
    17 make install
    18 
    19 == Third-party software dependencies ==
    20 GMP, LAPACK, BLAS. MOCHA can compile without GMP, though some functionality
    21 will be lost such as rank calculation using arbitrary precision arithmetic.
    22 
    23 Lapack and Blas can be installed by using `ThirdParty/Blas/get.Blas` and `ThirdParty/Lapack/get.Lapack` scripts. Then run `./configure --with-blas=BUILD --with-lapack=BUILD`.
    24 
    25 More information is available in the INSTALL file.
    26 
    27 = Bug Report =
    28 [https://projects.coin-or.org/MOCHA/newticket]
    29 
    30 = FAQ =
    31 [https://projects.coin-or.org/MOCHA/FAQ]
    32 = Matroid Optimization =
    33 Matroids encapsulate the combinatorial notion of independence. They can be
    34 found in graphs, matrices, point sets, hyperplane arrangements and many more.
    35 There are many ways to define a matroid, but for MOCHA the most useful
    36 axiomatization is that of bases. Given a finite set S (ground set) with n
    37 elements, the collection of subsets (B) of S are the bases for a matroid M if
    38 
    39 1) every element of (B) has the same cardinality,
    40 2) if B1 and B2 are in (B), for all x in B1 not in B2, there exists y in B2
    41 not in B1 such that B1 - x + y is in (B).
    42 
    43 Perhaps the simplest matroid example is given by a graph. Given a graph G, the
    44 bases of the matroid on G are all the spanning trees of G. It is not hard to
    45 see that the collection of spanning trees of G all have the same cardinality
    46 and the exchange property 2) holds.
    47 
    48 Another intuitive example is given by a matrix A. The ground set is the labeled
    49 columns of A, and a base of the matroid on A is any maximally linear
    50 independent collection of columns of A. ( Mat[roid/rix] )
    51 
    52 For more on matroids see: "Matroid Theory", Welsh, 1976, "Matroid Theory",
    53 Oxley, 1992 or for a sufficient online coverage [http://en.wikipedia.org/wiki/Matroid].
    54 
    55 Matroid optimization appears when weights are placed on the ground set S. For
    56 example, by placing a single real valued weight on every element of S, every
    57 base B1 has a weight given by the sum of the weights it contains. One could
    58 then optimize over the bases of a matroid by asking for the base with maximal
    59 (minimal) weight. This problem can be solved by the strongly polynomial greedy
    60 algorithm (which MOCHA has a function for).
    61 
    62 MOCHA can tackle an even larger family of optimization problems. Instead of
    63 placing a single real value weight on each element of S, one places d real
    64 valued weights on every element of S. In this case, instead of a base B1 having
    65 a real valued weight, the weight of B1 is a vector in R^d^, given by the sum of
    66 the weights it contains. To ask for an optimal base, given multiple weightings,
    67 one needs a way to decide between two vectors in R^d^. There are multiple
    68 methods to distinguish two points in R^d^, such as a functional f: R^d^ --> R,
    69 Pareto inequality, or min-max. We call these balancing functions, and they may
    70 be linear, convex, or highly non-linear.
    71 
    72 The difficulty of matroid optimization (with multiple weightings) lays in the
    73 fact that there are exponentially many bases with respect to n, the size of the
    74 ground set. So, one can not simply iterate over all bases of a matroid and
    75 optimize. Fortunately, under some assumptions on the weightings applied to the
    76 ground set S, the number of points obtained by considering the weights of all
    77 bases is polynomially bounded. There are deterministic algorithms to compute
    78 the projected bases (projected by the weighting on S), but they are
    79 computationally ''heavy''. See "Nonlinear Matroid Optimization and Experimental
    80 Design", Berstein et. al., 2008.
    81 
    82 MOCHA is a software packaged developed in conjunction with the paper
    83 "Computation in Multicriteria Matroid Optimization", submitted to the ACM
    84 Journal of Experimental Algorithmics, 2009. Its goals are to provide fast
    85 heuristics and algorithms aimed at solving multiple weight matroid optimization
    86 problems. Typically, the choice of weightings on the ground set ensure that the
    87 number of projected bases is much smaller than all bases. Many of MOCHA's
    88 heuristics attempt to give all the projected bases (the most difficult part),
    89 leaving the final optimization over a balancing function for later.
    90 
    91 The software in MOCHA will take in as input a matroid (currently supported
    92 formats are matrices, graphs, uniform) and the weightings on the ground
    93 set.  It will output a subset of the projected bases (guaranteed to be all
    94 projected bases in some cases).
    95 
    96 = How MOCHA works =
    97 Data Format:
    98     The input format for MOCHA is a text file in the following format:[[BR]]
    99 
    100         <MATROID TYPE>[[BR]]
    101         <MATROID DESCRIPTION>[[BR]]
    102         ...[[BR]]
    103         <Number of weightings/criteria>[[BR]]
    104         <Number of matroid elements>[[BR]]
    105         <#> <#>  ... <#>[[BR]]
    106         <#> <#>  ... <#>[[BR]]
    107         ...[[BR]]
    108         <#> <#>  ... <#>[[BR]]
    109 
    110     Example (Instances/Calibration/gn9e18d2w0w20.mo)[[BR]]
    111     GRAPH[[BR]]
    112     ADJACENCY[[BR]]
    113     9[[BR]]
    114     9[[BR]]
    115     1   0   0   0   0   1   0   1   0[[BR]]
    116     0   1   0   0   1   1   1   1   0 [[BR]]
    117     0   0   1   0   0   0   0   1   0 [[BR]]
    118     0   0   0   1   1   0   0   1   0 [[BR]]
    119     0   1   0   1   1   1   1   1   0 [[BR]]
    120     1   1   0   0   1   1   1   1   1 [[BR]]
    121     0   1   0   0   1   1   1   1   1 [[BR]]
    122     1   1   1   1   1   1   1   1   1 [[BR]]
    123     0   0   0   0   0   1   1   1   1 [[BR]]
    124     2[[BR]]
    125     18[[BR]]
    126     18   1   7   1   8   7  14  17   6   9  20   6  10   3   8   5   4  16 [[BR]]
    127     1  18   0   4  16  17  19   1  18   5   1  11   4  17  10   9  19  16 [[BR]]
    128 
    129 
    130     MATROID TYPE can be either "GRAPH" or "VECTOR".
    131     If the type is "GRAPH" then the next line should be "ADJACENCY".
    132     Following this the adjacency representation of the graph should follow.
    133     It should be in the format:[[BR]]
    134     <Number of rows>[[BR]]
    135     <Number of columns>[[BR]]
    136     followed by an appropriate row and column of numbers.
    137 
    138     If the type is "VECTOR" then the following lines should be a matrix
    139     given as[[BR]]
    140     <Number of rows>[[BR]]
    141     <Number of columns>[[BR]]
    142     followed by an appropriate row and column of numbers.
    143 
    144     After the matroid type is specified, the weight is given as a matroid
    145     given as[[BR]]
    146     <Number of rows>[[BR]]
    147     <Number of columns>[[BR]]
    148     followed by an appropriate row and column of numbers.
    149 
    150     An example of a vector matroid representation is:[[BR]]
    151     VECTOR[[BR]]
    152     3[[BR]]
    153     10[[BR]]
    154     0   6   8   7   0  10   6  10   9  10 [[BR]]
    155     3   2   0   6  10   3   5   1   5   5 [[BR]]
    156     4   5   4   9   1   0   1   7  10   6 [[BR]]
    157     2[[BR]]
    158     10[[BR]]
    159     1   7   1   5   7   8   3   7   5   2 [[BR]]
    160     3   8   7   7   0   6   5   3   8   5 [[BR]]
    161 
    162 What MOCHA does:
    163 The most important program is 'matroidtest' which contains heuristics/algorithms
    164 which output subsets of the projected bases. The projected bases are
    165 outputted in matlab format. The file should also be easy to parse using GNU
    166 utilities. We hope to add more output formats.
    167 
    168 The three general methods to find subsets of the projected bases are:
    169 
    170 DFBFS: Different Fiber BFS.[[BR]]
    171 This is a modified version of breadth first search which only pivots to new basis
    172 as long as it is a new projected basis.
    173 
    174 Pivot Test:[[BR]]
    175 This finds a tight rectangular box containing all projected basis then proceeds
    176 to use local search or tabu search on each point (many times if specified), using
    177 a specialized convex function. All the projected bases found are output.
    178 
    179 Boundary:[[BR]]
    180 This outputs the vertices boundary of the convex hull of the projected basis.
    181 Our heuristic also has the side effect of outputting some extreme points besides
    182 the vertices.
    183 
    184 For further description of our algorithms heuristics, see below.
    185 
    186 = Instances from our Paper =
    187 The directory 'Instances/' contains all of our input data for the paper as well as
    188 some simple examples demonstrating our software.
    189 
    190 Detailed How-To/Example:[[BR]]
    191     To reproduce most of the tests in our paper, only three programs
    192     are needed 'matroidtest', 'localsearch', and 'tabusearch'. Below
    193     we give instructions how to reproduce experiments shown in our
    194     paper.
    195 
    196     The program 'matroidtest' has the capability of running the
    197     following algorithms: Different Fiber BFS, Pivot Test, Projected
    198     Boundary Calculation, Pareto Calculation, and Brute force
    199     projected bases calculation (Graphs only). See our paper for
    200     a full description of these algorithms. 'matroidtest' has the
    201     option to output all computed points in a MATLAB ready file
    202     which will plot the points.
    203 
    204     The program 'matroidtest' can be run with no arguments. It is
    205     interactive and will ask which algorithms to run. If more than
    206     one are selected, e.g. DFBFS and Boundary calculation, then
    207     all the points will be output to the same file, with different
    208     labels.
    209 
    210     'matroidtest' can also be invoked as:[[BR]]
    211         matroidtest <inputfile>[[BR]]
    212         or [[BR]]
    213         matroidtest <inputfile> <outputfile>[[BR]]
    214 
    215 
    216     Different Fiber BFS:[[BR]]
    217 
    218         Run 'matroidtest'. Specify the input file either in the command line or
    219         when prompted. Next it will ask "Different Fiber BFS Enumerations?
    220         (y/n)". Enter "y". It will ask for the number of searches. This is the
    221         number of DFBFS searches to perform on the interior and boundary.
    222         'matroidtest' will perform this number of searches using (pseudo)random
    223         projected boundary points. Next, 'matroidtest' starts at a random
    224         unvisited projected base a number of times specified above.  Next
    225         'matroidtest' will ask for the BFS depth. This is the recursion level
    226         that DFBFS will terminate at.  Following this, 'matroidtest' will ask
    227         for the "Interior Random retry limit?".  This is the limit of how many
    228         times DFBFS will try to find a new random projected bases before
    229         giving up. 'matroidtest' will then ask for the "Boundary random retry
    230         limit?". This is the number of times DFBFS will try to find a new
    231         random projected base on the boundary before giving up. When prompted
    232         for all other algorithms/test, enter "n". When prompted for the output
    233         file, give a name. Alternatively enter the output filename as the
    234         second command-line argument.
    235 
    236         Here is a quick example:[[BR]]
    237         Run the following command from the src/ directory: [[BR]]
    238         ./matroidtest ../Instances/Calibration/gn11e20d2w0w100.mo tmpout.m[[BR]]
    239 
    240         Enter the following sequence of input:[[BR]]
    241         y[[BR]]
    242         100[[BR]]
    243         8[[BR]]
    244         10000[[BR]]
    245         100[[BR]]
    246         n[[BR]]
    247         n[[BR]]
    248         n[[BR]]
    249         n[[BR]]
    250         n[[BR]]
    251         n[[BR]]
    252         n[[BR]]
    253 
    254 
    255         This will run DFBFS 100 times, with a truncation level of 8, an
    256         interior retry limit of 10000, and a boundary retry limit of 100.
    257         Typically it takes MOCHA longer to find a random projected boundary
    258         point than an interior point.  It will write the outputed points to
    259         tmpout.m. In MATLAB execute 'tmpout.m'.
    260    
    261     Local Search/Tabu Search:[[BR]]
    262 
    263         The objective for local/tabu search must be hard coded into the files
    264         localsearch.cpp and tabusearch.cpp and recompiled. By default the
    265         object function is set to x^2. We did not want to spend excessive time
    266         implementing or including a bulky format to read in arbitrary objective
    267         functions. To change the objective function, study the function "MyFct"
    268         in localsearch.cpp or tabusearch.cpp.
    269 
    270         localsearch and tabusearch are fully interactive and will ask for all
    271         the necessary arguments. Alternatively they can be invoked as
    272         `localsearch <inputfile> <outputfile> <number of searches>`
    273 
    274         `tabusearch <inputfile> <outputfile> <number of searches> <tabu searchlimit>`
    275 
    276         Again, the output files are written in MATLAB format which can
    277         be run to display graphically the local and tabu searches.
    278 
    279         Example from within /src/ directory:
    280 
    281         ./localsearch ../Instances/Calibration/gn11e20d2w0w20.mo tmp.m 100
    282 
    283         This will use gn11e20d2w0w20.mo as input, output to the file tmp.m
    284         and run 100 local searches.
    285 
    286 
    287     Auto Box Pivot Heuristic:
    288    
    289         This will perform the Pivot Test described in our paper. Run
    290         'matroidtest', specify input and output files and when asked
    291         "Run Auto Box Pivot Heuristic (Local Search)? (y/n)" or
    292         "Run Auto Box Pivot Heuristic (Tabu Search)? (y/n)" select
    293         y according to which pivot heuristic you want to use. 'matroidtest'
    294         will then ask for the number of times to run local search or
    295         tabu search on each point. For tabu search, 'matroidtest' will
    296         also ask for the tabu search limit. The auto box pivot heuristic
    297         will then automatically calculate an appropriate bounding box of
    298         the projected bases using 2(number of weightings) local searches.
    299 
    300         An example run (for localsearch) would be as follows:[[BR]]
    301         Run the command from the src/ directory: [[BR]]
    302         ./matroidtest ../Instances/Calibration/gn11e20d2w0w100.mo tmpout.m
    303 
    304         Enter the following sequence of input:[[BR]]
    305         n[[BR]]
    306         y[[BR]]
    307         20[[BR]]
    308         n[[BR]]
    309         n[[BR]]
    310         n[[BR]]
    311         n[[BR]]
    312         n[[BR]]
    313         n[[BR]]
    314 
    315         This will run the auto box pivot heuristic using local search using
    316         20 attempts for each point.
    317 
    318 
    319     Box Pivot Heuristic:
    320 
    321         This is much the same as the Autobox heuristic above in 'matroidtest'
    322         except that the user is prompted for coordinates of a box of points
    323         to test using Pivot Test.
    324 
    325 
    326     Boundary Calculation:
    327         When there are only two criteria/weightings 'matroidtest' can
    328         calculate the boundary (and more) of the projected bases. When asked
    329         "Run Boundary Calculation (dim=2 only)? (y/n)" enter "y".
    330 
    331 
    332     Pareto Optimum Test:
    333         There are four options for finding Pareto optima:[[BR]]
    334         1) Boundary Only,[[BR]]
    335         2) Boundary Triangular Region Search,[[BR]]
    336         3) BFS Pareto Search, and[[BR]]
    337         4) BFS and Boundary Triangular Region Pareto Search.[[BR]]
    338 
    339         Boundary Only: This will compute the boundary of the projected bases.
    340             'matroidtest' will then output the Pareto optima that are contained
    341             in the boundary.
    342 
    343         Boundary Triangular Region Search: This follows the Boundary and
    344             Triangular Region Pareto Test heuristic described in our paper.
    345             'matroidtest' will compute the boundary, find regions where the
    346             remaining Pareto optima will be, then run the Pivot Heuristic using
    347             either local search or tabu search to enumerate a subset of
    348             potential Pareto optima.
    349 
    350         BFS Pareto Search: This will perform Different Fiber BFS and from the
    351             returned set, compute the Pareto optima. Note that these are only
    352             guaranteed to be Pareto optima of the points found by DFBFS, which
    353             may not necessarily be Pareto optima of the original problem.
    354 
    355         BFS and Boundary Triangular Region Pareto Search: This will perform
    356             DFBFS and Boundary Triangular Region Search and combine the
    357             results.
    358 
    359     Brute Force Enumeration:
    360 
    361         'matroidtest' can also enumerate all projected bases using reverse search
    362         when the matroid is graphical. This uses the algorithm of Matsui.
    363 
    364 
    365 
    366 
    367 = Executables contained in the MOCHA package =
    368 alltoproj
    369     This file is meant to convert the output of findChildren printing all
    370     spanning trees and project them by some given weighting.  Expects input to
    371     be sets given by unsigned ints on each line.  First argument should be the
    372     matrix that is our weighting.  The second argument should be the number of
    373     elements in each set
    374 
    375 designtomatrix
    376     This program will read in two matrices; a n x k exponent vector matrix B,
    377     a m x k design point matrix P
    378 
    379     It then computes A_ij := \prod_{h=1}^k P_{i,h}^B_{j,h}
    380     It reads in the matrices from standard input and prints the matrix to
    381     standard output
    382 
    383 estimatebases
    384     This program estimates the number of bases of a matrix by assigning
    385     random weights to each column of the matrix and finding the maximal
    386     weight basis. This is done m times and the resulting average estimates
    387     the function GAMMA. Then upper and lower bounds for the number of bases
    388     are calculated.
    389 
    390 genmatrix
    391     Generates a random matrix. Useful for creating random examples.
    392     run genmatrix for input format.
    393 
    394 genrandmo
    395    This is an interactive program used to generate random Vector and Graph
    396    matroids along with random weightings.
    397 
    398 graphtest
    399     Program to check validity of some internal graph routines.
    400 
    401 localsearch
    402     Program to perform localsearch heuristic as described in our paper.
    403     See explanation above for usage.
    404 
    405 matroidtest
    406     The program 'matroidtest' has the capability of running the
    407     following algorithms: Different Fiber BFS, Pivot Test, Projected
    408     Boundary Calculation, Pareto Calculation, and Brute force
    409     projected bases calculation (Graphs only). See our paper for
    410     a full description of these algorithms.
    411 
    412 mvbalclust
    413     Non-linear matroid optimization can solve the problem of min variance
    414     balanced clustering. The input is a file that is a matrix of
    415     2k points in R^n^ which are to be partitioned into two sets of size
    416     k such that the variance of their euclidean distances is minimized.
    417     Input is a file with the following format.
    418     <Number of rows>
    419     <Number of columns>
    420     followed by an appropriate row and column of numbers.
    421 
    422 nagibatest
    423     This program was written to test the our implementation of Matsui
    424     and Nagamochi-Ibariki algorithms. The input is
    425     ADJACENCY
    426     <Number of rows>
    427     <Number of columns>
    428     followed by an appropriate row and column of numbers.
    429     The previous matrix is the adjacency representation of the graph.
    430 
    431     nagibatest will enumerate all spanning trees and only print out
    432     the total number of trees. The code can be modified easily
    433     to print out all trees to stdout. Set "printTrees = 1;".
    434    
    435 point2po
    436     This program reads in from stdin points, and finds the pareto optimum using
    437     a straightforward search
    438 
    439 tabusearch
    440     Program to perform localsearch heuristic as described in our paper.
    441     See explanation above for usage.
    442 
    443 testmatrix
    444     Program to internally check matrix class.
    445 
    446 
    447 Data structures and code:
    448     Effort was made to make the code legible and intuitive. The authors
    449     hope to continue to add functionality and subroutines to many of
    450     the objects. Others are welcome and encouraged to contribute!
    451 
     1= MOCHA moved to https://github.com/coin-or/MOCHA =