Generalized filtering algorithms for infeasibility analysis. (English) Zbl 1278.90007
Summary: We present generalized filtering algorithms for debugging linear, mixed integer and nonlinear infeasible programs. Given a set of constraints that are infeasible or inconsistent, we give algorithms to identify a minimal subset of these constraints that are inconsistent. The algorithms combine existing filtering algorithms with a binary-search based divide-and-conquer approach to improve search speed. We give computational results to show the speed of the algorithms on various problem types.
MSC:
| 90-04 | Software, source code, etc. for problems pertaining to operations research and mathematical programming |
| 90C26 | Nonconvex programming, global optimization |
| 90C11 | Mixed integer programming |
References:
| [1] | van Loon, J., Irreducibly inconsistent systems of linear inequalities, European Journal of Operational Research, 8, 283-288 (1981) · Zbl 0468.90041 |
| [2] | Gleeson, J.; Ryan, J., Identifying minimally infeasible subsystems of inequalities, ORSA Journal of Computing, 2, 1, 61-63 (1990) · Zbl 0752.90050 |
| [3] | Chinneck, J. W.; Dravnieks, E. W., Locating minimal infeasible constraint sets in linear programs, ORSA Journal on Computing, 3, 157-168 (1991) · Zbl 0755.90055 |
| [4] | Tamiz, M.; Mardle, S.; Jones, D., Detecting is in infeasible linear programmes using techniques from goal programming, Computers and Operations Research, 23, 113-119 (1996) · Zbl 0868.90080 |
| [5] | Guieu, O.; Chinneck, J. W., Analyzing infeasible mixed integer and integer linear programs, INFORMS Journal on Computing, 11, 63-77 (1999) · Zbl 1034.90519 |
| [6] | Chinneck, J. W., Analyzing infeasible nonlinear programs, Computational Optimization and Applications, 4, 167-179 (1995) · Zbl 0822.90123 |
| [7] | Andersen, E. D., On primal and dual infeasibility certificates in a homogeneous model for convex optimization, SIAM Journal on Optimization, 11, 2, 380-388 (2000) · Zbl 1010.90055 |
| [8] | Chinneck, J. W., Computer codes for the analysis of infeasible linear programs, Journal of the Operational Research Society, 47, 61-72 (1996) · Zbl 0842.90079 |
| [9] | Chinneck, J. W., Finding a useful subset of constraints for analysis in an infeasible linear program, INFORMS Journal on Computing, 9, 2, 164-174 (1997) · Zbl 0885.90077 |
| [10] | Lindo Systems, Inc. LINDO API User’s Guide, Version 4.0, \(2005. \langle;\) http://www.lindo.com \(\rangle;\).; Lindo Systems, Inc. LINDO API User’s Guide, Version 4.0, \(2005. \langle;\) http://www.lindo.com \(\rangle;\). |
| [11] | Markowitz, H. M., Portfolio selection (1959), Blackwell: Blackwell Oxford |
| [12] | Drezner, Z., Facility location: a survey of applications and methods (1995), Springer: Springer New York |
| [13] | Alizadeh, F.; Goldfarb, D., Second-order cone programming, Mathematical Programming, 95, 1, 3-51 (2003) · Zbl 1153.90522 |
| [14] | Lobo, M. S.; Vandenberghe, L.; Boyd, S.; Lebret, L., Applications of second-order cone programming, Linear Algebra and its Applications, 284, 1-3, 193-228 (1998) · Zbl 0946.90050 |
| [15] | Floudas, C. A.; Pardalos, P. M.; Adjiman, C.; Esposito, W. R.; Gumus, Z. H.; Harding, S. T., Handbook of test problems in local and global optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0943.90001 |
| [16] | Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Mathematical Programming, 91, 2, 201-213 (2002) · Zbl 1049.90004 |
| [17] | Chinneck, J. W., An effective polynomial-time heuristic for the minimum-cardinality is set-covering problem, Annals of Mathematics and Artificial Intelligence, 17, 127-144 (1996) · Zbl 0887.90112 |
| [18] | Schrage, L., Optimization modeling with LINDO (1997), Scientific Press |
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.
