Về vấn đề lưu thông chung:
Tôi đồng ý với @Helen; mặc dù nó có thể không trực quan để thụ thai về việc sử dụng thực tế của giới hạn dưới, nhưng đó là một ràng buộc rằng phải đáp ứng được. Tôi không tin rằng bạn sẽ có thể bỏ qua hạn chế này, ngay cả khi dòng chảy đó bằng không.
Trường hợp dòng = 0 kháng cáo vấn đề luồng tối đa trực quan hơn (như được chỉ ra bởi @KillianDS). Trong trường hợp đó, nếu lưu lượng giữa một cặp nút bằng 0, thì chúng không thể ảnh hưởng đến "bảo toàn tổng lưu lượng": 
Khi không có giới hạn dưới nào (giả thiết luồng không âm) chảy không thể ảnh hưởng đến kết quả, vì
- nó không thể giới thiệu một sự vi phạm đến những hạn chế
- nó không thể ảnh hưởng đến sự sum (vì nó cho biết thêm một thuật ngữ không).
Ví dụ thực tế về lưu lượng tối thiểu có thể tồn tại do một số ràng buộc bên ngoài (một vấn đề liên quan yêu cầu ít nhất X nước đi qua một đường ống nhất định, như được chỉ ra bởi @Helen). Các ràng buộc giới hạn dưới cũng có thể phát sinh từ một vấn đề kép tương đương, làm giảm thiểu dòng chảy sao cho các cạnh nhất định có giới hạn thấp hơn (và tìm ra một tương đương tối ưu cho một vấn đề tối đa với giới hạn trên).
Đối với vấn đề cụ thể của bạn:
Nó có vẻ như bạn đang cố gắng để có được càng nhiều sự kiện thực hiện trong một tập cố định các khe thời gian (nơi không có hai sự kiện có thể chồng lên nhau trong một khe thời gian).
Hãy xem xét các bộ khe thời gian có thể được gán cho một sự kiện nhất định:
E1 - {09:10}
E2 - {09:00}
E3 - {9 : 20, 9:30, 9:40, 9:50}
E3 - {9:00, 9:10, 9:20, 9:30}
Vì vậy, bạn muốn tối đa hóa số của nhiệm vụ phân công (tức là sự kiện sự kiện để cạnh được bật "trên") st các tập kết quả được phân tách theo cặp (nghĩa là không có khe thời gian được gán chồng lên nhau).
Tôi tin rằng đây là NP-Hard bởi vì nếu bạn có thể giải quyết vấn đề này, bạn có thể sử dụng nó để giải quyết maximal set packing problem (tức là bộ đóng gói tối đa giảm xuống mức này). Vấn đề của bạn có thể được giải quyết với lập trình tuyến tính số nguyên, nhưng trong thực tế những vấn đề này cũng có thể được giải quyết rất tốt với các phương pháp tham lam/nhánh và bị ràng buộc.
Ví dụ: trong ví dụ của bạn. sự kiện E1 "xung đột" với xung đột E3 và E2 với E3. Nếu E1 được chỉ định (chỉ có một tùy chọn), thì chỉ có một nhiệm vụ có thể còn lại của E3 (bài tập sau). Nếu nhiệm vụ này được thực hiện cho E3, thì chỉ có một nhiệm vụ còn lại cho E2. Hơn nữa, các biểu đồ con rời rạc (các tập hợp các sự kiện không thể xung đột với các tài nguyên) có thể được giải quyết một cách riêng biệt.
Nếu đó là tôi, tôi sẽ bắt đầu với một giải pháp tham lam rất đơn giản (chỉ định nhiệm vụ với ít "khe" nhất), và sau đó sử dụng nó làm hạt giống cho chi nhánh và bộ giải kết buộc (nếu giải pháp tham lam tìm thấy 4 nhiệm vụ nhiệm vụ, sau đó bị ràng buộc nếu bạn đệ quy subtree của bài tập không thể vượt quá 3). Bạn thậm chí có thể ép ra một số hiệu suất bổ sung bằng cách tạo ra đồ thị của các giao điểm cặp giữa các bộ và chỉ thông báo cho các bộ liền kề khi một phép gán được thực hiện. Bạn cũng có thể cập nhật số bài tập tốt nhất khi bạn tiếp tục nhánh và bị ràng buộc (tôi nghĩ điều này là bình thường), vì vậy nếu bạn may mắn sớm, bạn hội tụ nhanh chóng.
Tôi đã sử dụng ý tưởng tương tự này để tìm tập hợp protein nhỏ nhất có thể giải thích một tập hợp các peptide được xác định (các phần protein) và nhận thấy nó là quá đủ cho các vấn đề thực tế. Đó là một vấn đề rất giống nhau.
Nếu bạn cần hiệu suất cạnh chảy máu: Khi được lặp lại, lập trình tuyến tính số nguyên có thể thực hiện gần như bất kỳ biến thể nào của sự cố mà bạn muốn. Tất nhiên, trong trường hợp rất xấu nó có thể chậm (trong thực tế, nó có thể sẽ làm việc cho bạn, đặc biệt là nếu đồ thị của bạn không phải là rất mật độ kết nối). Nếu không, thường xuyên lập trình tuyến tính thư giãn gần đúng các giải pháp cho ILP và nói chung là khá tốt cho loại vấn đề.
Hy vọng điều này sẽ hữu ích.
fyi: lưu lượng tối đa là một sự cố lưu thông đặc biệt trong đó giới hạn dưới là bằng không. Chúng không giống nhau. – KillianDS
Đã xóa thẻ. Cảm ơn! –
Giới hạn dưới có thể chỉ có nghĩa là người dùng yêu cầu phải có ít nhất X luồng trong một đường ống để nó có ích cho họ? Ví dụ, nếu họ đang cố gắng cấp năng lượng cho một thứ gì đó từ dòng chảy? Hãy suy nghĩ các nhà máy nước hoặc bóng đèn hay gì đó. (Đó là cách nó hoạt động trong đầu của tôi anyway.) – Helen