"""Solves given align-BDD instances to benchmark different methods.
Takes a list of align-BDD instances (generated by :py:mod:`gen_BDD_pair`) and solves it applying different heuristics. In particular, for each instance the script:
- generates the simplified problem and solves it with heuristics described in list :py:attr:`heuristics.SIMPL_HEU`,
- solves the original problem with the heuristics described in list :py:attr:`heuristics.ORIG_HEU`.
For each operation, runtime and the resulting objective are logged (and saved in a ``csv`` formatted file).
"""
import BDD as exact
import varseq as simpl
from time import time
import BB_search as bb
import heuristics as heu
import numpy as np
import sys
from copy import deepcopy
import argparse as ap
from experiments.misc import log
[docs]def main():
"""Implements the instance solution."""
parser = ap.ArgumentParser(description="Processes (solves) a list of align-BDD instances (c) A. Bochkarev, Clemson University, 2020",
formatter_class=ap.ArgumentDefaultsHelpFormatter)
parser.add_argument("-i", "--in", action="store", dest="inst_list", help="filename for instances list to process")
parser.add_argument("-o", "--out", action="store", dest="logfile", help="filename for the log")
parser.add_argument("-d", "--directory", action="store", dest="inst_dir", help="directory with instances")
parser.add_argument("-H", "--header", action="store_true", dest="header", help="show header only and exit")
args = parser.parse_args()
if args.header:
log("instance","num_type","value",comment="comment")
# needed for the legend
for heuristic in heu.SIMPL_HEU:
log("-1,legend",heuristic[0], comment=heuristic[2])
for heuristic in heu.ORIG_HEU:
log("-1,legend",heuristic[0], comment=heuristic[2])
log("-1,legend,simpl_BB", comment="Branch-and-bound")
exit(0)
inst_dir = args.inst_dir
with open(args.inst_list,"r") as inst_list:
with open(args.logfile,"w") as logf:
# process instances
for inst_id in inst_list:
inst_id = inst_id.rstrip()
if inst_id == "":
continue
t0=time()
fnameA = "".join([inst_dir, "A",inst_id,".bdd"])
fnameB = "".join([inst_dir, "B",inst_id,".bdd"])
bdd_A = exact.BDD(); bdd_A.load(fnameA)
bdd_B = exact.BDD(); bdd_B.load(fnameB)
######################################################
## The simplified problem
vs_A = simpl.VarSeq(bdd_A.vars, [len(l) for l in bdd_A.layers[:-1]])
vs_B = simpl.VarSeq(bdd_B.vars, [len(l) for l in bdd_B.layers[:-1]])
# find opts for varseq instance with BB-search
t0 = time()
b = bb.BBSearch(vs_A,vs_B)
status = b.search()
log(inst_id,"simpl_opt_status",1-int(status=="optimal"),outfile=logf, comment=status)
simpl_obj = b.Ap_cand.size() + b.Bp_cand.size()
t1 = time()
simpl_time = t1 - t0
log(inst_id, "simpl_BB_time",simpl_time,outfile=logf)
log(inst_id, "simpl_BB_obj",simpl_obj,outfile=logf)
# testing heuristics for the simplified problem
## simple ones: toA, toB, toRandom
v = []; s = []; t=[]
for heuristic in heu.SIMPL_HEU:
t0 = time()
sh,vh = heuristic[1](vs_A,vs_B)
t1 = time()
th = t1-t0
log(inst_id, heuristic[0]+"_time",th,outfile=logf)
log(inst_id, heuristic[0]+"_obj",sh,outfile=logf)
v.append(vh); s.append(sh); t.append(th)
simpl_results = dict(zip([c[0] for c in heu.SIMPL_HEU], [s,t,v]))
simpl_results.update({"simpl_BB":[b.Ap_cand.size()+b.Bp_cand.size(), simpl_time, b.Ap_cand.layer_var]})
######################################################
# The original problem
t0 = time()
o = b.Ap_cand.layer_var # optimal order found by the BBSearch
bdd_Aa = bdd_A.align_to(o)
bdd_Ba = bdd_B.align_to(o)
oo_simpl_order = bdd_Aa.size() + bdd_Ba.size()
for heuristic in heu.ORIG_HEU:
t0 = time()
s,t_add,v = heuristic[1](bdd_A,bdd_B,simpl_results)
t1 = time()
log(inst_id, heuristic[0]+"_time",t_add+(t1-t0),outfile=logf)
log(inst_id, heuristic[0]+"_obj",s,outfile=logf)
if __name__ == "__main__":
main()