arXiv:2203.02878

A Survey for Solving Mixed Integer Programming via Machine Learning

Jiayi Zhang, Chang Liu, Junchi Yan, Xijun Li, Hui-Ling Zhen, Mingxuan Yuan

제출 2022-03-06

원문 초록

This paper surveys the trend of leveraging machine learning to solve mixed integer programming (MIP) problems. Theoretically, MIP is an NP-hard problem, and most of the combinatorial optimization (CO) problems can be formulated as the MIP. Like other CO problems, the human-designed heuristic algorithms for MIP rely on good initial solutions and cost a lot of computational resources. Therefore, we consider applying machine learning methods to solve MIP, since ML-enhanced approaches can provide the solution based on the typical patterns from the historical data. In this paper, we first introduce the formulation and preliminaries of MIP and several traditional algorithms to solve MIP. Then, we advocate further promoting the different integration of machine learning and MIP and introducing related learning-based methods, which can be classified into exact algorithms and heuristic algorithms. Finally, we propose the outlook for learning-based MIP solvers, direction towards more combinatorial optimization problems beyond MIP, and also the mutual embrace of traditional solvers and machine learning components.

함께 살펴볼 논문

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

arXiv:2607.13054v1cs.RO공통 태그 Survey, Combinatorial Optimization

환경 모니터링에서 커버리지 극대화를 위한 자율 UAV 경로 계획: 체계적 문헌 고찰

Autonomous UAV Route Planning for Coverage Maximization in Environmental Monitoring: A Systematic Literature Review

무인항공기(UAV)를 활용한 환경 모니터링에는 에너지 한계, 운영 제약, 기하학적 복잡성을 다루면서 커버 영역을 극대화하는 경로 계획 방법이 필요하다. 본 논문은 커버리지 중심 환경 모니터링을 위한 자율 UAV 경로 계획에 관한 진행 중인 체계적 문헌 고찰(SLR)의 절차와 예비 결과를 보고한다. 이 고찰은 PRISMA 2020 프레임워크를 따르며, 2015년부터 2026년까지 발표된 연구를 Scopus와 Web of Science에서 검색한다. 절차는 경로 계획(path planning), 커버리지 경로 계획(coverage path planning), 정보 경로 계획(informative path planning)에 초점을 두며, 알고리즘 계열, 커버리지 및 에너지 지표, 장애물 처리, 기하학적 환경 표현, 환경 제약을 강조한다. 현재 단계에서 562건의 기록이 식별되었고, 161건의 중복이 제거되었으며, 401건의 고유 기록이 제목, 초록, 키워드로 스크리닝되었다. 이 중 247건이 전문(full-text) 적격성 평가를 위해 유지되었고(235건 적격, 12건 경계 기록은 전문 검토 중 해결 예정), 유지된 연구의 예비 분석은 커버리지 중심 공식화, 다중 UAV 협조, 에너지 인식 최적화에 대한 강한 집중을 시사하는 반면, 날씨, 불확실성, 장애물이 많은 환경을 명시적으로 다루는 연구는 상대적으로 적다. 유지된 연구의 대부분은 시뮬레이션 기반 검증에 의존하여 잠재적인 시뮬레이션-현실 간 격차를 부각시키며, 최근 출판물은 강화학습, 하이브리드 최적화, 기하학 인식 계획에 대한 관심 증가를 보여준다. 이러한 초기 결과는 활발하지만 분절된 연구 환경을 나타내며, 현실적인 환경 모니터링 임무를 위한 성숙한 기법과 미해결 공백을 식별하기 위한 구조화된 종합의 필요성을 뒷받침한다.

arXiv:2607.14821v2cs.CV공통 태그 Survey

모달 경계의 흐림: 단일 모달에서 다중 모달 인물 재식별(ReID)에 대한 통합 서벡

Blurring Modal Boundaries: A Unified Survey from Single- to Multi-Modal Person Re-ldentification

인물 재식별(ReID)은 지능형 감시 시스템의 핵심 구성 요소로, 분리된 카메라 네트워크 간 신원을 매칭하는 것을 목표로 한다. 전통적인 방법은 주로 단일 모달 RGB 영상에 의존하지만, 낮은 조도와 가림(occlusion)과 같은 환경적 도전 과제에 종종 제약을 받는다. 이러한 한계를 극복하기 위해 해당 분야는 교차 모달(cross-modal) 및 다중 모달(multi-modal) 패러다임으로 빠르게 발전하고 있다. 본 서벡은 이러한 전환에 대한 포괄적인 개요를 제시하며, 직접 가시성을 넘어 지각을 확장하는 신흥 비시선(NLOS, Non-Line-of-Sight) ReID를 포함하여 가시-적외선(VI-ReID), 텍스트-이미지(TI-ReID), 스케치 기반(Sketch-ReID) 등 주요 교차 모달 과제를 체계적으로 검토한다. 또한 3분광(tri-spectral) 및 다중 모달 융합 ReID를 살펴보고, 다양한 센서의 상보적 정보가 어떻게 견고성(robustness)을 향상시키는지 논의한다. 데이터셋, 과제, 방법론을 요약하는 것을 넘어, 모달리티 불변(modality-invariant) 특징을 효과적으로 포착하도록 설계된 가시-적외선 ReID용 트랜스포머 기반 기준선 프레임워크를 제안한다. 마지막으로, 현재 연구 환경을 바탕으로 향후 연구를 위한 여러 유망한 방향을 제시한다.

arXiv:2610.13503v2cs.CV공통 태그 Combinatorial Optimization

SplatQ: 2차 선택을 통한 3D 가우시안 스플래팅의 상호작용 인지 가지치기

SplatQ: Interaction-Aware Pruning of 3D Gaussian Splatting via Quadratic Selection

기존의 3D 가우시안 스플래팅(3DGS) 가지치기(pruning) 방법들은 주로 독립적인 중요도 점수에 기반한 전역 Top-K 선택에 의존하여, 영역별 예산 제어가 부족하고 공동 삭제 효과를 무시합니다. 결과적으로 전체 장면에 걸쳐 균형 잡힌 재구성 품질을 보장하지 못합니다. 본 논문에서는 고정된 예산 하에서 영역별 예산 할당과 공동 가우시안 선택을 조율하는 조합 가지치기 알고리즘인 SplatQ를 제안합니다. SplatQ는 공간적 근접성과 외형 유사성을 기준으로 가우시안을 크기가 제한된 블록으로 분할하여, 전역 선택 문제를 특정 크기의 하위 문제들로 분해합니다. 그런 다음 중요도 기반의 블록 유지 할당량을 평활화하여 과도한 예산 집중을 방지합니다. 마지막으로 가우시안 불투명도 변화에 대한 대표 픽셀 색상의 반응을 활용하여 공동 삭제 효과의 2차 근사를 구성합니다. 개별 반응, 쌍별 상호작용 및 할당량 페널티는 2차 비제약 이진 최적화(QUBO) 목적 함수에 통합되며, 모의 담금질(SA) 또는 코히런트 이징 머신(CIM)을 사용하여 이를 해결함으로써 가우시안을 공동으로 선택합니다. 5개 벤치마크에 대한 실험을 통해 SplatQ가 종합적인 재구성 품질, 공간적 품질 균형, 렌더링 속도 측면에서 최신 가지치기 방법들보다 우수한 성능을 보임을 입증합니다. 절제 연구(ablation)를 통해 예산 평활화가 국소적인 세부 표현 재구성을 향상시키는 한편, 상호작용 모델링이 고정된 예산 하에서 가우시안 선택 품질을 향상시킴을 확인합니다.

arXiv:2607.11821v2cs.DM공통 태그 Combinatorial 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:2607.22305v2cs.AI공통 태그 Survey

영향력 있는 다원주의적 정렬 연구를 위한 로드맵

A Roadmap to Impactful Pluralistic Alignment Research

책임 있는 AI에 관한 많은 연구는 수십억 명이 사용하는 AI 시스템의 행동을 바꾸는 것을 목표로 한다. 다양한 인간의 가치와 관점을 대표하고 이에 기여하는 AI 시스템을 구축하는 것을 목표로 하는 다원적 가치 정렬은 이러한 활발한 연구 의제 중 하나로 부상했다. 그러나 주요 프론티어 연구소와 오픈 웨이트 개발자를 감사한 결과, 다원적 정렬이 이들 모델의 학습이나 평가 방식에 영향을 미쳤다는 공개적 증거를 찾을 수 없었다. 다원적 정렬은 주요 목표를 달성하려면 실제 도입이 필요하므로, 우리는 세 가지 장벽을 규명하고 각각을 해결하기 위한 연구 로드맵을 제시한다. 1. 지금까지 다원적 정렬의 정당화는 대부분 규범적이거나 이론적이다. 다원적 AI가 사용자와 사회에 주는 이점과 단점을 측정하는 연구가 필요하다. 2. 다원적 정렬 연구 커뮤니티는 다원적 행동이 언제 정당화되는지, 그리고 실제로 어떤 모습이어야 하는지에 대해 합의하지 못했다. 개발자가 이를 구현할 수 있을 만큼 구체적으로 이 행동을 명세하는 연구가 필요하다. 3. 기존의 다원주의 평가와 방법은 배포할 준비가 되어 있지 않다. 다른 모델 특성에 미치는 영향을 보고하고 프로덕션 시스템의 요구 사항을 충족하는 평가와 방법이 필요하다. 이러한 장벽은 다원적 정렬에만 해당하지 않으므로, 우리의 로드맵은 유사한 변화 이론을 가진 책임 있는 AI 연구의 다른 분야에도 적용된다. 사람들이 더 많은 의사결정을 AI 시스템에 맡기고 AI 에이전트가 사람을 대신해 행동하는 만큼, 우리는 이 로드맵이 해당 연구가 그러한 결정을 내리는 배포된 모델에 도달하도록 돕기를 바란다.

토론

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