Lập trình số nguyên trong Python

Bởi 4 lượt xem

Bài viết đăng tại: https://programming.laptrinh.site

Một bài toán Lập trình số nguyên là một bài toán được xây dựng để đảm bảo tính khả thi hoặc tối ưu hóa toán học bằng cách cung cấp rằng một số hoặc tất cả các biến liên quan đến vấn đề là số nguyên.

Giả sử một số biến quyết định trong bài toán được tìm thấy là không rời rạc. Trong trường hợp đó, chúng được phân loại là bài toán hỗn hợp số nguyên, thường được gọi là MIP/MILP (Lập trình tuyến tính số nguyên hỗn hợp).

Vì vậy, trong bài viết này về Python, chúng ta sẽ khám phá các phương pháp và thư viện khác nhau mà chúng ta có thể sử dụng để giải quyết các loại vấn đề này trong Python.

Các vấn đề về lập trình số nguyên hỗn hợp trong Python

Bài toán lập trình hỗn hợp số nguyên ( MIP ) là bài toán trong đó một số biến quyết định được đảm bảo là các giá trị nguyên nghiêm ngặt để có lời giải tối ưu.

Việc sử dụng các biến số nguyên này sẽ mở rộng phạm vi và điểm số của các vấn đề tối ưu hóa hữu ích mà một lập trình viên có thể sử dụng để xác định và giải quyết một cách hiệu quả và chính xác nhất.

Một kịch bản thiết yếu trong MIP là biến quyết định được coi là nhị phân; nói cách khác, nó chỉ có thể được biểu diễn dưới dạng 0 hoặc 1 .

Chúng thường được gọi là Giá trị số nguyên nhị phân. Các biến quyết định này thường được sử dụng để mô hình hóa các quyết định True / False hoặc Yes / No dựa trên các tính toán cẩn thận.

Bây giờ có một số bộ giải được thiết kế để giải quyết các loại vấn đề này.

Chúng bao gồm Gurobi và Python-MIP tiên tiến nhất, trong số các bộ giải quy hoạch tuyến tính số nguyên hỗn hợp được biết đến và tìm kiếm phổ biến nhất.

Một bộ giải MIP có cấu hình cao khác là bộ giải CBC hoặc COIN-OR Branch-&-Cut . Cuối cùng, Python-MIP giúp việc phát triển các bộ giải dựa trên MIP, hiệu suất cao cho bất kỳ ứng dụng tùy chỉnh nào trở nên dễ dàng.

Nó cung cấp các tính năng cao cấp và hiện đại, được mô tả và giải thích đầy đủ chi tiết bên dưới.

Công cụ Python cho MIP/MILP : Python-MIP

Trong Python, chúng ta có một thư viện rộng lớn gọi là MIP , về cơ bản là một tập hợp các công cụ dựa trên Python để lập mô hình và giải các bài toán lập trình tuyến tính hỗn hợp nguyên.

Với cú pháp lấy cảm hứng rất nhiều từ Pulp , MIP cung cấp cho người dùng quyền truy cập vào các tính năng nâng cao và hiệu quả như lazy constraints , MIPstart , nhóm solution pools và cut generation .

Nhiều tính năng nổi bật của nó bao gồm:

  • Mô hình cấp cao

    Hầu hết các lập trình viên đã phát triển kỹ năng mô hình hóa bằng ngôn ngữ lập trình cấp cao vì nó dễ dàng. Tuy nhiên, chúng ta có thể viết các MIP models của mình bằng Python một cách nhanh chóng.

    Tính năng nạp chồng toán tử giúp toàn bộ quá trình viết biểu thức tuyến tính mượt mà hơn nhiều trong Python.

  • tính năng đóng gói

    Với các tính năng như trình cut generators và lazy constraints , lập trình viên có thể làm việc với các công thức vững chắc bằng cách sử dụng nhiều ràng buộc.

    Nó chỉ tạo ra các bất đẳng thức cần thiết trong quá trình tìm kiếm branch and cut . Sau đó, để bổ sung, bạn có thể truy vấn vào nhóm solution pool để trích xuất hoặc xem qua các giải pháp hàng đầu được tìm thấy trong quá trình tìm kiếm.

    Hơn nữa, MIPstart cho phép lập trình viên ban đầu sử dụng phương pháp phỏng đoán phụ thuộc vào vấn đề để tạo ra các giải pháp khả thi cho việc tìm kiếm MIP .

  • Nhanh & Hiệu quả

    Gói MIP trong Python thực hiện call trực tiếp đến thư viện có thể tải động gốc của bộ giải đã được cài đặt bằng cách sử dụng CFFI module .

    Các mô hình này được bộ giải lưu trữ và thực hiện hiệu quả. Trong khi đó, MIP liên quan đến việc giao tiếp với mã của bạn. Trong khi giao diện Gurobi Python chính thức cũng cung cấp các tính năng để xử lý MILP , thư viện MIP trong Python tương thích với Pypy .

    Nó có thể chạy nhanh hơn 25 lần so với nó, vì hiệu suất của nó chỉ dựa trên CPython .

  • đa giải quyết

    MIP trong Python được xây dựng để tích hợp hoàn toàn với các C-based libraries của bộ giải COIN-OR Branch-&-Cut và Gurobi .

    Với MIP , bạn không phải lo lắng về việc viết một phương tiện để liên lạc giữa các bộ giải khác nhau, vì nó đã được xử lý trong thư viện Python-MIP .

    Bạn chỉ cần viết một mã duy nhất, độc lập với bộ giải.

  • Được trang bị các phiên bản Python mới nhất

    Như đã đề cập ở trên, MIP tương thích với Python phiên bản 3.6 trở lên, vì vậy chúng tôi không phải lo lắng về sự dư thừa làm chậm tốc độ của bạn.

Bây giờ bạn đã biết Lập trình số nguyên hỗn hợp là gì và các bộ giải khác nhau có sẵn để hướng dẫn bạn qua bất kỳ vấn đề lập trình số nguyên nào có thể cần giải theo cách tối ưu hóa hữu ích và hiệu quả nhất.

Bạn cũng có thể khám phá tài liệu chính thức về tất cả các bộ giải được đề cập để tìm giải pháp cho vấn đề cụ thể của mình.

Bài viết liên quan

  1. Bỏ qua các lần lặp lại trong vòng lặp Python
  2. Chuyển chuỗi thành số nguyên trong Python
  3. Chuyển đổi danh sách chuỗi thành số nguyên trong Python
  4. Tạo một số nguyên tố ngẫu nhiên trong Python
  5. Python Khắc phục sự cố bộ nhớ dùng chung & Khóa tài nguyên dùng chung
  6. Chuyển đổi Int sang nhị phân trong Python
  7. Truy cập Chỉ mục trong Vòng lặp 'Foreach' bằng Python
  8. Khắc phục lỗi lặp qua lỗi mảng 0-D trong Python NumPy

URL Link

https://laptrinh.site/lap-trinh-so-nguyen-trong-python/

Viết bởi Duy Mạnh. Đã đăng ký bản quyền tác giả tại Creativecommons và DMCA