arXiv:2502.02688

Efficient Implementation of the Global Cardinality Constraint with Costs

Margaux Schmied, Jean-Charles Regin

제출 2025-02-04

원문 초록

The success of Constraint Programming relies partly on the global constraints and implementation of the associated filtering algorithms. Recently, new ideas emerged to improve these implementations in practice, especially regarding the all different constraint. In this paper, we consider the cardinality constraint with costs. The cardinality constraint is a generalization of the all different constraint that specifies the number of times each value must be taken by a given set of variables in a solution. The version with costs introduces an assignment cost and bounds the total sum of assignment costs. The arc consistency filtering algorithm of this constraint is difficult to use in practice, as it systematically searches for many shortest paths. We propose a new approach that works with upper bounds on shortest paths based on landmarks. This approach can be seen as a preprocessing. It is fast and avoids, in practice, a large number of explicit computations of shortest paths.

함께 살펴볼 논문

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

arXiv:2410.24145v3stat.ML공통 태그 ARC공식 코드 · Papers with Code

원형 데이터에 대한 투영 랜덤 포레스트와 준비 예측

Projected random forests and conformal prediction of circular data

우리는 원형 반응 변수를 갖는 회귀 문제에 준비 예측 기법을 적용하여, 데이터 교환 가능성 가정 하에 임의의 원형 예측 모델에 대해 적응형 호 길이와 유한 표본 커버리지 보장을 갖는 예측 집합을 생성합니다. 선형 반응 변수를 위해 설계된 기존 예측 모델의 높은 성능을 활용하여, 임의의 선형 반응 회귀 모델을 원형 반응 변수에 적합한 모델로 변환하는 일반적인 투영 절차를 분석합니다. 이 투영 절차에서 랜덤 포레스트를 기본 모델로 사용할 경우, 예측 집합 구성 시 별도의 보정 샘플이 필요 없도록 랜덤 포레스트의 OOB(Out-of-Bag) 메커니즘을 활용합니다. 합성 및 실제 데이터셋에서 결과적으로 도출된 투영 랜덤 포레스트 모델은, 기존의 두 가지 대안 모델이 생성한 분할 준비 예측 집합보다 더 짧은 중앙값 호 길이를 가지는 더 효율적인 OOB 준비 예측 집합을 생성합니다.

토론

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