Enhancements on the hyperplanes arrangements in mixed-integer programming techniques. (English) Zbl 1256.90029
Summary: This paper is concerned with improvements in constraints handling for mixed-integer optimization problems. The novel element is the reduction of the number of binary variables used for expressing the complement of a convex (polytopic) region. As a generalization, the problem of representing the complement of a possibly not connected union of such convex sets is detailed. In order to illustrate the benefits of the proposed improvements, a typical control application, the control of multiagent systems using receding horizon optimization techniques, is considered.
MSC:
| 90C11 | Mixed integer programming |
Keywords:
mixed integer programming (MIP); non-convex constraints; hyperplane arrangements; cell mergingSoftware:
cddReferences:
| [1] | Grundel, D., Murphey, R., Pardalos, P.: Cooperative Systems, Control and Optimization, vol. 588. Springer, Berlin (2007) · Zbl 1110.93005 |
| [2] | Grundel, D., Pardalos, P.: Theory and Algorithms for Cooperative Systems, vol. 4. World Scientific, Singapore (2004) · Zbl 1091.90002 |
| [3] | Earl, M., D’Andrea, R.: Modeling and control of a multi-agent system using mixed integer linear programming. In: Proceedings of the 40th IEEE Conference on Decision and Control, Orlando, Florida, USA, vol. 1, pp. 107–111 (2001) |
| [4] | Osiadacz, A.: Integer and combinatorial optimization. In: Nemhauser, G.L., Wolsey, L.A. (eds.) Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1988). International Journal of Adaptive Control and Signal Processing, 4(4), 333–344 (1990) |
| [5] | Jünger, M., Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G., Wolsey, L.: 50 Years of Integer Programming 1958–2008: From the Early Years to the State-of-the-Art. Springer, Berlin (2009) · Zbl 1181.90003 |
| [6] | Schouwenaars, T., De Moor, B., Feron, E., How, J.: Mixed integer programming for multi-vehicle path planning. In: Proceedings of the 2nd IEEE European Control Conference, Porto, Portugal, pp. 2603–2608. (2001) |
| [7] | Richards, A., How, J.: Model predictive control of vehicle maneuvers with guaranteed completion time and robust feasibility. In: Proceedings of the 24th American Control Conference, Portland, Oregon, USA, vol. 5, pp. 4034–4040 (2005) |
| [8] | Ousingsawat, J., Campbell, M.: Establishing trajectories for multi-vehicle reconnaissance. In: Proceedings of AIAA Guidance, Navigation and Control Conference, Providence, Rhode Island, USA, pp. 2188–2199 (2004) |
| [9] | Beard, R., McLain, T., Goodrich, M., Anderson, E.: Coordinated target assignment and intercept for unmanned air vehicles. Proc. IEEE Trans. Robot. Autom. 18(6), 911–922 (2002) · doi:10.1109/TRA.2002.805653 |
| [10] | Richards, A., Bellingham, J., Tillerson, M., How, J.: Coordination and control of multiple UAVS. In: Proceedings of AIAA Guidance, Navigation and Control Conference. Monterey, CA (2002) |
| [11] | Schumacher, C., Chandler, P., Pachter, M.: UAV task assignment with timing constraints. In: Proceedings of AIAA Guidance, Navigation and Control Conference, Austin, Texas (2003) |
| [12] | Bemporad, A., Morari, M.: Control of systems integrating logic, dynamics, and constraints. Automatica 35, 407–428 (1999) · Zbl 1049.93514 · doi:10.1016/S0005-1098(98)00178-2 |
| [13] | Bemporad, A., Borrelli, F., Morari, M.: Optimal controllers for hybrid systems: stability and piecewise linear explicit form. In: Proceedings of the 39th IEEE Conference on Decision and Control, Sydney, NSW, Australia, pp. 1810–1815 (2000) |
| [14] | Mayne, D., Rawlings, J., Rao, C., Scokaert, P.: Constrained model predictive control: stability and optimality. Automatica 36, 789–814 (2000) · Zbl 0949.93003 · doi:10.1016/S0005-1098(99)00214-9 |
| [15] | Camacho, E.F., Bordons, C.: Model Predictive Control. Springer, Berlin (2004) |
| [16] | Bellingham, J., Richards, A., How, J.: Receding horizon control of autonomous aerial vehicles. In: Proceedings of the 21th American Control Conference, Anchorage, Alaska, USA, vol. 5, pp. 3741–3746 (2002) |
| [17] | Prodan, I., Olaru, S., Niculescu, S.: Predictive control for tight group formation of multi-agent systems. In: Proceedings of the 18th IFAC World Congress, Milano, Italy, pp. 138–143 (2011) |
| [18] | Stoican, F., Olaru, S., Seron, M., De Doná, J.: Reference governor for tracking with fault detection capabilities. In: Proceedings of the 2010 Conference on Control and Fault Tolerant Systems, Nice, France, pp. 546–551 (2010) |
| [19] | Garey, M., Johnson, D.: Computers and intractability. A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. Freeman, San Francisco (1979) · Zbl 0411.68039 |
| [20] | Earl, M., D’Andrea, R.: Iterative MILP methods for vehicle-control problems. IEEE Trans. Robot. 21(6), 1158–1167 (2005) · doi:10.1109/TRO.2005.853499 |
| [21] | Vitus, M., Pradeep, V., Hoffmann, G., Waslander, S.L., Tomlin, C.J.: Tunnel-milp: path planning with sequential convex polytopes. In: Proceedings of AIAA Guidance, Navigation and Control Conference, Honolulu, Hawaii, USA (2008) |
| [22] | Stoican, F., Prodan, I., Olaru, S.: On the hyperplanes arrangements in mixed-integer techniques. In: Proceedings of the 30th American Control Conference, San Francisco, CA, USA, pp. 1898–1903 (2011) · Zbl 1256.90029 |
| [23] | Stoican, F., Prodan, I., Olaru, S.: Enhancements on the hyperplane arrangements in mixed integer techniques. In: 50th IEEE Conference on Decision and Control and European Control Conference, Orlando, FL, USA, pp. 3986–3991 (2011) |
| [24] | Olaru, S., Dumur, D.: Avoiding constraints redundancy in predictive control optimization routines. IEEE Trans. Autom. Control 50(9), 1459–1465 (2005) · Zbl 1365.93159 · doi:10.1109/TAC.2005.854659 |
| [25] | Orlik, P., Terao, H.: Arrangements of Hyperplanes, vol. 300. Springer, Berlin (1992) |
| [26] | Ziegler, G.: Lectures on Polytopes. Springer, Berlin (1995) · Zbl 0823.52002 |
| [27] | Orlik, P.: Hyperplane arrangements. In: Floudas, C.A., Orlik, P.M. (eds.) Encyclopedia of Optimization, pp. 1545–1547. Springer, New York (2009) |
| [28] | Pardalos, P.: Hyperplane arrangements in optimization. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 1547–1548. Springer, New York (2009) |
| [29] | Buck, R.: Partition of Space. Am. Math. Mon. 50(9), 541–544 (1943) · Zbl 0061.30609 · doi:10.2307/2303424 |
| [30] | Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65(1), 21–46 (1996) · Zbl 0854.68070 · doi:10.1016/0166-218X(95)00026-N |
| [31] | Ferrez, J.A., Fukuda, K.: Implementations of lp-based reverse search algorithms for the zonotope construction and the fixed-rank convex quadratic maximization in binary variables using the zram and the cddlib libraries. Tech. rep., Mcgill (2002) |
| [32] | Kobayashi, K., Imura, J.: Modeling of discrete dynamics for computational time reduction of Model Predictive Control. In: Proceedings of the 17th International Symposium on Mathematical Theory of Networks and Systems, Kyoto, Japan, pp. 628–633 (2006) |
| [33] | Zaslavsky, T.: Counting the faces of cut-up spaces. Am. Math. Soc. 81, 5 (1975) · Zbl 0317.05012 |
| [34] | Geyer, T., Torrisi, F., Morari, M.: Optimal complexity reduction of piecewise affine models based on hyperplane arrangements. In: Proceedings of the 23th American Control Conference, Boston, Massachusetts, USA, vol. 2, pp. 1190–1195 (2004) |
| [35] | Geyer, T., Torrisi, F., Morari, M.: Optimal complexity reduction of polyhedral piecewise affine systems. Automatica 44(7), 1728–1740 (2008) · Zbl 1149.93303 · doi:10.1016/j.automatica.2007.11.027 |
| [36] | Rudell, R., Sangiovanni-Vincentelli, A.: Espresso-mv: algorithms for multiple-valued logic minimization. In: Proceedings of the IEEE Custom Integrated Circuits Conference, pp. 230–234 (1985) |
| [37] | Olfati-Saber, R., Murray, R.: Distributed cooperative control of multiple vehicle formations using structural potential functions. In: Proceedings of the 15th IFAC World Congress, Barcelona, Spain pp. 346–352 (2002) |
| [38] | Rimon, E., Koditschek, D.: Exact robot navigation using artificial potential functions. IEEE Trans. Robot. Autom. 8(5), 501–518 (1992) · doi:10.1109/70.163777 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
