요긴소프트

이전 글에 이어서 제약조건을 설정하고 최적화를 실행하는 부분을 설명하겠습니다. # 제약조건 for i in range(n): model.Add(xb1[i] == x[i] + b[i]*W) model.Add(xb2[i] == xb1[i] + w[i]) model.AddNoOverlap2D(xival,yival) model.AddMaxEquality(z,[b[i] for i in range(n)]) # 목적함수 model.Minimize(z) # 모델 최적화 solver = cp_model.CpSolver() # 로그 남기기 solver.parameters.log_search_progress = True # search worker 개수 지정 - 멀티스레드 #solver.parameters.num_searc..

2D bin packing(상자 채우기) 문제는 2차원 평면에 사각형의 객체를 적절히 채우는 문제입니다. 이 문제를 푸는 방법은 상당히 여러가지가 있는 것 같습니다. 여기말고 '티바이트' 라는 분의 블로그에 상당히 자세한 알고리즘 풀이가 있으니, 궁금하신 분들은 참고하시면 좋을 것 같습니다. 이 글에서는 OrTools의 CP-SAT 솔버를 통해 문제를 해결하는 방법을 보여드립니다. 아래 소스의 대부분은 "Yet Another Math Programming Consultant"라는 분의 블로그의 글을 참고했습니다. 우선 결과부터 보여드리면 아래와 같습니다. 너비 68, 높이 60 영역에 50개에 서로 크기가 같거나 다른 상자를 채운 모습입니다. 소스는 크게 4부분으로 나누어 집니다. 데이터 정의 제약 조건..

이전 글에서 orTools로 n-Queens 솔루션을 찾는 방법을 설명했습니다. 이번 글에서는 지난 번 글에 이어지는 글로 솔루션의 결과를 출력하는 방법을 소개합니다. ### 모델 해결 solver = cp_model.CpSolver() ### 모델 다이어그램 출력 printer = DiagramPrinter(queens) ### 모델 다이어그램 출력 status = solver.SearchForAllSolutions(model, printer) print() print('찾은 솔루션 개수 : %i' % printer.SolutionCount()) print("걸린 시간: ", solver.WallTime(), "ms") 지난 번 소스 맨 마지막 부분을 보면 solver를 통해 솔루션을 찾기에서 Diag..

N-Queens 문제는 가로, 세로 칸의 수가 동일한 체스판 모든 행에 서로 공격할 수 없는 퀸을 배치하는 문제입니다. 이 문제에 대한 자세한 정보는 위키백과에서 확인 할 수 있습니다. 아래는 OrTools 최적화 도구를 이용해 N-Queens 문제를 푸는 python 소스입니다. import sys # CP-SAT 솔버 from ortools.sat.python import cp_model def main(board_size): model = cp_model.CpModel() # 변수 생성 # 배열의 인덱스는 열(column), 값은 행(Row) queens = [model.NewIntVar(0, board_size - 1, 'x%i' % i) for i in range(board_size)] # 제약..

Google Optimization Tools로 구글에서 만들어 무료(open-source)로 배포하고 있는 최적화 도구입니다. 최적화 도구란 여러가지 선택 가능한 문제를 수학적 모델로 정의하고 가장 나은 선택을 제시해 주는 프로그램이라고 할 수 있다. 예를 자주 드는 N-Queen 문제가 있다. 크기가 N x N 인 체스판 위에 퀸 N 개가 서로를 공격 할 수 없게 놓는 경우의 수를 구하는 문제 체스에서 퀸은 대각선과 가로, 세로로 공격할 수 있다. 그러면 N x N 크기의 체스판에서 공격할 수 없게 놓을 수 있는 퀸 배치 경우의 수는 몇개인가? N-Queens 문제는 최적화라기보다 가능한 모든 경우의 수를 구하는 문제이지만, 최대값, 최소값을 구하는 문제도 Or-Tools를 통해 구할 수 있다. Or..

아나콘다를 이용해 python 가상 개발환경을 관리할 수 있다. python 개발 가상환경이 필요한 이유는 하나의 컴퓨터에 여러개의 python 프로젝트(프로그램)을 작성하면, 각각의 프로젝트에서 다양한 버전의 모듈 설치가 필요한 경우가 생긴다. 그리고 여러명의 개발자가 하나의 프로젝트를 협업할 때, 동일한 가상개발 환경을 구성해 소스 통합 시 모듈 버전 충돌문제를 발생하지 않도록 해준다. 아나콘다 설치는 아나콘다 홈페이지에서 자신의 개발 머신에 맞는 설치파일을 다운받아 설치하면 된다. 가상환경 생성하기 conda create -n python= 가상환경 내보내기 conda env export > 가상환경파일명.yml 가상환경 불러오기 conda env create --file 가상환경파일이름.yml 내..

Shapely 라이브러리는 기하학적 객체를 읽고, 쓰고, 분석하는 일을 하지만 해당 객체를 그려주지는 않는다. Python에서 matplotlib는 도형정보를 그리는 모듈 중 하나인데, 이를 이용해 shapely의 기하정보를 그릴 수 있다. 설치 방법은 pip install matplotlib 하면 설치된다. import matplotlib.pyplot as plt from shapely.geometry import Polygon fig, ax = plt.subplots() # Create Polygon exterior = [(20, 20), (50, 70), (80, 20)] poly = Polygon(exterior) # Plot Polygon xe, ye = poly.exterior.xy ax.pl..

WKT(Well Known Text) 포맷은 이름대로 직관적으로 도형의 정보를 알 수 있는 포맷이다. GEOS에서 소개된 WKT 포맷의 예는 아래와 같다. POINT(0 0) POINT EMPTY LINESTRING(0 0, 0 1, 1 2) LINESTRING EMPTY POLYGON((0 0, 1 0, 1 1, 0 1, 0 0)) POLYGON((0 0, 4 0, 4 4, 0 4, 0 0), (1 1, 1 2, 2 2, 2 1, 1 1)) POLYGON EMPTY MULTIPOINT(0 0, 1 1) GEOMETRYCOLLECTION(MULTIPOINT(0 0, 1 1), POINT(3 4), LINESTRING(2 3, 3 4)) 점(POINT), 선(LINESTRING), 면(POLYGON), 다..

shapely에서 bouding box 쉽게 만들기 # shapely 설치후 box 클래스 import from shapely.geometry import box b = box(0.0, 0.0, 200, 100) print(b.wkt) # print 결과 : POLYGON ((200 0, 200 100, 0 100, 0 0, 200 0)) list(b.exterior.coords) # 결과 : [(200.0, 0.0), (200.0, 100.0), (0.0, 100.0), (0.0, 0.0), (200.0, 0.0)] # 기타 도형의 bounding box로 shapely.geometry.box 폴리곤 만들기 pbox = box(*myPolygon.bounds, ccw=True) ※ shapely 설치 ..

Shapely는 기하학적인 객체의 조작 및 분석을 위한 파이썬 라이브러리입니다. Manipulation and analysis of geometric objects 현재 Github에서 꾸준히 업데이트 관리되고 있습니다. 소개에 따르면 널리 사용하고 있는 오픈 소스 기하학 라이브러리인 GEOS(PostGIS, JTS 등에서 사용)를 사용하고 있다고 합니다. Shapely 2.0 이상 버전을 사용하시려면 Python 은 3.7이상, GEOS는 3.5이상, NumPy는 1.14 이상 버전이 설치되어 있거나 설치하면 됩니다. 설치방법은 간단히 pip install shapely 를 통해 할 수 있고, conda 환경이라면 conda install shapely --channel conda-forge 를 통해서..