lower_bound.hpp File Reference

Exact lower bound on weighted HPWL (design doc 04 §1 level L4). More...

#include <cstdint>
#include "place/legality.hpp"

Go to the source code of this file.

Classes
class	tmk::place::MinCostFlow
	Min-cost flow on a small graph (exposed for tests). More...

Namespaces
namespace	tmk
namespace	tmk::place

Enumerations
enum class	tmk::place::RotationModel { tmk::place::Fixed , tmk::place::Any }

Functions
std::int64_t	tmk::place::hpwl_lower_bound (const Problem &p, const Placement &pl, RotationModel model)
	Minimum weighted HPWL (Σ weight · HPWL, nm) over all positions of the movable parts with overlaps and the board outline ignored.

Detailed Description

Exact lower bound on weighted HPWL (design doc 04 §1 level L4).

Without overlap and outline constraints, minimising Σ_n w_n (max_i x_i − min_i x_i) over the movable parts' positions is a linear program whose constraints are all differences (U_n − X_p ≥ o, X_p − L_n ≥ −o), so its dual is an uncapacitated min-cost flow from the nets' upper nodes U_n through the parts (or the fixed "ground" node) to the nets' lower nodes L_n. Solved exactly in integers by successive shortest paths (Ahuja, Magnanti, Orlin, "Network Flows", 1993, ch. 9). By LP duality the optimum equals the minimum of the relaxed placement problem, so it bounds every legal placement from below.

Definition in file lower_bound.hpp.