Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Sử dụng giảm thiểu tiền xử lý đôi để tái cấu trúc các ràng buộc tích lũy
Tóm tắt
Các giảm thiểu tiền xử lý đôi là một lớp kỹ thuật tái cấu trúc nhằm loại bỏ các giải pháp khả thi hoặc thậm chí là tối ưu, đồng thời đảm bảo rằng ít nhất một giải pháp tối ưu vẫn tồn tại, miễn là bài toán ban đầu khả thi. Giảm thiểu tiền xử lý và giảm thiểu đôi là các thành phần quan trọng của các giải pháp lập trình tuyến tính nguyên hỗn hợp hiện đại. Trong bài báo này, chúng tôi giới thiệu cả hai dưới dạng các khái niệm thống nhất, thực tiễn trong các giải pháp lập trình ràng buộc. Dựa trên ý tưởng hiện có về khóa biến, chúng tôi định nghĩa chính thức và biện minh cho việc sử dụng thông tin đôi cho các ràng buộc tích lũy trong giai đoạn tiền xử lý của một giải pháp. Cụ thể, khóa biến được sử dụng để phân tách các ràng buộc tích lũy, phát hiện các biến không liên quan, và suy diễn các gán biến và giảm kích thước miền. Vì độ phức tạp tính toán của các thuật toán lan truyền thường phụ thuộc vào số lượng biến và/hoặc kích thước miền, nên các giảm thiểu đôi này là một nguồn tiềm năng để tăng tốc tính toán. Thông qua bằng chứng thực nghiệm về các bài toán lập lịch dự án bị hạn chế tài nguyên, chúng tôi chứng minh rằng các điều kiện cho giảm thiểu đôi xuất hiện trong các trường hợp điểm chuẩn nổi tiếng và rằng một tỷ lệ đáng kể trong số đó có thể được giải quyết đến tối ưu trong giai đoạn tiền xử lý – mà không cần tìm kiếm. Mặc dù chúng tôi coi kết quả này là rất hứa hẹn, nhưng chúng tôi không nhận thấy sự thay đổi đáng kể nào trong thời gian chạy tổng thể do việc sử dụng các giảm thiểu đôi mới của chúng tôi.
Từ khóa
#giảm thiểu tiền xử lý đôi #ràng buộc tích lũy #lập trình ràng buộc #tối ưu hóa #tăng tốc tính toánTài liệu tham khảo
Achterberg, T. (2007). Constraint integer programming. PhD thesis, Technische Universität Berlin.
Achterberg, T. (2009). SCIP: Solving constraint integer programs. Mathematical Programming Computation, 1(1), 1–41.
Aggoun, A., Beldiceanu, N. (1993). Extending chip in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling, 17(7), 57–73.
Artigues, C., Demassey, S., Néron, E., (eds.) (2008). Resource-constrained project scheduling: Models, algorithms, extensions and applications. iSTE
Baptiste, P., & Pape, C.L. (2000). Constraint propagation and decomposition techniques for highly disjunctive and highly cumulative project scheduling problems. Constraints, 5(1–2), 119–139.
Baptiste, P., Pape, C.L., Nuijten, W. (2001). Constraint-based scheduling. Kluwer Academic Publishers.
Baptiste, P., & Pape, C.L. (2005). Scheduling a single machine to minimize a regular objective function under setup constraints. Discrete Optimization, 2(1), 83–99.
Berthold, T., Heinz, S., Lübbecke, M.E., Möhring, R.H., Schulz, J. (2010). A constraint integer programming approach for resource-constrained project scheduling. In Lodi, A., Milano, M., Toth, P., (eds.) Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (vol. 6140, pp. 313–317) of LNCS. Springer.
Berthold, T., Heinz, S., Schulz, J. (2011). An approximative criterion for the potential of energetic reasoning. In Marchetti-Spaccamela, A., Segal, M., (eds.) Theory and Practice of Algorithms in (Computer) systems (vol. 6595, pp. 229–239) of LNCS. Springer.
Bixby, R.E., & Wagner, D.K. (1987). A note on detecting simple redundancies in linear systems. Operation Research Letters, 6(1), 15–17.
Bordeaux, L., Cadoli, M., Mancini, T. (2008). A unifying framework for structural properties of CSPs: definitions, complexity, tractabilit. Journal of Artificial Intelligence Research, 32(1), 607–629.
Borrett, J.E., & Tsang, E.P.K. (2001). A context for constraint satisfaction problem formulation selection. Constraints, 6(4), 299–327.
Chu, G., & Stuckey, P.J. (2012). A generic method for identifying and exploiting dominance relations. In Milano, M., (ed.) Principles and practice of constraint programming - CP 2012 (vol. 7514, pp. 6–22) of LNCS.
Dantzig, G.B., & Thapa, M.N. (2003). Linear programming 2. Springer Series in Operations Research. Springer.
de la Banda, M.J.G., Marriott, K., Rafeh, R., Wallace, M. (2006). The modelling language Zinc. In Benhamou, F., (ed.) Principles and practice of constraint programming - CP 2006 (vol. 4204, pp. 700–705). LNCS.
Dechter, R. (2003). Constraint processing. Elsevier Morgan Kaufmann.
Frisch, A.M., Harvey, W., Jefferson, C., Martínez-Hernández, B., Miguel, I. (2008). ESSENCE: A constraint language for specifying combinatorial problems. Constraints, 13, 268–306.
Gent, I.P., Petrie, K.E., Puget, J.F. (2006). Symmetry in constraint programming. In Handbooks of constraint programming. Elsevier.
Gent, I.P., Miguel, I., Rendl, A. (2007). Tailoring solver-independent constraint models: a case study with ESSENCE and MINION. In Miguel, I., Ruml, W., (eds.) Abstraction, Reformulation, and Approximation (vol. 4612, pp. 184–199) of LNCS.
Guzelsoy, M. (2010). Dual methods in mixed integer linear programming. PhD thesis, Lehigh University,Industrial and Systems Engineering.
Heinz, S., & Schulz, J. (2011). Explanations for the cumulative constraint: An experimental study. In Pardalos, P.M., Rebennack, S. (eds.) Experimental algorithms (vol. 6630, pp. 400–409) of LNCS. Springer.
Imbert, J.L., & Hentenryck, P.V. (1996). Redundancy elimination with a lexicographic solved form. Annals of Mathematics and Artificial Intelligence, 17(1–2), 85–106.
Karwan, M.H., Lotfi, V., Telgen, J., Zionts, S. (1983). Redundancy in mathematical programming. A state-of-the-art survey. Volume 206 of Lecture Notes in Economics and Mathematical Systems. Springer.
Kiziltan, Z. (2004). Symmetry breaking ordering constraints: Thesis. AI Communications, 17, 167–169.
Klein, R., & Scholl, A. (1999). Computing lower bounds by destructive improvement: An application to resource-constrained project scheduling. European Journal of Operational Research, 112(2), 322–346.
Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D.E., Wolter, K. (2011). MIPLIB 2010. Mathematical Programming Computation, 3(2), 103–163.
Laurière, J.L. (1978). A language and a program for stating and solving combinatorial problems. Artificial Intelligence, 10(1), 29–127.
Mahajan, A. (2010). Presolving mixed-integer linear programs. Preprint ANL/MCS-P1752-0510, Mathematics and Computer Science Division.
Marriott, K., Nethercote, N., Rafeh, R., Stuckey, P.J., de la Banda, M.G., Wallace, M. (2008). The design of the zinc modelling language. Constraints, 13(3), 229–267.
Möhring, R.H., Schulz, A.S., Stork, F., Uetz, M. (2003). Solving project scheduling problems by minimum cut computations. Management Science, 49(3), 330–350.
Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G. (2007). MiniZinc: Towards a standard CP modelling language. In Bessiere, C., (ed.) Principles and Practice of Constraint Programming - CP 2007 (vol. 4741, pp. 529–543) of LNCS. Springer.
Pesant, G., Quimper, C., Zanarini, A. (2012). Counting-based search: Branching heuristics for constraint satisfaction problems. Journal of Artificial Intelligence Research, 43, 173–210.
Prestwich, S.D., & Beck, J.C. (2004). Exploiting dominance in three symmetric problems. In Proceedings of the fourth international workshop on symmetry and constraint satisfaction problems.
PSPLib: Project scheduling problem library. http://129.187.106.231/psplib/.
Puget, J.F. (2005). Automatic detection of variable and value symmetries. In van Beek, P. (ed.) Principles and practice of constraint programming - CP 2005 (vol. 3709, pp. 475–489) of LNCS.
Rendl, A. (2010). Effective compilation of constraint models. PhD thesis, University of St Andrews.
Savelsbergh, M.W.P. (1994). Preprocessing and probing techniques for mixed integer programming problems. ORSA Journal on Computing, 6, 445–454.
Schutt, A., Feydy, T., Stuckey, P.J., Wallace, M.G. (2012). Solving rcpsp/max by lazy clause generation. Journal of Scheduling. (accepted).
van Hoeve, W.J. (2001). The all different constraint: A survey. CoRR cs.PL/0105015.
Vilím, P. (2009). Max energy filtering algorithm for discrete cumulative resources. In van Hoeve, W.J., Hooker, J.N. (eds.) Integration of AI and OR techniques in constraint programming for combinatorial optimization problems (vol. 5547, pp. 294–308) of LNCS.
Yunes, T., Aron, I.D., Hooker, J.N. (2010). An integrated solver for optimization problems. Operations Research, 58(2), 342–356.