arXiv:2606.20637v1 cs.AI

의무의 해밀토니안 표현을 통한 선거구 최적화(COTHROM): 아일랜드 선거구 경계의 알고리즘적 재편

Constituency Optimisation Through Hamiltonian Representation Of Mandates (COTHROM): Algorithmic Redistricting of Irish Election Boundaries

Ruaidhrí Campion, Matthew Fenlon, Joshua Cooney Mercedal, Casey Farren-Colloty, Eliza Somerville, Michael A. J. Mitchell

제출 2026-06-02

한국어 초록

아일랜드의 비례 대표 단일 이동표(PR-STV) 제도에서 선거구 재편은 방대한 가능 구성 집합 가운데 최적으로 대표성 있는 선거구 경계 집합을 선택해야 하는 과제에 직면하며, 여기서 '대표성'은 종종 서로 긴장 관계에 있는 헌법적 목표들의 미묘한 균형을 의미한다. 우리는 상호 트레이드오프(trade-off)를 명시적이고 정량화 가능하게 만들면서 여러 헌법적 요건을 체계적으로 최적화하는 아일랜드 선거구 재편을 위한 최초의 계산 프레임워크를 제시한다. 선거구 재편 문제는 통계물리학을 사용하여 분석되며, 헌법적 목표는 Potts 해밀토니안의 항으로 간주된다. 마르코프 연쇄 몬테카를로(MCMC) 방법과 시뮬레이티드 어닐링(simulated annealing)을 사용하여 결합 상수를 목표 가중치의 대리 변수로 하여 이 구성 공간을 체계적으로 탐색하면서 이 목적 함수를 최소화한다. 다중 기준 의사결정 분석(MCDA)과 파레토 최적성(Pareto Optimality)은 특정 목표 가중치 조합을 다른 조합보다 선택할 때의 모호성을 해소하는 데 활용된다. 코르크 주(County Cork)에서 평가된 비례 대표성과 치밀성(compactness) 목표에 관하여, COTHROM은 다양한 목표 가중치에 대해 기존의 법적 선거구 경계를 지속적으로 개선한다.

원문 초록

Electoral redistricting in Ireland's Proportional Representation Single Transferable Vote (PR-STV) system faces the challenge of selecting an optimally representative set of electoral boundaries from an enormous set of possible configurations, and where ``representative'' is a delicate balance of constitutional objectives that are often in tension with one another. We present the first computational framework for Irish electoral redistricting that systematically optimises across multiple constitutional requirements while making trade-offs explicit and quantifiable. The electoral redistricting problem is parsed using statistical physics, where constitutional objectives are considered as terms in a Potts Hamiltonian. Markov Chain Monte Carlo (MCMC) methods and simulated annealing are employed to minimise this objective function, systematically exploring this configuration space, with coupling constants as proxies for objective weightings. Multi Criterion Decision Analysis (MCDA) and Pareto Optimality is then utilised to remedy the ambiguity in choosing a certain objective weighting combination over others. With respect to proportional representation and compactness objectives evaluated in County Cork, COTHROM consistently improves on the existing legal constituency boundaries for a range of objective weightings.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.20637v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.22539v1math.OC공통 태그 Stochastic Optimization, Combinatorial Optimization, simulated annealing

방사선 치료 스케줄링을 위한 최적화 모델 비교

Comparing Optimization Models for Radiotherapy Scheduling

방사선 치료 스케줄링 문제(Radiotherapy Scheduling Problem, RTSP)는 방사선 치료를 받는 환자들에 대한 최적 일정을 결정하는 문제로, 방사선 치료가 암 치료에서 핵심적인 역할을 하므로 임상 결과에 큰 영향을 미치는 과업이다. 하루가 끝날 때 새로 도착한 모든 환자를 함께 스케줄링하는 일일 배치 접근법은 정수 선형 계획(Integer Linear Programming)으로 모델링되며, 현재 RTSP에 대한 가장 효과적인 방법 중 하나이다. 그러나 이러한 형식화는 시간과 메모리 측면에서 상당한 계산 자원을 필요로 한다. 본 연구에서는 RTSP First Fit과 RTSP Best Fit이라는 두 가지 새로운 탐욕적 휴리스틱(greedy heuristics)을 개발하고, 이를 시뮬레이티드 어닐링(Simulated Annealing, SA) 접근법의 구성적 휴리스틱(constructive heuristics)으로 사용하여 스케줄링을 최적화함으로써 이러한 한계를 해결한다. 제안된 방법——휴리스틱 단독 및 SA와의 결합——은 공개 데이터셋에서 두 가지 서로 다른 최신 정확 솔버(exact solvers)로 풀린 정수 선형 프로그램(integer linear program) 형식화와 비교하여 평가된다. 평가 지표에는 환자 대기 시간, 선호도 충족, 선형 가속기(linear accelerator) 배정 변경(네 가지 서로 다른 가중치 구성으로 집계)을 포착하는 여섯 가지 스케줄링 목표, 풀이 시간, 메모리 소비가 포함된다. 결과는 새로운 휴리스틱이 정확한 방법들의 해에 근접한 해를 달성하면서 실행 시간과 메모리 사용량을 극적으로 줄인다는 것을 보여준다. 또한 SA와 결합하면 실행 시간과 메모리 사용량을 낮게 유지하면서 해의 품질을 더욱 향상시킨다.

arXiv:2607.11821v2cs.DM공통 태그 Combinatorial Optimization, multi-objective optimization

지지 비지배점에 의한 다목적 네트워크 문제의 비지배 집합 표현

Representing the Non-dominated Set of Multi-objective Network Problems by Supported Non-dominated Points

다목적 조합 최적화에서 비지지 비지배점(unsupported non-dominated point)은 통상 지지점(supported point)보다 수가 많으며, 계산하기도 훨씬 어려운 경우가 많다. 최근 연구에 따르면 극단 지지 비지배점(extreme supported non-dominated point)은 특정 이진 문제의 비지배 집합에 대해 고품질 표현을 제공한다. 본 논문에서는 이 관찰이 용량 제한 네트워크 최적화 문제로 일반화되지 않음을 보인다. 즉, 호(arc) 용량이 증가할수록 표현 품질이 저하되는 반면, 지지 비지배점은 여러 품질 지표에서 지속적으로 고품질 표현을 제공한다. 그러나 지지점 집합도 실용적인 응용에서는 지나치게 클 수 있으며, 일반적으로 소수의 고정된 대안만이 요구된다. 비지배 집합에서 고정 크기 표현을 선택하려면 계산 비용이 높은 전체 집합 생성이 필요하므로, 표현이 제공하려는 계산 상의 이점이 감소한다. 따라서 본 논문은 부분집합 선택 문제에서 (극단) 지지점을 대안적 후보 집합으로 제안한다. 수치 실험 결과, 후보 집합을 지지 비지배점으로 제한하더라도 완전한 비지배 집합에서 선택한 것과 거의 동일한 품질의 고정 크기 표현을 얻을 수 있음을 보인다. 종합하면, 지지 비지배점은 고품질 표현이자 부분집합 선택을 위한 합리적인 후보 집합으로 모두 활용될 수 있다.

arXiv:2610.13773v1math.OC공통 태그 Stochastic Optimization, multi-objective optimization

기하학적 구조를 고려한 다중 목적 최적화: 엔트로피 기반 가중치 업데이트를 적용한 노름 제약 오라클

Geometry-Aware Multi-Objective Optimization: Norm-Constrained Oracles with Entropic Weight Updates

다중 경사하강법(Multiple-gradient descent)은 일반적으로 유클리드 기하학에서 공식화되는 반면, 행렬 인식 옵티마이저는 다른 노름(norm)에 의해 유도된 방향을 사용합니다. 본 논문에서는 노름 제약이 있는 선형 최소화 오라클과 태스크 가중치의 엔트로피 업데이트를 결합한 단일 루프 다중 목적 최적화 기법을 분석합니다. 유한 차원 노름 쌍에 대해 결정론적 환경에서 $O(T^{-1/2})$의 에르고딕 정지성(ergodic stationarity) 수렴 속도를 확립하며, 비정규화된 경우 평활성(smoothness) 및 하한 유계성으로부터 필요한 궤적 그래디언트 경계를 유도합니다. 확률적 그래디언트와 유계 그래디언트 가정 하에서는 단일 지속 혼합 그래디언트 모멘텀 버퍼를 통해 선행 항이 태스크 수에 명시적으로 의존하지 않는 $O(T^{-1/4})$ 수렴 속도를 산출합니다. 또한 임의의 유계 그래디언트 시퀀스에 대해 내부 가중치 목적식의 정적 리그릿(static regret)을 확립하고, 엔트로피 정규화와 가중치 하한(weight floor)을 적용하여 궤적 그래디언트 경계를 조건으로 에르고딕 정지성을 유지하면서 웜업(burn-in) 이후 반복별 내부 갭 제어를 달성합니다. 최적의 혼합 그래디언트는 스펙트럼 및 부호 기하학에서 유일하지 않을 수 있으므로, 선택에 독립적인 내부 갭의 필요성을 부여합니다. 본 분석은 동시 연구인 MOON에서 연구된 스펙트럼 구성을 일반적인 노름으로 확장합니다. 실험을 통해 기존 멀티태스크 옵티마이저와 제안 방법을 비교하고 오라클, 가중치 부여 및 모멘텀 선택을 검토합니다.

arXiv:2609.26978v1stat.ML공통 태그 Stochastic Optimization, Combinatorial Optimization

다중 스케일 행렬 가중치를 통한 온라인 역 선형 최적화의 정밀 후회 상한

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

고정된 알려지지 않은 선형 효용(utility)을 갖는 온라인 역 선형 최적화를 연구한다. 각 라운드에서 환경(environment)은 컴팩트 행동 집합을 제시하고, 학습자(learner)는 그 집합에서 행동(action)을 추천하며, 환경은 동일한 집합 위에서 효용을 최대화하는 행동을 반환한다. 효용 벡터와 행동이 $d$차원 유클리드 단위 구(unit ball) 안에 있을 때, 시간 지평(time horizon)을 알 필요 없이 모든 시간 지평에 대해 기대 후회(regret)---최적 행동 대비 누적 효용 부족분---가 $O(\sqrt d)$인 무작위 알고리즘을 제시한다. $d$에 대한 의존성은 $T\ge d$인 지평에 대한 알려진 $\Omega(\sqrt d)$ 하한에 의해 상수 배수까지 최적이다. 우리 알고리즘은 기하학적으로 간격을 둔 스케일에서 다항식 특징(feature) 공간上的 행렬 곱셈 가중(matrix multiplicative weights)을 유지한다. 선형 프로그램(linear program)을 풀어 추천 분포를 선택하고, 이용 가능한 행동과 피드백 행동을 비교하여 점수 행렬을 갱신한다. 유리수 oracle 출력과 피드백 행동 하에서, 선형 최적화 oracle에 상대적으로 계산 가능한 구현이 $O(\sqrt d)$ 후회 상한을 유지한다. 차원, 지평, 입력 길이에 대해 다항 시간 실행 복잡도로 동일한 rate를 달성할 수 있는지는 열려 있다.

arXiv:2609.28263v1cs.LG공통 태그 Stochastic Optimization, Combinatorial Optimization

재해결 없이 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

대규모 언어 모델(LLM) 추론과 검색 서비스의 확대는 온라인 선형 계획 문제의 규모를 키우며, 계산적으로 효율적인 알고리즘을 요구한다. 본 연구는 확률적 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법(RASGD)을 제안한다. 이 알고리즘은 요청 하나와 현재 재고(inventory)만으로 자원 가격을 갱신하며, 자원 m개에 대해 도착(arrival)마다 O(m) 연산과 메모리만 필요하고 LP나 표본 평균 최적화(sample-average optimization)는 사용하지 않는다. 핵심은 재해결(re-solving)에서 쓰이는 현재 자원 가격 책정 로직을 1차 SGD 갱신으로 표현하는 것이다. 각 도착마다 이중 목적(dual objective)의 잔여 재고 허용량(allowance)을 갱신하고, 스텝 크기(stepsize)는 초기에는 학습을 위해 작아지다가 이후에는 재고 조정 속도에 맞추어 커진다. 표준 비퇴화(non-degeneracy) 조건 하에서 알고리즘은 모든 표본 경로(sample path)에서 실행 가능(feasible)하며, 실현된 분수적 후견 최적(realized fractional hindsight optimum) 대비 O(\log T) 기대 후회(expected regret)를 달성한다. 이는 분포를 알고 계산 제약이 없는 정책에 대한 하한과 일치한다. 분석은 변화하는 자원 수준에서 최적 가격을 추적하지 않고, 고정 참조 가격 주변의 곡률(curvature)을 재고 안정성(inventory stability)으로 전환한다. 수치 실험에서 RASGD는 도착마다 LP 재해결과 견줄 만한 후회를 달성하고, 시험한 1차 기준선(first-order baselines)보다 나으면서 1차 방법의 계산 효율은 유지한다. 이 결과는 RASGD가 대규모 OLP에서 높은 할당 품질을 계산 효율적으로 달성하는 접근임을 보여준다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.