sawmill-quantum-optima/classical_solver.py at main · spinsphere/sawmill-quantum-optima · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
"""
Classical greedy packing solver for sawmill optimization.

Serves as the baseline for comparison against the quantum solver.
"""

import time
import numpy as np
from data_generator import Log, BoardCandidate, _board_intersects_defect, Defect


def _boards_physically_overlap(a: BoardCandidate, b: BoardCandidate, kerf=0.125):
    """Check spatial overlap between two boards (with kerf allowance)."""
    a_l = a.cx - a.width / 2.0 - kerf
    a_r = a.cx + a.width / 2.0 + kerf
    a_b = a.cy - a.height / 2.0 - kerf
    a_t = a.cy + a.height / 2.0 + kerf

    b_l = b.cx - b.width / 2.0
    b_r = b.cx + b.width / 2.0
    b_b = b.cy - b.height / 2.0
    b_t = b.cy + b.height / 2.0

    return a_l < b_r and a_r > b_l and a_b < b_t and a_t > b_b


def greedy_solve(log: Log, respect_hidden_defects=False):
    """
    Greedy packing: sort boards by value density, greedily add non-overlapping.

    Args:
        log: The log to solve.
        respect_hidden_defects: If True, skip boards that hit hidden defects
            (simulates perfect knowledge). If False, hidden defects are
            discovered during "cutting" and the board is simply discarded.

    Returns:
        dict with keys: selected_boards, total_value, waste_fraction,
        solve_time, defect_discoveries
    """
    t0 = time.time()
    candidates = list(log.board_candidates)

    # sort by value per unit area (descending)
    for c in candidates:
        c._density = c.value / max(c.width * c.height, 1e-6)
    candidates.sort(key=lambda c: c._density, reverse=True)

    selected = []
    total_value = 0.0
    defect_discoveries = 0

    for c in candidates:
        # check overlap with already-selected boards
        if any(_boards_physically_overlap(c, s) for s in selected):
            continue

        # check visible defects (always respected)
        visible_hit = any(
            _board_intersects_defect(c, d)
            for d in log.defects if not d.hidden
        )
        if visible_hit and c.grade == 'premium':
            continue  # skip premium boards on visible defects

        # hidden defect logic
        if not respect_hidden_defects:
            hidden_hit = any(
                _board_intersects_defect(c, d)
                for d in log.defects if d.hidden
            )
            if hidden_hit:
                # "discover" the defect mid-cut — board is wasted
                defect_discoveries += 1
                # greedy just moves on (no re-optimization)
                continue

        selected.append(c)
        total_value += c.value

    # waste calculation
    log_area = np.pi * (log.diameter_small / 2.0) ** 2  # conservative
    board_area = sum(b.width * b.height for b in selected)
    waste_fraction = 1.0 - min(board_area / max(log_area, 1e-6), 1.0)

    return {
        'selected_boards': selected,
        'total_value': total_value,
        'waste_fraction': waste_fraction,
        'solve_time': time.time() - t0,
        'defect_discoveries': defect_discoveries,
        'method': 'classical_greedy',
    }