빈 패킹 (상자 채우기)

무엇을 정하나요

물건마다 담을 상자를 정합니다.

최소 실행 예제

from optimaru.bin_packing import solve
from optimaru.bin_packing.models import BinPackingProblemModel, ItemModel

problem = BinPackingProblemModel(
    bin_capacity=10,
    items=[
        ItemModel(id="A", weight=8), ItemModel(id="B", weight=7),
        ItemModel(id="C", weight=3), ItemModel(id="D", weight=2),
    ],
)

core = problem.to_core()
print(solve(core, time_limit_seconds=1.0, random_seed=42))  # 0hard/-2soft 같은 Score
solved = BinPackingProblemModel.from_core(core)
print({item.id: item.bin for item in solved.items}, solved.bins_used, solved.bin_loads)

같은 유스케이스를 그림과 실행 결과가 담긴 Jupyter 노트북으로도 볼 수 있습니다. examples/bin-packing.ipynb ↗

입력 파라미터

ItemModel

id 필수 입력 물건 id입니다. weight 필수 입력 1차원 무게나 크기입니다. color 선택 사항인 색상입니다. 상자 하나에 색상별로 물건을 하나만 넣을 수 있습니다.

ConflictModel

first 필수 입력 한쪽 물건의 id입니다. second 필수 입력 같은 상자에 넣으면 안 되는 물건의 id입니다.

BinPackingProblemModel

bin_capacity 필수 입력 상자 하나의 최대 적재량입니다. 상자는 모두 같습니다. items 필수 입력 물건 목록입니다. 물건마다 한 번씩 배정합니다. conflicts 같은 상자에 넣으면 안 되는 물건 쌍입니다.

풀이 파라미터

풀이를 호출할 때 넘기는 값입니다. 시간 제한, 시드, 병렬 수가 여기에 있습니다.

탐색은 best-fit decreasing으로 만든 해에서 시작해 늦은 수락(late acceptance) 방식으로 진행하며, 변경·교환 이동과 파괴·재구성에 더해 상자를 한 걸음에 비우는 이동 두 가지를 씁니다. 상자는 마지막 물건이 빠져야 비용이 사라지기 때문입니다. EmptyBinMove는 용량만 확인합니다. RepackMove는 가벼운 상자 몇 개의 물건을 아무 위반도 생기지 않는 곳에만 다시 넣으므로, 물건에 색상이나 금지 쌍이 있을 때 상자 수를 줄이는 것은 이 이동입니다. 색상 4가지와 금지 쌍 10개가 있고 무게만으로도 상자 43개가 필요한 물건 120개짜리 문제에서 2초 만에 상자 43개에 도달합니다. 0.1.5보다 하나, 이 이동이 없을 때보다 두세 개 적습니다.

탐색 옵션 전체 (29)

SolverConfig에 값을 넣어 config=로 넘기세요.

파라미터	기본값	의미
best_score_limit	—	최고 점수가 이 값에 닿으면 일찍 멈춥니다. 기본값으로는 작동하지 않습니다.
change_move_weight	0.75	변경 이동의 상대적 비중입니다. 0이면 쓰지 않습니다.
custom_move_probability	1.0	한 걸음에서 유스케이스 전용 이동을 고를 수 있는 확률의 상한입니다. 1이면 제한이 없습니다.
descent_weight	0.0	최선 개선 하강의 비중입니다. 0이면 끕니다.
empty_bin_candidates	3	상자를 비우는 두 이동이 가장 가벼운 상자 몇 개 가운데서 비울 상자를 고를지 정합니다. 1이면 언제나 가장 가벼운 상자를 비웁니다.
empty_bin_moves	True	가벼운 상자 하나를 통째로 비워 물건을 다른 상자로 옮기는 EmptyBinMove를 씁니다. 용량만 확인하므로 색상이나 금지 쌍이 있으면 상자 수를 거의 줄이지 못하며, 그때는 repack_moves가 줄입니다.
full_assert	False	증분 점수를 전체 재계산과 매번 비교합니다. 느리므로 디버깅할 때만 씁니다.
late_acceptance_size	0	늦은 수락(late acceptance) 기록의 길이입니다. 0이면 문제 크기에 맞춰 정합니다.
on_new_best	None	새 최고 해를 찾을 때마다 부르는 콜백입니다. 콜백이 예외를 내면 풀이를 멈추고 그 예외를 그대로 냅니다.
parallel_solver_count	1	독립적으로 동시에 돌리는 탐색 수입니다. 탐색마다 시드가 다르고 시간은 똑같이 쓰며, 가장 좋은 결과를 고릅니다.
random_seed	0	탐색에 쓰는 난수 시드입니다.
repack_moves	True	RepackMove를 씁니다. 가벼운 상자 하나를 다른 가벼운 상자 최대 repack_partner_bins개와 함께 비운 뒤, 무거운 물건부터 용량·색상·금지 쌍 규칙을 어기지 않는 가장 꽉 찬 상자에 다시 넣습니다. 색상이나 금지 쌍이 있을 때 상자 수를 줄이는 것은 이 이동입니다.
repack_partner_bins	2	RepackMove가 처음 고른 상자와 함께 비우는 다른 가벼운 상자의 최대 수입니다. 0이면 그 상자만 비우고, 음수는 ValueError를 냅니다.
ruin_recreate	True	탐색이 정체되면 적응형 파괴·재구성을 실행합니다.
ruin_recreate_as_move_max_ruin	12	그 작은 파괴로 제거할 최대 항목 수입니다.
ruin_recreate_as_move_weight	0.0	한 걸음을 작은 파괴·복구로 쓰고 일반 이동처럼 판단할 확률입니다. 음수는 지원하는 유스케이스에서 자동 선택이고, 0이면 끕니다.
ruin_recreate_max_ruin_count	60	한 번에 제거하는 항목 수의 절대 상한입니다.
ruin_recreate_max_ruin_fraction	0.3	한 번에 제거하는 해의 최대 비율입니다.
ruin_recreate_min_ruin_fraction	0.1	한 번에 제거하는 해의 최소 비율입니다.
ruin_recreate_operator_decay	0.8	연산자 가중치가 적응하는 속도입니다.
ruin_recreate_polish_steps	5000	실행 후 다듬는 언덕 오르기 이동 수입니다. step_count_limit에는 세지 않습니다.
ruin_recreate_rewards	[33.0, 9.0, 3.0, 0.0]	새 최고, 개선, 수락, 거절 결과에 주는 연산자 보상입니다.
ruin_recreate_unimproved_step_trigger	5000	파괴·재구성을 실행하기까지 새 최고 해 없이 지나는 걸음 수입니다.
spent_limit_seconds	30.0	탐색 시간(초)이며, 0부터 1e9까지 줄 수 있습니다.
step_count_limit	0	이 걸음 수에 도달하면 멈춥니다. 0이면 제한이 없습니다.
swap_move_weight	0.25	교환 이동의 상대적 비중입니다. 0이면 쓰지 않습니다.
unimproved_spent_limit_seconds	0.0	새 최고 해 없이 이 시간(초)이 지나면 멈춥니다. 0이면 제한이 없습니다.
unimproved_step_count_limit	0	새 최고 해 없이 이 걸음 수가 지나면 멈춥니다. 0이면 제한이 없습니다.
value_recommender_probability	0.5	변경 이동이 물건을 아무 상자에나 넣지 않고 이미 쓰고 있는 상자로 옮길 확률입니다. 0이면 끕니다.

돌아오는 결과

solve는 to_core()로 만든 엔진 객체를 그 자리에서 채우고 0hard/-2soft 같은 엔진 Score를 돌려줍니다. 값은 .hard와 .soft로 읽습니다. 결과를 모델로 읽으려면 from_core로 변환합니다. 탐색이 해를 바꿨다면 상자 번호는 처음 쓰인 순서대로 0부터 다시 매깁니다.

ItemModel

bin 0부터 시작하는 상자 번호입니다. -1이면 아직 풀리지 않았다는 뜻입니다.

BinPackingProblemModel

bins_used 물건이 든 상자 수입니다. bin_loads 상자별 총 무게입니다. score_hard 필수 점수입니다. 0이면 가능한 해입니다. score_soft 선호 점수입니다. 사용한 상자 수의 음수입니다.

제약

optimaru.bin_packing.constraints에서 클래스를 가져와 BinCapacityCost()처럼 호출해서 넘깁니다. 넘긴 제약만 점수에 들어가고, 아무것도 넘기지 않으면 기본 제약을 씁니다. 목록에 같은 제약을 여러 번 넣을 수 있으며, 넣은 것마다 따로 점수에 들어갑니다. 제약마다 다음 파라미터를 받습니다.

위의 최소 실행 예제에 이어서 실행합니다.

from optimaru.bin_packing.constraints import BinCapacityCost, UsedBinsCost, get_constraints

picked = get_constraints([BinCapacityCost(weight=5), UsedBinsCost()])
print(solve(problem.to_core(), time_limit_seconds=1.0, random_seed=42, constraints=picked))

제약 사용법 →

기존 해에서 시작하기

최신 버전이 필요합니다. pip install -U optimaru로 올려 주세요.

with_initial_solution(problem, solution)은 solution에서 탐색을 시작하는 BinPackingProblemModel 복사본을 돌려줍니다. solution은 풀린 모델이나 그 JSON 딕셔너리입니다. solve 전에 복사본의 .to_core()를 호출하세요.

위의 최소 실행 예제에 이어서 실행합니다.

from optimaru.bin_packing import with_initial_solution

warm = with_initial_solution(problem, solved).to_core()
print(solve(warm, time_limit_seconds=1.0, random_seed=42), warm.bin_loads())

• 물건은 id로 맞춥니다. 빠졌거나 상자가 -1인 물건은 탐색 전에 best-fit 구성으로 기존 상자 주변에 배치합니다. 완전한 해는 구성 단계를 건너뜁니다.
• time_limit_seconds=0을 주면 바로 멈추므로 완전한 해는 넣은 그대로 돌아옵니다. step_count_limit = 0은 제한이 없다는 뜻이므로, 바로 멈추려면 시간 제한을 쓰세요.
• 모르는 id, 중복, 물건 수를 벗어난 상자 번호는 ValueError를 냅니다.

예외와 제한

• 상자는 1차원이고 크기가 모두 같습니다. 문제 모델에는 가중치 필드가 없습니다. 기본 가중치는 모두 1이며, 바꾸려면 constraints=로 제약을 넘기세요.

직접 해 보기

• 라이브 데모 ↗
• Jupyter 노트북 ↗
• 솔루션 페이지에서 보기 →