#!/usr/bin/perl

use strict;
use FileHandle;
use Getopt::Mixed;

use vars qw ($opt_sequenced $opt_numeric $opt_simple $opt_constraints $opt_preferences $opt_derived $opt_bounded $opt_fixed $opt_time $opt_soft $opt_exponential $opt_weight $opt_range $opt_seed $opt_n $opt_skip $opt_cp $opt_sat $opt_cut $opt_zinc $opt_comment $opt_info $opt_ipc);

Getopt::Mixed::getOptions("sequenced numeric simple constraints preferences derived bounded=s fixed time soft exponential weight=s range=s seed=s n=s skip=s cp sat cut zinc comment info ipc=s");
my $infilename = shift;

# random number generator (linear congruential)
my $rng_seed = 100000000;
if (defined $opt_seed) {
    $rng_seed = $opt_seed;
}

sub random {
    # x = ((a * x) + b) % mod;
    $rng_seed = ((23 * $rng_seed) % 100000001);
    return $rng_seed;
}

my $i = random();
print "Random number 1: $i\n";
$i = random();
print "Random number 2: $i\n";
$i = random();
print "Random number 3: $i\n";

# extract infile basename
my $basename;
$_ = $infilename;
while (/([^\/]*\/)(.+)/) {
    $_ = $2;
}
if (/([^\.]+)\.(.*)/) {
    $basename = $1;
}
else {
    $basename = $_;
}

print STDERR "reading file: $infilename (basename = \"$basename\")\n";

my $mode = 0;
my $problem_name;
my $products = 0;
my $orders = 0;
my %includes = ();
my $current_order = 0;
my $line_count = 0;
my $problem_count = 0;

open FILE, "<$infilename" or die "could not open file $infilename: $!\n";
while (<FILE>) {
    $line_count = $line_count + 1;
    # print STDERR "[$mode] line $line_count\n";

    if ($mode == 0) {
	if (/[:alpha:].*/) {
	    $problem_count = ($problem_count + 1);
	    print STDERR "[$mode] start of problem $_";
	    $problem_name = "$basename $problem_count: $_";
	    $mode = 1;
	}
	elsif (/([0-9]+) ([0-9]+)/) {
	    $problem_count = ($problem_count + 1);
	    print STDERR "[$mode] $1 orders, $2 products\n";
	    $problem_name = "$basename $problem_count\n";
	    $orders = $1;
	    $current_order = 1;
	    $products = $2;
	    $mode = 2;
	}
    }
    elsif ($mode == 1) {
	if (/([0-9]+) ([0-9]+)/) {
	    print STDERR "[$mode] $1 orders, $2 products\n";
	    $orders = $1;
	    $current_order = 1;
	    $products = $2;
	    $mode = 2;
	}
	else {
	    print STDERR "[$mode] ERROR (line $line_count): dimension not found\n";
	    $mode = 0;
	}
    }
    elsif ($mode == 2) {
	# print STDERR "[$mode] order $current_order is \"$_\"\n";
	my $current_product = 1;
	while (/[:blank:]*(1|0)(.*)/) {
	    if ($1 == "1") {
		# print STDERR "order $current_order includes product $current_product\n";
		$includes{$current_order,$current_product} = 1;
	    }
	    else {
		# print STDERR "order $current_order does NOT include product $current_product\n";
		$includes{$current_order,$current_product} = 0;
	    }
	    $current_product = ($current_product + 1);
	    $_ = $2;
	}
	if ($current_product <= $products) {
	    print STDERR "[$mode] ERROR (line $line_count): only ($current_product - 1) bits found in order $current_order description\n";
	    $mode = 0;
	}
	$current_order = ($current_order + 1);
	if ($current_order > $orders) {
	    if (not (defined $opt_skip and ($problem_count <= $opt_skip))) {
		if (defined $opt_cp) {
		    write_constraint_program();
		}
		elsif (defined $opt_sat) {
		    write_CNF();
		}
		elsif (defined $opt_zinc) {
		    write_zinc();
		}
		elsif (defined $opt_cut) {
		    write_cut();
		}
		elsif (defined $opt_info) {
		    write_info();
		}
		else {
		    write_problem();
		}

		if (defined $opt_n) {
		    if (defined $opt_skip) {
			if ($problem_count >= ($opt_skip + $opt_n)) {
			    exit 0;
			}
		    }
		    elsif ($problem_count >= $opt_n) {
			exit 0;
		    }
		}
	    }
	    $mode = 0;
	}
    }
}

sub write_problem {
    my $filename;
    my $problemname;
    my $problem_type = "";
    my $problem_limits;
    my $problem_params = "";
    my $is_strips = 1;

    my $max = $orders;
    if (defined $opt_bounded) {
	$max = $opt_bounded;
    }

    if (defined $opt_soft) {
	$problem_type = ($problem_type . "soft");
	$is_strips = 0;
    }
    if (defined $opt_numeric) {
	if (defined $opt_simple) {
	    $problem_type = ($problem_type . "simplenumeric");
	}
	else {
	    $problem_type = ($problem_type . "numeric");
	}
	$is_strips = 0;
    }
    if (defined $opt_preferences) {
	$problem_type = ($problem_type . "preferences");
	$is_strips = 0;
	if (defined $opt_derived) {
	    $problem_type = ($problem_type . "derived");
	}
    }
    if (defined $opt_constraints) {
	$problem_type = ($problem_type . "constraints");
	$is_strips = 0;
    }
    if (defined $opt_time) {
	if (defined $opt_numeric) {
	    $problem_type = "complex";
	}
	else {
	    $problem_type = ($problem_type . "time");
	    $is_strips = 0;
	}
    }
    if ($is_strips) {
	if (defined $opt_sequenced) {
	    $problem_type = "sequencedstrips";
	}
	else {
	    $problem_type = "strips";
	}
    }
    $problem_params = "_"
	unless (not defined $opt_range and not defined $opt_seed);
    if (defined $opt_range) {
	$problem_params = ($problem_params . "r$opt_range");
    }
    if (defined $opt_seed) {
	$problem_params = ($problem_params . "s$opt_seed");
    }
    if (defined $opt_fixed) {
	if (defined $opt_bounded) {
	    $problem_limits = "fixed$opt_bounded";
	}
	else {
	    $problem_limits = "fixed";
	}
    }
    elsif (defined $opt_bounded) {
	$problem_limits = "max$opt_bounded";
    }

    # figure out filename
    if (defined $opt_ipc) {
	if (length($opt_ipc) < 2) {
	    $filename = "p0$opt_ipc.pddl";
	}
	else {
	    $filename = "p$opt_ipc.pddl";
	}
	$opt_ipc = ($opt_ipc + 1);
    }
    elsif (defined $problem_limits) {
	$filename = "os\_$problem_type\_$basename\_$problem_count\_$problem_limits$problem_params.pddl";
    }
    else {
	$filename = "os\_$problem_type\_$basename\_$problem_count$problem_params.pddl";
    }

    # figure out problem name
    if (defined $problem_limits) {
	$problemname = "os-$problem_type-$basename-$problem_count-$problem_limits";
    }
    else {
	$problemname = "os-$problem_type-$basename-$problem_count";
    }
    print STDERR "writing problem $problem_count to $filename...\n";

    my $file_handle;
    open ($file_handle, ">:crlf", $filename);

    # preamble
    print $file_handle ";; problem $problem_name";
    my $nec = ($orders * 2) + $products;
    print $file_handle ";; $orders orders, $products products (max open stacks = \#actions - $nec)\n";
    print $file_handle "(define (problem $problemname)\n";
    print $file_handle "  (:domain openstacks-$problem_type)\n";

    # object decls
    print $file_handle "  (:objects";
    unless (defined $opt_numeric or defined $opt_derived) {
	foreach my $i (0 .. $max) { print $file_handle " n$i"; };
	print $file_handle " - count";
    }
    foreach my $i (1 .. $orders) { print $file_handle " o$i"; };
    print $file_handle " - order";
    foreach my $i (1 .. $products) { print $file_handle " p$i"; };
    print $file_handle " - product)\n";  # end :objects

    # init spec
    print $file_handle "  (:init";
    if (defined $opt_sequenced) {
	print $file_handle " (machine-available)";
    }
    unless (defined $opt_numeric or defined $opt_derived) {
	foreach my $i (1 .. $max) {
	    my $j = $i - 1;
	    print $file_handle " (next-count n$j n$i)";
	}
	if (defined $opt_preferences) {
	    print $file_handle " (stacks-in-use n0)";
	}
	else {
	    if (defined $opt_fixed) {
		print $file_handle " (stacks-avail n$max)";
	    }
	    else {
		print $file_handle " (stacks-avail n0)";
	    }
	}
    }
    foreach my $i (1 .. $orders) {
	print $file_handle " (waiting o$i)";
	unless (defined $opt_constraints) {
	    for my $j (1 .. $products) {
		if ($includes{$i,$j}) {
		    print $file_handle " (includes o$i p$j)";
		}
	    }
	}
    }
    if (defined $opt_time) {
	my $r = 10;
	if (defined $opt_range) {
	    $r = $opt_range;
	}
	foreach my $i (1 .. $products) {
	    my $t = ((random() % $r) + 1) * $orders;
	    print $file_handle " (= (make-time p$i) $t)";
	}
    }
    if (defined $opt_numeric) {
	if (defined $opt_simple and not defined $opt_preferences) {
	    print $file_handle " (= (stacks-avail) 0)";
	}
	else {
	    print $file_handle " (= (stacks-in-use) 0)";
	}
	unless (defined $opt_simple) {
	    print $file_handle " (= (max-in-use) 0)";
	}
    }
    print $file_handle ")\n";  # end :init

    # goal spec
    print $file_handle "  (:goal (and";
    foreach my $i (1 .. $orders) {
	print $file_handle " (shipped o$i)";
    }
    my $sum = 0;
    if (defined $opt_soft) {
	if (defined $opt_exponential) {
	    for my $i (1 .. $orders) {
		my @p = order_product_list($i);
		my $v = 1;
		for my $n (0 .. $#p) {
		    my $n1 = $n + 1;
		    if ($n1 == 1) {
			print $file_handle " (preference d\-o$i\-n$n1 (delivered o$i p$p[0]))";
		    }
		    else {
			print $file_handle " (preference d\-o$i\-n$n1 (and";
			for my $j (0 .. $n) {
			    print $file_handle " (delivered o$i p$p[$j])";
			}
			print $file_handle "))";
		    }
		    my $new_v = $v * 2;
		    $sum = ($sum + ($new_v - $v));
		    $v = $new_v;
		}
	    }
	}
	else {
	    for my $i (1 .. $orders) {
		for my $j (1 .. $products) {
		    if ($includes{$i,$j}) {
			print $file_handle " (preference d\-o$i\-p$j (delivered o$i p$j))";
			$sum = ($sum + 1);
		    }
		}
	    }
	}
    }
    print $file_handle "))\n";  # end :goal
    if (defined $opt_soft) {
	print $file_handle "  ;; max value = $sum\n";
    }

    # constraint spec
    if (defined $opt_constraints or defined $opt_preferences) {
	print $file_handle "  (:constraints (and";
	if (defined $opt_preferences) {
	    if (defined $opt_derived) {
		for my $i (1 .. $max) {
		    print $file_handle " (preference max$i (always (not (orders-open-$i))))";
		}
	    }
	    elsif (defined $opt_numeric) {
		for my $i (1 .. $orders) {
		    print $file_handle " (preference max$i (always (< (stacks-in-use) $i)))";
		}
	    }
	    else {
		for my $i (1 .. $max) {
		    print $file_handle " (preference max$i (always (not (stacks-in-use n$i))))";
		}
	    }
	}
	if (defined $opt_constraints) {
	    for my $i (1 .. $orders) {
		for my $j (1 .. $products) {
		    if ($includes{$i,$j}) {
			print $file_handle " (sometime-before (made p$j) (started o$i))";
			print $file_handle " (sometime-before (shipped o$i) (made p$j))";
		    }
		}
	    }
	}
	print $file_handle "))\n";  # end :constraints
    }

    if (defined $opt_soft) {
	print $file_handle "  (:metric maximize ";
	if (defined $opt_preferences) {
	    print $file_handle "(- ";
	}

	if (defined $opt_exponential) {
	    for my $i (1 .. $orders - 1) {
		my @p = order_product_list($i);
		my $v = 1;
		print $file_handle "(+ ";
		for my $n (0 .. $#p - 1) {
		    my $n1 = $n + 1;
		    my $new_v = 2 * $v;
		    my $this_v = $new_v - $v;
		    $v = $new_v;
		    print $file_handle "(+ (* $this_v (- 1 (is-violated d\-o$i\-n$n1))) ";
		}
		my $n1 = $#p + 1;
		my $new_v = 2 * $v;
		my $this_v = $new_v - $v;
		print $file_handle "(* $this_v (- 1 (is-violated d\-o$i\-n$n1)))";
		for my $j (0 .. $#p - 1) {
		    print $file_handle ")";
		}
	    }
	    # last order
	    my @p = order_product_list($orders);
	    my $v = 1;
	    for my $n (0 .. $#p - 1) {
		my $n1 = $n + 1;
		my $new_v = 2 * $v;
		my $this_v = $new_v - $v;
		$v = $new_v;
		print $file_handle "(+ (* $this_v (- 1 (is-violated d\-o$orders\-n$n1))) ";
	    }
	    my $n1 = $#p + 1;
	    my $new_v = 2 * $v;
	    my $this_v = $new_v - $v;
	    print $file_handle "(* $this_v (- 1 (is-violated d\-o$orders\-n$n1)))";
	    for my $j (0 .. $#p - 1) {
		print $file_handle ")";
	    }
	    for my $i (1 .. $orders - 1) {
		print $file_handle ")";
	    }
	}
	else {
	    for my $i (1 .. $orders - 1) {
		my @p = order_product_list($i);
		print $file_handle "(+ ";
		for my $j (0 .. $#p - 1) {
		    print $file_handle "(+ (- 1 (is-violated d\-o$i\-p$p[$j])) ";
		}
		print $file_handle "(- 1 (is-violated d\-o$i\-p$p[$#p]))";
		for my $j (0 .. $#p - 1) {
		    print $file_handle ")";
		}
	    }
	    # last order
	    my @p = order_product_list($orders);
	    for my $j (0 .. $#p - 1) {
		print $file_handle "(+ (- 1 (is-violated d\-o$orders\-p$p[$j]))";
	    }
	    print $file_handle "(- 1 (is-violated d\-o$orders\-p$p[$#p]))";
	    for my $j (0 .. $#p - 1) {
		print $file_handle ")";
	    }
	    for my $i (1 .. $orders - 1) {
		print $file_handle ")";
	    }
	}

	if (defined $opt_preferences) {
	    for my $i (1 .. $max - 1) {
		if (defined $opt_weight) {
		    print $file_handle "(+ (* $opt_weight (is-violated max$i))";
		}
		else {
		    print $file_handle "(+ (is-violated max$i)";
		}
	    }
	    if (defined $opt_weight) {
		print $file_handle "(* $opt_weight (is-violated max$max))";
	    }
	    else {
		print $file_handle "(is-violated max$max)";
	    }
	    for my $i (1 .. $max - 1) {
		print $file_handle ")";
	    }
	    print $file_handle ")";
	}

	print $file_handle ")\n";
    }
    elsif (defined $opt_preferences) {
	print $file_handle "  (:metric minimize ";
	for my $i (1 .. $max - 1) {
	    if (defined $opt_weight) {
		print $file_handle "(+ (* $opt_weight (is-violated max$i))";
	    }
	    else {
		print $file_handle "(+ (is-violated max$i)";
	    }
	}
	if (defined $opt_weight) {
	    print $file_handle "(* $opt_weight (is-violated max$max))";
	}
	else {
	    print $file_handle "(is-violated max$max)";
	}
	for my $i (1 .. $max - 1) {
	    print $file_handle ")";
	}
	print $file_handle ")\n";
    }
    elsif (defined $opt_numeric and not defined $opt_simple) {
	if (defined $opt_time) {
	    if (defined $opt_weight) {
		print $file_handle "  (:metric minimize (+ (* $opt_weight (max-in-use)) (total-time)))\n";
	    }
	    else {
		print $file_handle "  (:metric minimize (+ (max-in-use) (total-time)))\n";
	    }
	}
	else {
	    print $file_handle "  (:metric minimize (max-in-use))\n";
	}
    }
    elsif (defined $opt_time) {
	print $file_handle "  (:metric minimize (total-time))\n";
    }

    print $file_handle ")\n";  # end (define (problem ...))
    close $file_handle;
}

sub order_product_list {
    my $which_order = shift;
    my @l = ();
    for my $i (1 .. $products) {
	if ($includes{$which_order,$i}) {
	    @l = (@l, $i);
	}
    }
    # print STDERR "order $which_order product list: @l (length = $#l)\n";
    return @l;
}

sub count_products_in_order {
    my $which_order = shift;
    my $n = 0;
    for my $i (1 .. $products) {
	if ($includes{$which_order,$i}) {
	    $n = ($n + 1);
	}
    }
    # print STDERR "order $which_order product list: @l (length = $#l)\n";
    return $n;
}

sub write_constraint_program {
    my $filename;
    my $problem_limits;

    my $max = $orders;
    if (defined $opt_bounded) {
	$max = $opt_bounded;
    }

    if (defined $opt_bounded) {
	$problem_limits = "max$opt_bounded";
    }
    if (defined $problem_limits) {
	$filename = "solve\_$basename\_$problem_count\_$problem_limits.ecl";
    }
    else {
	$filename = "solve\_$basename\_$problem_count.ecl";
    }
    print STDERR "writing problem $problem_count to $filename...\n";

    my $file_handle;
    open ($file_handle, ">:crlf", $filename);

    # library import
    print $file_handle ":- lib(ic).\n\n";

    # define the setup procedure
    print $file_handle "setup(";
    foreach my $i (1 .. $products) {
	if ($i > 1) { print $file_handle ","; }
	print $file_handle "P$i";
    }
    print $file_handle ",NMAX) :-\n";

    # basic constraints on Pi variables
    foreach my $i (1 .. $products) {
	print $file_handle "\tP$i :: 1 .. $products,\n";
    }
    print $file_handle "\talldifferent([";
    foreach my $i (1 .. $products) {
	if ($i > 1) { print $file_handle ","; }
	print $file_handle "P$i";
    }
    print $file_handle "]),\n";

    # define Fi variables
    foreach my $i (1 .. $orders) {
	my @p = order_product_list($i);
	print $file_handle "\tminlist([";
	for my $j (0 .. $#p - 1) {
	    print $file_handle "P$p[$j],";
	}
	print $file_handle "P$p[$#p]],F$i),\n";
    }

    # define Li variables
    foreach my $i (1 .. $orders) {
	my @p = order_product_list($i);
	print $file_handle "\tmaxlist([";
	for my $j (0 .. $#p - 1) {
	    print $file_handle "P$p[$j],";
	}
	print $file_handle "P$p[$#p]],L$i),\n";
    }

    # define Oij variables
    foreach my $i (1 .. $orders) {
	foreach my $j (1 .. $products) {
	    print $file_handle "\tO$i\_$j \#= (F$i \#=< $j and L$i \#>= $j),\n";
	}
    }

    # define Ni variables
    foreach my $i (1 .. $products) {
	print $file_handle "\tN$i \#= ";
	foreach my $j (1 .. $orders - 1) {
	    print $file_handle "O$j\_$i +";
	}
	print $file_handle "O$orders\_$i,\n";
    }

    # constrain NMAX
    print $file_handle "\tmaxlist([";
    foreach my $i (1 .. $products) {
	if ($i > 1) { print $file_handle ","; }
	print $file_handle "N$i";
    }
    print $file_handle "],NMAX).\n\n";

    # define a bounded solve procedure
    print $file_handle "solve_with_bound(B) :-\n";
    print $file_handle "\tsetup(";
    foreach my $i (1 .. $products) {
	if ($i > 1) { print $file_handle ","; }
	print $file_handle "P$i";
    }
    print $file_handle ",NMAX),\n";
    print $file_handle "\tNMAX \#=< B,\n";
    print $file_handle "\tlabeling([";
    foreach my $i (1 .. $products) {
	if ($i > 1) { print $file_handle ","; }
	print $file_handle "P$i";
    }
    print $file_handle ",NMAX]),\n";
    print $file_handle "\tprintf(\"schedule: \%w, max \#open: \%u\%n\",[[";
    foreach my $i (1 .. $products) {
	if ($i > 1) { print $file_handle ","; }
	print $file_handle "P$i";
    }
    print $file_handle "],NMAX]).\n";

    # main call

#     print $file_handle ":- setup(";
#     foreach my $i (1 .. $products) {
# 	if ($i > 1) { print $file_handle ","; }
# 	print $file_handle "P$i";
#     }
#     print $file_handle ",NMAX),\n";
#     if (defined $opt_bounded) {
# 	print $file_handle "   NMAX \#=< $opt_bounded,\n";
#     }
#     print $file_handle "   labeling([";
#     foreach my $i (1 .. $products) {
# 	if ($i > 1) { print $file_handle ","; }
# 	print $file_handle "P$i";
#     }
#     print $file_handle ",NMAX]),\n";
#     print $file_handle "   printf(\"schedule: \%w, max \#open: \%u\%n\",[[";
#     foreach my $i (1 .. $products) {
# 	if ($i > 1) { print $file_handle ","; }
# 	print $file_handle "P$i";
#     }
#     print $file_handle "],NMAX]).\n";

    close $file_handle;
}

sub write_CNF {
    my $filename;
    my $problem_limits;

    my $max = $orders;
    if (defined $opt_bounded) {
	$max = $opt_bounded;
    }

    if (defined $opt_bounded) {
	$problem_limits = "max$opt_bounded";
    }
    if (defined $problem_limits) {
	$filename = "test\_$basename\_$problem_count\_$problem_limits.cnf";
    }
    else {
	$filename = "test\_$basename\_$problem_count.cnf";
    }
    print STDERR "writing problem $problem_count to $filename...\n";

    my $file_handle;
    open ($file_handle, ">:crlf", $filename);

    # comments before "p"-line seem to be acceptable to more solvers
    print $file_handle "c problem $basename\_$problem_count with bound $max\n";

    my $n_points = ((2 * $orders) + $products);

    my $at_prec = ($n_points * $n_points);
    my $n_per_map = ($orders * $max);
    my $at_map = ($products * $n_per_map);

    my $cl_tc = ($n_points * ($n_points - 1) * ($n_points - 2));
    my $cl_to = ($n_points * ($n_points - 1));
    my $cl_ac = (($n_points * ($n_points - 1)) + $n_points);
    my $cl_ospec = $orders;
    for my $i (1 .. $orders) {
	my @p = order_product_list($i);
	$cl_ospec = ($cl_ospec + (2 * ($#p + 1)));
    }
    my $cl_map = ($products * $orders);
    my $cl_map_inj = ($products * (($orders * ($orders - 1)) / 2) * $max);
    my $cl_map_can = ($products * (($orders * ($orders - 1)) / 2) * (($max * ($max - 1)) / 2));

    my $n_atoms = $at_prec + $at_map;
    my $n_clauses = $cl_tc + $cl_ac + $cl_ospec + $cl_map + $cl_map_inj + $cl_map_can;

    print $file_handle "p cnf $n_atoms $n_clauses\n";

    if (defined $opt_comment) {
	print $file_handle "c transitivity of precedence ($cl_tc clauses):\n";
    }
    for my $i (1 .. $n_points) {
	for my $j (1 .. $n_points) {
	    for my $k (1 .. $n_points) {
		if ((not $i == $j) and (not $i == $k) and (not $j == $k)) {
		    if (defined $opt_comment) {
			print $file_handle "c ($i < $j) & ($j < $k) -> ($i < $k)\n";
		    }
		    my $i_prec_j = (($i - 1) * $n_points) + $j;
		    my $j_prec_k = (($j - 1) * $n_points) + $k;
		    my $i_prec_k = (($i - 1) * $n_points) + $k;
		    print $file_handle "-$i_prec_j -$j_prec_k $i_prec_k 0\n";
		}
	    }
	}
    }

    if (defined $opt_comment) {
	print $file_handle "c acyclicity of precedence ($cl_ac clauses):\n";
    }
    for my $i (1 .. $n_points) {
	for my $j (1 .. $n_points) {
	    if (not $i == $j) {
		if (defined $opt_comment) {
		    print $file_handle "c ($i < $j)  -> !($j < $i)\n";
		}
		my $i_prec_j = (($i - 1) * $n_points) + $j;
		my $j_prec_i = (($j - 1) * $n_points) + $i;
		print $file_handle "-$i_prec_j -$j_prec_i 0\n";
	    }
	}
    }

    if (defined $opt_comment) {
	print $file_handle "c irreflexivity of precedence:\n";
    }
    for my $i (1 .. $n_points) {
	if (defined $opt_comment) {
	    print $file_handle "c !($i < $i)\n";
	}
	my $i_prec_i = (($i - 1) * $n_points) + $i;
	print $file_handle "-$i_prec_i 0\n";
    }

    if (defined $opt_comment) {
	print $file_handle "c totality of precedence ($cl_to clauses):\n";
    }
    for my $i (1 .. $n_points) {
	for my $j (1 .. $n_points) {
	    if (not $i == $j) {
		if (defined $opt_comment) {
		    print $file_handle "c ($i < $j)  V ($j < $i)\n";
		}
		my $i_prec_j = (($i - 1) * $n_points) + $j;
		my $j_prec_i = (($j - 1) * $n_points) + $i;
		print $file_handle "$i_prec_j $j_prec_i 0\n";
	    }
	}
    }

    if (defined $opt_comment) {
	print $file_handle "c order specification ($cl_ospec clauses):\n";
    }
    for my $i (1 .. $orders) {
	my $start_i = $i;
	my $end_i = $orders + $i;
	my $start_prec_end = (($start_i - 1) * $n_points) + $end_i;
	if (defined $opt_comment) {
	    print $file_handle "c start[$i] < end[$i] ($start_i < $end_i)\n";
	}
	print $file_handle "$start_prec_end 0\n";
	my @p = order_product_list($i);
	for my $j (0 .. $#p) {
	    my $make_pj = ((2 * $orders) + $p[$j]);
	    my $start_prec_make = (($start_i - 1) * $n_points) + $make_pj;
	    my $make_prec_end = (($make_pj - 1) * $n_points) + $end_i;
	    if (defined $opt_comment) {
		print $file_handle "c start[$i] < make[$p[$j]] ($start_i < $make_pj)\n";
	    }
	    print $file_handle "$start_prec_make 0\n";
	    if (defined $opt_comment) {
		print $file_handle "c make[$p[$j]] < end[$i] ($make_pj < $end_i)\n";
	    }
	    print $file_handle "$make_prec_end 0\n";
	}
    }

    if (defined $opt_comment) {
	print $file_handle "c mapping ($cl_map clauses):\n";
    }
    for my $i (1 .. $products) {
	my $make_i = ((2 * $orders) + $i);
	for my $j (1 .. $orders) {
	    my $start_j = $j;
	    my $end_j = $orders + $j;
	    my $start_prec_make = (($start_j - 1) * $n_points) + $make_i;
	    my $make_prec_end = (($make_i - 1) * $n_points) + $end_j;
	    my $map_at_i = ($at_prec + (($i - 1) * $n_per_map));
	    if (defined $opt_comment) {
		my $first_map = ($map_at_i + (($j - 1) * $max) + 1);
		my $last_map = ($map_at_i + (($j - 1) * $max) + $max);
		print $file_handle "c start[$j] < make[$i] & make[$i] < end[$j] -> map[$j] to 1..$max at $i (($start_j < $make_i) & ($make_i < $end_j) -> ($first_map .. $last_map)\n";
	    }
	    print $file_handle "-$start_prec_make -$make_prec_end";
	    for my $k (1 .. $max) {
		my $map_j_to_k = (($j - 1) * $max) + $k;
		my $map_j_to_k_at_i = ($map_at_i + $map_j_to_k);
		print $file_handle " $map_j_to_k_at_i";
	    }
	    print $file_handle " 0\n";
	}
    }

    if (defined $opt_comment) {
	print $file_handle "c injectivity of mapping ($cl_map_inj clauses):\n";
    }
    for my $i (1 .. $products) {
	my $make_i = ((2 * $orders) + $i);
	for my $j (1 .. $orders) {
	    for my $j2 (($j + 1) .. $orders) {
		for my $k (1 .. $max) {
		    my $map_j_to_k = (($j - 1) * $max) + $k;
		    my $map_j2_to_k = (($j2 - 1) * $max) + $k;
		    my $map_at_i = ($at_prec + (($i - 1) * $n_per_map));
		    my $map_j_to_k_at_i = ($map_at_i + $map_j_to_k);
		    my $map_j2_to_k_at_i = ($map_at_i + $map_j2_to_k);
		    if (defined $opt_comment) {
			print $file_handle "c map[$j] = $k -> !map[$j2] = $k at $i\n";
		    }
		    print $file_handle "-$map_j_to_k_at_i -$map_j2_to_k_at_i 0\n";
		}
	    }
	}
    }

    if (defined $opt_comment) {
	print $file_handle "c canonicity of mapping ($cl_map_can clauses):\n";
    }
    for my $i (1 .. $products) {
	my $map_at_i = ($at_prec + (($i - 1) * $n_per_map));
	for my $j (1 .. $orders) {
	    for my $k (1 .. $max) {
		for my $j2 ($j + 1 .. $orders) {
		    for my $k2 ($k + 1 .. $max) {
			my $map_j2_to_k = (($j2 - 1) * $max) + $k;
			my $map_j_to_k2 = (($j - 1) * $max) + $k2;
			my $map_j2_to_k_at_i = ($map_at_i + $map_j2_to_k);
			my $map_j_to_k2_at_i = ($map_at_i + $map_j_to_k2);
			if (defined $opt_comment) {
			    print $file_handle "c map[$j2] = $k -> !map[$j] = $k2 at $i\n";
			}
			print $file_handle "-$map_j2_to_k_at_i -$map_j_to_k2_at_i 0\n";
		    }
		}
	    }
	}
    }

    close $file_handle;

    write_translation();
}

sub write_translation {
    my $filename;
    my $problem_limits;

    my $max = $orders;
    if (defined $opt_bounded) {
	$max = $opt_bounded;
    }

    if (defined $opt_bounded) {
	$problem_limits = "max$opt_bounded";
    }
    if (defined $problem_limits) {
	$filename = "restore\_$basename\_$problem_count\_$problem_limits.sed";
    }
    else {
	$filename = "restore\_$basename\_$problem_count.sed";
    }
    print STDERR "writing solution translator for $basename $problem_count to $filename...\n";

    my $file_handle;
    open ($file_handle, ">:crlf", $filename);

    my $n_points = ((2 * $orders) + $products);

    my $at_prec = ($n_points * $n_points);
    my $n_per_map = ($orders * $max);
    my $at_map = ($products * $n_per_map);

    for my $i (1 .. $orders) {
	my $start_i = $i;
	my $end_i = $orders + $i;

	my $start_i_prec_end_i = (($start_i - 1) * $n_points) + $end_i;
	my $end_i_prec_start_i = (($end_i - 1) * $n_points) + $start_i;
	print $file_handle "s/^$start_i_prec_end_i\$/($start_i_prec_end_i) start[$i] < end[$i]/g\n";
	print $file_handle "s/^-$start_i_prec_end_i\$/(-$start_i_prec_end_i) not start[$i] < end[$i]/g\n";
	print $file_handle "s/^$end_i_prec_start_i\$/($end_i_prec_start_i) end[$i] < start[$i]/g\n";
	print $file_handle "s/^-$end_i_prec_start_i\$/(-$end_i_prec_start_i) not end[$i] < start[$i]/g\n";

	for my $j (1 .. $orders) {
	    if (not $i == $j) {
		my $start_j = $j;
		my $end_j = $orders + $j;

		my $start_i_prec_end_j = (($start_i - 1) * $n_points) + $end_j;
		my $start_j_prec_end_i = (($start_j - 1) * $n_points) + $end_i;

		print $file_handle "s/^$start_i_prec_end_j\$/($start_i_prec_end_j) start[$i] < end[$j]/g\n";
		print $file_handle "s/^-$start_i_prec_end_j\$/(-$start_i_prec_end_j) not start[$i] < end[$j]/g\n";
		print $file_handle "s/^$start_j_prec_end_i\$/($start_j_prec_end_i) start[$j] < end[$i]/g\n";
		print $file_handle "s/^-$start_j_prec_end_i\$/(-$start_j_prec_end_i) not start[$j] < end[$i]/g\n";

		my $end_i_prec_start_j = (($end_i - 1) * $n_points) + $start_j;
		my $end_j_prec_start_i = (($end_j - 1) * $n_points) + $start_i;

		print $file_handle "s/^$end_i_prec_start_j\$/($end_i_prec_start_j) end[$i] < start[$j]/g\n";
		print $file_handle "s/^-$end_i_prec_start_j\$/(-$end_i_prec_start_j) not end[$i] < start[$j]/g\n";
		print $file_handle "s/^$end_j_prec_start_i\$/($end_j_prec_start_i) end[$j] < start[$i]/g\n";
		print $file_handle "s/^-$end_j_prec_start_i\$/(-$end_j_prec_start_i) not end[$j] < start[$i]/g\n";

		my $start_i_prec_start_j = (($start_i - 1) * $n_points) + $start_j;
		my $start_j_prec_start_i = (($start_j - 1) * $n_points) + $start_i;
		print $file_handle "s/^$start_i_prec_start_j\$/($start_i_prec_start_j) start[$i] < start[$j]/g\n";
		print $file_handle "s/^-$start_i_prec_start_j\$/(-$start_i_prec_start_j) not start[$i] < start[$j]/g\n";
		print $file_handle "s/^$start_j_prec_start_i\$/($start_j_prec_start_i) start[$j] < start[$i]/g\n";
		print $file_handle "s/^-$start_j_prec_start_i\$/(-$start_j_prec_start_i) not start[$j] < start[$i]/g\n";

		my $end_i_prec_end_j = (($end_i - 1) * $n_points) + $end_j;
		my $end_j_prec_end_i = (($end_j - 1) * $n_points) + $end_i;
		print $file_handle "s/^$end_i_prec_end_j\$/($end_i_prec_end_j) end[$i] < end[$j]/g\n";
		print $file_handle "s/^-$end_i_prec_end_j\$/(-$end_i_prec_end_j) not end[$i] < end[$j]/g\n";
		print $file_handle "s/^$end_j_prec_end_i\$/($end_j_prec_end_i) end[$j] < end[$i]/g\n";
		print $file_handle "s/^-$end_j_prec_end_i\$/(-$end_j_prec_end_i) not end[$j] < end[$i]/g\n";
	    }
	}

	for my $j (1 .. $products) {
	    my $make_j = ((2 * $orders) + $j);
	    my $start_i_prec_make_j = (($start_i - 1) * $n_points) + $make_j;
	    my $end_i_prec_make_j = (($end_i - 1) * $n_points) + $make_j;
	    my $make_j_prec_start_i = (($make_j - 1) * $n_points) + $start_i;
	    my $make_j_prec_end_i = (($make_j - 1) * $n_points) + $end_i;

	    print $file_handle "s/^$start_i_prec_make_j\$/($start_i_prec_make_j) start[$i] < make[$j]/g\n";
	    print $file_handle "s/^-$start_i_prec_make_j\$/(-$start_i_prec_make_j) not start[$i] < make[$j]/g\n";
	    print $file_handle "s/^$end_i_prec_make_j\$/($end_i_prec_make_j) end[$i] < make[$j]/g\n";
	    print $file_handle "s/^-$end_i_prec_make_j\$/(-$end_i_prec_make_j) not end[$i] < make[$j]/g\n";
	    print $file_handle "s/^$make_j_prec_start_i\$/($make_j_prec_start_i) make[$j] < start[$i]/g\n";
	    print $file_handle "s/^-$make_j_prec_start_i\$/(-$make_j_prec_start_i) not make[$j] < start[$i]/g\n";
	    print $file_handle "s/^$make_j_prec_end_i\$/($make_j_prec_end_i) make[$j] < end[$i]/g\n";
	    print $file_handle "s/^-$make_j_prec_end_i\$/(-$make_j_prec_end_i) not make[$j] < end[$i]/g\n";
	}
    }

    for my $i (1 .. $products) {
	my $make_i = ((2 * $orders) + $i);
	for my $j (1 .. $products) {
	    my $make_j = ((2 * $orders) + $j);
	    my $make_i_prec_make_j = (($make_i - 1) * $n_points) + $make_j;
	    print $file_handle "s/^$make_i_prec_make_j\$/($make_i_prec_make_j) make[$i] < make[$j]/g\n";
	    print $file_handle "s/^-$make_i_prec_make_j\$/(-$make_i_prec_make_j) not make[$i] < make[$j]/g\n";
	}
    }

    for my $i (1 .. $products) {
	my $map_at_i = ($at_prec + (($i - 1) * $n_per_map));
	for my $j (1 .. $orders) {
	    for my $k (1 .. $max) {
		my $map_j_to_k = (($j - 1) * $max) + $k;
		my $map_j_to_k_at_i = ($map_at_i + $map_j_to_k);
		print $file_handle "s/^$map_j_to_k_at_i\$/($map_j_to_k_at_i) map[$j] = $k at $i/g\n";
		print $file_handle "s/^-$map_j_to_k_at_i\$/(-$map_j_to_k_at_i) not map[$j] = $k at $i/g\n";
	    }
	}
    }

    close $file_handle;
}

sub exponential_penalty_function {
    my $pos = shift;
    my $n = shift;

    my $sum = 0;
    my $v = 1;
    for my $k (1 .. $n) {
	if ($k >= $pos) {
	    $sum = ($sum + $v);
	}
	$v = ($v * 2);
    }
    return $sum;
}

sub write_cut {
    my $filename;

    if (defined $opt_ipc) {
	if (length($opt_ipc) < 2) {
	    $filename = "p0$opt_ipc.txt";
	}
	else {
	    $filename = "p$opt_ipc.txt";
	}
	$opt_ipc = ($opt_ipc + 1);
    }
    else {
	$filename = "$basename\_$problem_count.txt";
    }
    print STDERR "writing problem $problem_count to $filename...\n";

    my $file_handle;
    open ($file_handle, ">:crlf", $filename);

    print $file_handle "$orders $products\n";

    for my $i (1 .. $orders) {
	if (defined $opt_exponential) {
	    my $p = 1;
	    my $n = count_products_in_order($i);
	    for my $j (1 .. $products) {
		if ($includes{$i,$j}) {
		    my $c = exponential_penalty_function($p, $n);
		    print $file_handle " $c";
		    $p = ($p + 1);
		}
		else {
		    print $file_handle " 0";
		}
	    }
	}
	else {
	    for my $j (1 .. $products) {
		if ($includes{$i,$j}) {
		    print $file_handle " 1";
		}
		else {
		    print $file_handle " 0";
		}
	    }
	}
	print $file_handle "\n";
    }

    if (defined $opt_time) {
	my $r = 10;
	if (defined $opt_range) {
	    $r = $opt_range;
	}
	foreach my $i (1 .. $products) {
	    my $t = ((random() % $r) + 1) * $orders;
	    print $file_handle " $t";
	}
	print $file_handle "\n";
    }

    close $file_handle;
}

sub write_zinc {
    my $filename;

    $filename = "$basename\_$problem_count.zinc";
    print STDERR "writing problem $problem_count to $filename...\n";

    my $file_handle;
    open ($file_handle, ">:crlf", $filename);

    print $file_handle "include \"openstacks.zinc\";\n";
    print $file_handle "nProducts = $products;\n";
    print $file_handle "nOrders = $orders;\n";

    print $file_handle "contains = [";

    for my $i (1 .. $orders) {
	print $file_handle "[";
	for my $j (1 .. $products) {
	    if ($includes{$i,$j}) {
		print $file_handle "true";
	    }
	    else {
		print $file_handle "false";
	    }
	    if ($j < $products) {
		print $file_handle ",";
	    }
	}
	print $file_handle "]";
	if ($i < $orders) {
	    print $file_handle ",";
	}
	print $file_handle "\n";
    }
    print $file_handle "];";

    close $file_handle;
}

sub write_info {
    print STDOUT "problem $basename $problem_count:\n";
    print STDOUT "\#orders = $orders\n";
    print STDOUT "\#products = $products\n";

    my $reduced_products = 0;

    for my $j (1 .. $products) {
	my $use_count = 0;
	for my $i (1 .. $orders) {
	    if ($includes{$i,$j}) {
		$use_count = ($use_count + 1);
	    }
	}
	if ($use_count > 0) {
	    $reduced_products = ($reduced_products + 1);
	}
	else {
	    print STDOUT "product \#$j is not required by any order\n";
	}
    }

    print STDOUT "reduced \#products = $reduced_products\n";
}