Index of /projects/partitioning

      Name                    Last modified       Size  Description


[DIR] Parent Directory        09-Feb-2005 15:52      -  
[   ] k_m_tree.c              07-Sep-2001 18:06     6k  
[   ] k_m_tree.desc           07-Sep-2001 18:06     2k  
[   ] sat.h                   07-Sep-2001 18:06     3k  

This directory was created on September 7, 2001.

It contains code K-M-tree generation code by Irina Rish.  Below is an
excerpt from an email message from Irina to Sheila on Monday July 9,
where she

1.  describes the code

2.  identifies some DIMACS problems that are well-structured. 
    These are 
      "dubois20" and "dubois21" (see below)
    We might also want to experiment with 
      "aim-100-2_0-no-1" 

For further explanation see Irina's thesis
          http://www.research.ibm.com/people/r/rish/
 including page 62.

- Sheila


======================================================

From rish@us.ibm.com Mon Jul  9 10:49:36 2001


Hi,
sorry it took me long to get back to you. Here is the code for k-m-tree
generator used in our experiments.
(See attached file: k_m_tree.c)(See attached file: sat.h)

The function you need to call is

void gen_cnf_k_m_tree ( k, m, clq, cls, lit, p ) /* generate a cnf formula
on a  k-m-tree */

int k;      /* k-tree parameter:  */
int k;      /* k-tree parameter:  */
int m;      /* k+m is a clique size */
int clq;    /* number of cliques in a tree */
int cls;    /* number of clauses per clique of size k+m */
int lit;    /* number of literals per clause */
float p;      /* probability of a variable to appear positive in a clause
*/

Good luck, and let me know if there are any problems.

=======================================================================
Sheila wrote:

>Regarding the DIMACS benchmarks, did you find some problems to be more
>structured than others?  Could you recommend some that might be
>suitable for testing out our algorithms?

I tried just a few of them  (the results are in my thesis, at
          http://www.research.ibm.com/people/r/rish/
on page 62.

Some problems had quite low induced width (e.g., 'dubois20' and
'dubois21'), so variable elimination (directional resolution) was 3-4
orders of magnitude faster than search.

Other problems had high induced width, but some of them still could be
easily solved after preprocessing by bounded resolution (BDR(3)) -
e.g., 'aim-100-2_0-no-1'.

Regards,

-----------------------------------------
Irina Rish, PhD
IBM T.J. Watson Research Center
30 Saw Mill River Road
Hawthorne, NY 10532
email: rish@us.ibm.com
Tel:     914-784-7431, Fax:   914-784-6307


Lyndon Drake <lyndon@cs.york.ac.uk> on 02/27/2001 12:01:13 PM

To:   Irina Rish <irinar@ics.uci.edu>
cc:
Subject:  k-tree-embeddings problem generator


I am a PhD student at York University, supervised by Toby Walsh and Alan
Frisch, and studying the use of inference in satisfiability checking.

You mention a k-tree-embeddings random problem generator in your paper
"Resolution versus Search", and as I am interested in structured
problems I was wondering if you would mind sending me a copy of your
problem generator?

I also noticed a link on your web page to Principles and Strategies of
Automated Inference: A Unifying View , AAAI-98 tutorial, Rina Dechter
and Irina Rish.  but the link appears to be broken.  I would be
interested in getting hold of a copy of the tutorial if you still have
it.

Thanks,
Lyndon