bb.c

生成直角Steiner树的程序包

	}

	/* Print out the old and new lower and upper bounds, with timestamp. */
	t1 = get_cpu_time ();
	convert_cpu_time (t1 - bbip -> t0, buf1);

	if (bbip -> prevlb <= -DBL_MAX) {
		old_gap = 99.9;
		new_gap = 99.9;
	}
	else {
		old_gap = 100.0 * (prev - bbip -> prevlb) / prev;
		new_gap = 100.0 * (ub - bbip -> prevlb) / ub;
	}

	tracef (" %% @UO %s %24.20f %2.10f\n",
		buf1, UNSCALE (prev, sip), old_gap);
	tracef (" %% @UN %s %24.20f %2.10f\n",
		buf1, UNSCALE (ub, sip), new_gap);
}

/*
 * This routine deletes any existing node whose objective value is
 * cut off by the given latest feasible integer solution.
 */

	static
	void
cut_off_existing_nodes (

double		best_z,		/* IN - new best objective value */
struct bbtree *	tp		/* IN - branch-and-bound tree */
)
{
int		num_cut;
struct bbheap *	hp;
struct bbnode *	p;

	num_cut = 0;

	/* We process the nodes from WORST to best... */
	hp = &(tp -> heap [WORST_NODE_HEAP]);

	while (hp -> nheap > 0) {
		/* Get node with highest objective value... */
		p = hp -> array [0];
		if (p -> index [WORST_NODE_HEAP] NE 0) {
			fatal ("cut_off_existing_nodes: Bug 1.");
		}
		if (p -> z < best_z) {
			/* All remaining nodes are < best_z... */
			break;
		}

		/* This node has been cut off! */
		delete_node_from_bbtree (p, tp);
		p -> next = tp -> free;
		tp -> free = p;
		++num_cut;
	}

	if (num_cut > 0) {
		tracef (" %%	=== %d nodes cut off ===\n", num_cut);
	}
}

/*
 * This routine updates the node preemption value.  The node to be
 * preempted must be active when this routine is called (i.e., it must
 * be removed from the heap so that the "next best" node is at the top
 * of the heap).
 */

	static
	void
update_node_preempt_value (

struct bbinfo *		bbip		/* IN - branch-and-bound info */
)
{
struct bbtree *		tp;
struct bbheap *		hp;
struct bbnode *		node2;

	tp = bbip -> bbtree;
	hp = &(tp -> heap [BEST_NODE_HEAP]);

	if (hp -> nheap <= 0) {
		/* No other nodes.  Preempt only at cutoff. */
		bbip -> preempt_z = bbip -> best_z;
	}
	else {
		/* Preempt current node when next-best is exceeded. */
		node2 = hp -> array [0];
		bbip -> preempt_z = node2 -> z;
	}
}

/*
 * This routine performs most of the separations -- in the proper order.
 */

	static
	struct constraint *
do_separations (

struct bbinfo *		bbip,		/* IN - branch-and-bound info */
cpu_time_t **		Tpp		/* IN/OUT - CPU time vector */
)
{
double *		x;
bitmap_t *		vert_mask;
bitmap_t *		edge_mask;
struct cinfo *		cip;
struct comp *		comp;
struct comp *		p;
struct comp **		hookp;
struct comp *		p2;
cpu_time_t *		Tp;
struct constraint *	cp;
struct constraint *	cp2;
struct constraint *	tmp;
bool			print_flag;
bool			optimal;
bool			any_skipped;

	x		= bbip -> node -> x;
	vert_mask	= bbip -> tmap;
	edge_mask	= bbip -> fset_mask;
	cip		= bbip -> cip;

	Tp = *Tpp;

	/* Find all zero-weight cutsets... */
	cp = find_cutset_constraints (x, vert_mask, edge_mask, cip);
	*Tp++ = get_cpu_time ();

	/* Find solid integer cycles... */
	cp = find_integer_cycles (x, vert_mask, edge_mask, cp, cip);
	*Tp++ = get_cpu_time ();

	/* Break problem up into congested components... */
	print_flag = TRUE;
	comp = find_congested_components (x,
					  vert_mask,
					  edge_mask,
					  print_flag,
					  cip);

	/* Exhaustively enumerate all components that are sufficiently	*/
	/* small...  Delete them from the list when done.		*/
	hookp = &comp;
	while ((p = *hookp) NE NULL) {
		if (p -> num_verts <= SEC_ENUM_LIMIT) {
			cp2 = enumerate_all_subtours (p, NULL, bbip);
			*hookp = p -> next;
			p -> next = NULL;
			free_congested_component (p);
			while (cp2 NE NULL) {
				tmp = cp2 -> next;
				cp2 -> next = cp;
				cp = cp2;
				cp2 = tmp;
			}
		}
		else {
			hookp = &(p -> next);
		}
	}
	*Tp++ = get_cpu_time ();

	/* Find violated SEC's using a heuristic flow	*/
	/* formulation.					*/
	for (p = comp; p NE NULL; p = p -> next) {
		p -> cp = sec_flow_heuristic (p,
					      x,
					      edge_mask,
					      cip,
					      p -> cp);
	}
	*Tp++ = get_cpu_time ();

	/* Find small-cardinality subtour violations	*/
	/* by partial enumeration...			*/
	for (p = comp; p NE NULL; p = p -> next) {
		p -> cp = find_small_subtours (p, p -> cp, bbip);
	}
	*Tp++ = get_cpu_time ();

	/* Discard each component for which we have found at least one	*/
	/* violation.  Gather all constraints onto the main list...	*/
	hookp = &comp;
	for (;;) {
		p = *hookp;
		if (p EQ NULL) break;
		cp2 = p -> cp;
		if (cp2 NE NULL) {
			/* Gather these constraints onto main list... */
			p -> cp = NULL;
			while (cp2 NE NULL) {
				tmp = cp2 -> next;
				cp2 -> next = cp;
				cp = cp2;
				cp2 = tmp;
			}
			*hookp = p -> next;
			p -> next = NULL;
			free_congested_component (p);

		}
		else {
			/* No constraints yet for this component.  We	*/
			/* may want to try the more expensive method...	*/
			/* Retain this component.			*/
			hookp = &(p -> next);
		}
	}

#if 0
	/* Time to use the new-fangled SEC separator... */
	p2 = comp;
	comp = NULL;
	cp = sec_flow_separator (&p2, x, edge_mask, bbip, cp);
	*Tp++ = get_cpu_time ();
#else
	/* Time to use the new-fangled SEC separator... */
	/* Do it one component at a time, so that we can see if */
	/* there are any components for which no violations were found. */
	while (comp NE NULL) {
		p2 = comp;
		comp = comp -> next;
		p2 -> next = NULL;
		cp2 = sec_flow_separator (&p2, x, edge_mask, bbip, NULL);
		while (cp2 NE NULL) {
			tmp = cp2 -> next;
			cp2 -> next = cp;
			cp = cp2;
			cp2 = tmp;
		}
	}
	*Tp++ = get_cpu_time ();
#endif

	/* If this separation routine does not find any SEC violations,	*/
	/* it means that none exist!					*/
	optimal = TRUE;

	/* Note: congested components are all freed now... */

#if 0
	if (cp EQ NULL) {
		/* Nothing else found -- look for fractional cutsets... */
		cp = find_fractional_cutsets (x,
					      bbip -> csip,
					      vert_mask,
					      edge_mask,
					      cip);
		*Tp++ = get_cpu_time ();
	}
#endif

	if ((cp EQ NULL) AND optimal) {
		/* We KNOW that we have NO violations!  The LP	*/
		/* relaxation is now OPTIMAL!			*/
		bbip -> node -> optimal = TRUE;
	}

	*Tpp = Tp;

	return (cp);
}

/*
 * This routine attempts to use LP reduced costs to fix variables.  Any
 * variable whose reduced cost exceeds the current LP/IP gap can be
 * permanently fixed to its current value (either 0 or 1) for the duration
 * of the current bb-node (and all of its children).
 */

	static
	int
reduced_cost_var_fixing (

struct bbinfo *		bbip	/* IN - branch-and-bound info */
)
{
int			i;
int			nedges;
int			nmasks;
int			status;
int			nfix0;
int			nfix1;
struct cinfo *		cip;
LP_t *			lp;
double *		zlb;
double			gap;
double			threshold;
int *			newfix0;
int *			newfix1;
struct bbnode *		nodep;
double *		x;

	if (bbip -> best_z >= DBL_MAX) {
		/* Can't reasonably attempt this until we have	*/
		/* a valid upper bound...			*/
		return (VFIX_NOTHING_FIXED);
	}

	nodep = bbip -> node;
	gap = bbip -> best_z - nodep -> z;

	/* Only fix if we significantly exceed the gap... */
	gap *= (1.0 + FUZZ);

	threshold = nodep -> z + gap;

	lp	= bbip -> lp;
	cip	= bbip -> cip;
	nedges	= cip -> num_edges;
	nmasks	= cip -> num_edge_masks;

	nodep	= bbip -> node;
	x	= nodep -> x;
	zlb	= nodep -> zlb;

	newfix0 = NEWA (nedges, int);
	newfix1 = NEWA (nedges, int);

	nfix0	= 0;
	nfix1	= 0;

	for (i = 0; i < nedges; i++) {
		if (BITON (bbip -> fixed, i)) continue;

		if (zlb [2 * i] > threshold) {
			newfix1 [nfix1++] = i;
		}
		if (zlb [2 * i + 1] > threshold) {
			newfix0 [nfix0++] = i;
		}
	}

	status = VFIX_NOTHING_FIXED;

	if ((nfix0 > 0) OR (nfix1 > 0)) {
		status = fix_variables (bbip, newfix0, nfix0, newfix1, nfix1);
	}

	free ((char *) newfix1);
	free ((char *) newfix0);

	return (status);
}

/*
 * This routine fixes variables to zero and/or one.  We are given two
 * lists of variables to fixed, those to be fixed to zero, and those
 * to be fixed to one.  This routine then iteratively applies a series
 * of deductive steps that can cause additional variables to be fixed
 * based upon connectivity and compatibility criteria.
 */

	static
	int
fix_variables (

struct bbinfo *		bbip,		/* IN - branch-and-bound info */
int *			fix_to_0,	/* IN - vars to fix to 0 */
int			nfix0,		/* IN - number of vars fixed to 0 */
int *			fix_to_1,	/* IN - vars to fix to 1 */
int			nfix1		/* IN - number of vars fixed to 1 */
)
{
int			i;
int			j;
int			k;
int			t;
int			fs;
int			nedges;
int			nmasks;
int			kmasks;
int			status;
int			last_fset;
int			fix0_count;
int			fix1_count;
struct cinfo *		cip;
struct bbnode *		nodep;
bitmap_t *		fixmask0;
bitmap_t *		fixmask1;
bitmap_t *		terms_checked;
int *			ep1;
int *			ep2;
int *			ep3;
int *			ep4;
int *			vp1;
int *			vp2;
int			vars_fixed;
int			fix_frac;

#undef	PRINT_FIXED_VARIABLES

	cip	= bbip -> cip;
	nodep	= bbip -> node;

	nedges	= cip -> num_edges;
	nmasks	= cip -> num_edge_masks;
	kmasks	= cip -> num_vert_masks;

	fixmask0 	= NEWA (2 * nmasks + kmasks, bitmap_t);
	fixmask1 	= fixmask0 + nmasks;
	terms_checked	= fixmask1 + nmasks;

	/* Initialize masks of vars in fix-to-0 and fix-to-1 lists. */
	/* We use these to prevent adding duplicate entries later on. */
	for (i = 0; i < nmasks; i++) {
		fixmask0 [i] = 0;
		fixmask1 [i] = 0;
	}
	for (i = 0; i < nfix0; i++) {
		SETBIT (fixmask0, fix_to_0 [i]);
	}
	for (i = 0; i < nfix1; i++) {
		SETBIT (fixmask1, fix_to_1 [i]);
	}

	status = VFIX_NOTHING_FIXED;

	fix_frac = 0;

	fix0_count = 0;
	fix1_count = 0;

	/* Iteratively fix variables until no more fixing can be done. */
	do {
		vars_fixed = FALSE;

		/* =============== Handle fixing vars to 0 =============== */

		ep1 = fix_to_0;
		ep2 = ep1;
		ep3 = ep1 + nfix0;
		while (ep1 < ep3) {
			fs = *ep1++;
			CLRBIT (fixmask0, fs);
			if (NOT BITON (bbip -> fset_mask, fs)) continue;
			if (BITON (bbip -> fixed, fs)) {
				if (NOT BITON (bbip -> value, fs)) {
					/* Already fixed to zero!  Ignore. */
					continue;
				}
				/* Already fixed to one! */
				status = VFIX_INFEASIBLE;
				goto alldone;
			}
			/* Fix it to zero now! */
			SETBIT (bbip -> fixed, fs);
			CLRBIT (bbip -> value, fs);
			SETBIT (nodep -> fixed, fs);
			CLRBIT (nodep -> value, fs);
			if ((FUZZ < nodep -> x [fs]) AND
			    (nodep -> x [fs] + FUZZ < 1.0)) {
				++fix_frac;
			}
			change_var_bounds (bbip -> lp, fs, 0.0, 0.0);
			++fix0_count;
#ifdef PRINT_FIXED_VARIABLES
			tracef (" %%	Fixed x%-3d = 0\n", fs);
#endif
			/* Save this edge for later check. */
			*ep2++ = fs;
			/* We have fixed at least 1 variable! */
			status = VFIX_VARIABLES_FIXED;
			vars_fixed = TRUE;
		}
		ep1 = fix_to_0;
		if (ep1 < ep2) {
			/* Check if any of the vars we just set to 0	*/
			/* permit us to deduce vars that must be 1...	*/
			for (i = 0; i < kmasks; i++) {
				terms_checked [i] = 0;
			}
			while (ep1 < ep2) {
				i = *ep1++;
				vp1 = cip -> edge [i];
				vp2 = cip -> edge [i + 1];
				while (vp1 < vp2) {
					t = *vp1++;
					if (BITON (terms_checked, t)) continue;
					SETBIT (terms_checked, t);
					ep3 = cip -> term_trees [t];
					ep4 = cip -> term_trees [t + 1];
					k = 0;
					last_fset = -1;
					while (ep3 < ep4) {
						fs = *ep3++;
						if (NOT BITON (bbip -> fset_mask, fs)) continue;
						if (BITON (bbip -> fixed, fs) AND
						    NOT BITON (bbip -> value, fs)) continue;
						/* Full set fs has term t */
						/* and is NOT fixed to zero. */
						last_fset = fs;
						++k;
						if (k > 1) break;
					}
					if (k <= 0) {
						/* disconnected terminal! */
						status = VFIX_INFEASIBLE;
						goto alldone;
					}
					if ((k EQ 1) AND
					    NOT BITON (fixmask1, last_fset)) {
						/* one full set left, it */
						/* must be taken! */
						SETBIT (fixmask1, last_fset);
						fix_to_1 [nfix1++] = last_fset;
					}
				}
			}
		}
		/* Set the Fix-to-0 list to empty.  Fixmask0 should now	*/
		/* have all bits turned off.				*/
		nfix0 = 0;


		/* =============== Handle fixing vars to 1 =============== */

		ep1 = fix_to_1;
		ep2 = ep1 + nfix1;
		while (ep1 < ep2) {
			fs = *ep1++;
			CLRBIT (fixmask1, fs);
			if (NOT BITON (bbip -> fset_mask, fs)) continue;
			if (BITON (bbip -> fixed, fs)) {
				if (BITON (bbip -> value, fs)) {
					/* Already fixed to one!  Ignore. */
					continue;
				}
				/* Already fixed to zero! */
				status = VFIX_INFEASIBLE;
				goto alldone;
			}
			/* Fix it to one now! */
			SETBIT (bbip -> fixed, fs);
			SETBIT (bbip -> value, fs);
			SETBIT (nodep -> fixed, fs);
			SETBIT (nodep -> value, fs);
			if ((FUZZ < nodep -> x [fs]) AND
			    (nodep -> x [fs] + FUZZ < 1.0)) {
				++fix_frac;
			}
			change_var_bounds (bbip -> lp, fs, 1.0, 1.0);
			++fix1_count;
#ifdef PRINT_FIXED_VARIABLES
			tracef (" %%	Fixed x%-3d = 1\n", fs);
#endif
			/* We have fixed at least 1 variable! */
			status = VFIX_VARIABLES_FIXED;
			vars_fixed = TRUE;

			/* Fix every *other* incompatible FST to zero! */
			ep3 = cip -> inc_edges [fs];
			ep4 = cip -> inc_edges [fs + 1];
			while (ep3 < ep4) {
				j = *ep3++;
				if (j EQ fs) continue;
				if (NOT BITON (fixmask0, j)) {
					SETBIT (fixmask0, j);
					fix_to_0 [nfix0++] = j;
				}
			}
		}
		/* Set the Fix-to-1 list to empty.  Fixmask1 should now	*/
		/* have all bits turned off.				*/
		nfix1 = 0;
	} while (vars_fixed);

alldone:

	if ((fix0_count | fix1_count) NE 0) {
		/* Problem has changed -- force re-solve of LP. */
		nodep -> cpiter = -1;
	}

	switch (status) {
	case VFIX_NOTHING_FIXED:
		break;

	case VFIX_VARIABLES_FIXED:
		if (fix_frac >