Diagnosis and Resolution of Infeasibility in the Constraint Method for Solving Multi Objective Linear Programming Problems

ABSTRACT

In this paper we discuss about infeasibility diagnosis and infeasibility resolution, when the constraint method is used for solving multi objective linear programming problems. We propose an algorithm for resolution of infeasibility, which is a combination of interactive, weighting and constraint methods.Numerical examples are provided to illustrate the techniques developed.

In this paper we discuss about infeasibility diagnosis and infeasibility resolution, when the constraint method is used for solving multi objective linear programming problems. We propose an algorithm for resolution of infeasibility, which is a combination of interactive, weighting and constraint methods.Numerical examples are provided to illustrate the techniques developed.

KEYWORDS

Multi Objective Linear Programming; Weighting Method; Constraint Method; Infeasibility Analysi; IIS

Multi Objective Linear Programming; Weighting Method; Constraint Method; Infeasibility Analysi; IIS

Cite this paper

M. Safi and H. Marzooni, "Diagnosis and Resolution of Infeasibility in the Constraint Method for Solving Multi Objective Linear Programming Problems,"*American Journal of Operations Research*, Vol. 2 No. 3, 2012, pp. 283-288. doi: 10.4236/ajor.2012.23034.

M. Safi and H. Marzooni, "Diagnosis and Resolution of Infeasibility in the Constraint Method for Solving Multi Objective Linear Programming Problems,"

References

[1] R. Steuer, “Multiple Criteria Optimization: Theory Computation and Application,” Wiley, New York, 1986.

[2] H. W. Kuhn and A. W. Tucker, “Nonlinear Programming,” In: J. Neyman, Ed., Proceeding of the Second Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, 1951, pp. 481-492.

[3] Y. Y. Haimes, L. Lasdon and D. Wismer, “On a Bicriteria Formulation of the Problems of the Integrated System Identification and System Optimization,” IEEE Transaction on Systems, Man, and Cybernetics, SMC-1, 1971, pp. 296-297.

[4] V. J. Bowman, “On the Relationship of the Tchebycheff Norm and the Efficient Frontier of Multi-Criteria Objectives,” In: H. Thiriez and S. Zients, Eds., Multiple-Crite- ria Decision Making, Springer-Verlag, Berlin, 1976, pp. 76-86.

[5] A. Arbel and P. Korhonen, “Using Aspiration Levels in an Interactive Interior Multi-Objective Linear Programming Algorithm”. European Journal of Operational Research, Vol. 89, 1996, pp. 193-201.

[6] M. Zangiabadi, M. R. Safi and H. R. Maleki, “An Algorithm For Solving Multi Objective Programming Problems,” Logic Colloquium, ASL, European Summer Meeting, Italy, Turin, 2004.

[7] H. J. Zimmermann, “Fuzzy Programming and Linear Programming with Several Objective Functions,” Fuzzy Sets and Systems, Vol. 1, No. 1, 1987, pp. 45-55. doi:10.1016/0165-0114(78)90031-3

[8] S. M. Guu and Y. K. Wu, “A Compromise Model for Solving Fuzzy Multi Objective Linear Programming Problems,” Journal of Chinese, Institute of industrial Engineers, Vol. 18, No. 5, 2001, pp. 87-93

[9] M. Jimenez and A. Bilbao, “Pareto Optimal Solutions in Fuzzy Multi Objective Linear Programming,” Fuzzy Sets and Systems, Vol. 160, No. 18, 2009, pp. 2714-2721. doi:10.1016/j.fss.2008.12.005

[10] N. Chakravarti, “Some Results Concerning Post-Infeasibility Analysis,” European Journal of Operational Research, Vol. 73, No. 1, 1994, pp. 139-143. doi:10.1016/0377-2217(94)90152-X

[11] J. W. Chinneck, “MINOS(IIS): Infeasibility Analysis Using MINOS,” Computers and Operations Research, Vol. 21, No. 1, 1994, pp. 1-9. doi:10.1016/0305-0548(94)90057-4

[12] J. W. Chinneck, “Fast Heuristics for the Maximum Feasible Subsystem Problem,” INFORMS Journal on Computing, Vol. 13, No. 3, 2001, pp. 210-223. doi:10.1287/ijoc.13.3.210.12632

[13] G. M. Roodman, “Post-Infeasibility Analysis in Linear Programming,” Management Science, Vol. 25, No. 9, 1979, pp. 916-922. doi:10.1287/mnsc.25.9.916

[14] T. León and V. Liern, “A Fuzzy Method to Repair Infeasibility in Linearly Constrained Problems,” Fuzzy Sets and Systems, Vol. 122, No. 2, 2001, pp. 237-243. doi:10.1016/S0165-0114(00)00010-5

[15] M. Tamiz, S. J. Mardle and D. F. Jones, “Detecting IIS in Infeasible Linear Programming Using Techniques from Goal Programming,” Computers and Operations Research, Vol. 23, No. 2, 1996, pp. 113-119. doi:10.1016/0305-0548(95)00018-H

[16] J. Yang, “Infeasibility Resolution Based on Goal Programming,” Computers and Operations Research, Vol. 35, No. 5, 2008, pp. 1483-1493. doi:10.1016/j.cor.2006.08.006

[17] J. W. Chinneck, “Feasibility and Infeasibility in Optimization. Algorithms and Computational Methods,” Springer, New York, 2008.

[18] J. W. Chinneck and E. W. Dravnieks, “Locating Minimal Infeasible Constraint Sets in Linear Programs,” ORSA Journal on Computing, Vol. 3, No. 2, 1991, pp. 157-168. doi:10.1287/ijoc.3.2.157

[19] J. W. Chinneck, “An Effective Polynomial-Time Heuristic for the Minimum-Cardinality IIS Set-Covering Problem,” Annals of Mathematics and Artificial Intelligence, Vol. 17, No. 1, 1996, pp. 127-144. doi:10.1007/BF02284627

[20] G. Brown and G. Graves, “Elastic Programming: A New Approach to Large-Scale Mixed Integer Optimization,” Presented at ORSA/TIMS Conference, Las Vegas, 1975

[1] R. Steuer, “Multiple Criteria Optimization: Theory Computation and Application,” Wiley, New York, 1986.

[2] H. W. Kuhn and A. W. Tucker, “Nonlinear Programming,” In: J. Neyman, Ed., Proceeding of the Second Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, 1951, pp. 481-492.

[3] Y. Y. Haimes, L. Lasdon and D. Wismer, “On a Bicriteria Formulation of the Problems of the Integrated System Identification and System Optimization,” IEEE Transaction on Systems, Man, and Cybernetics, SMC-1, 1971, pp. 296-297.

[4] V. J. Bowman, “On the Relationship of the Tchebycheff Norm and the Efficient Frontier of Multi-Criteria Objectives,” In: H. Thiriez and S. Zients, Eds., Multiple-Crite- ria Decision Making, Springer-Verlag, Berlin, 1976, pp. 76-86.

[5] A. Arbel and P. Korhonen, “Using Aspiration Levels in an Interactive Interior Multi-Objective Linear Programming Algorithm”. European Journal of Operational Research, Vol. 89, 1996, pp. 193-201.

[6] M. Zangiabadi, M. R. Safi and H. R. Maleki, “An Algorithm For Solving Multi Objective Programming Problems,” Logic Colloquium, ASL, European Summer Meeting, Italy, Turin, 2004.

[7] H. J. Zimmermann, “Fuzzy Programming and Linear Programming with Several Objective Functions,” Fuzzy Sets and Systems, Vol. 1, No. 1, 1987, pp. 45-55. doi:10.1016/0165-0114(78)90031-3

[8] S. M. Guu and Y. K. Wu, “A Compromise Model for Solving Fuzzy Multi Objective Linear Programming Problems,” Journal of Chinese, Institute of industrial Engineers, Vol. 18, No. 5, 2001, pp. 87-93

[9] M. Jimenez and A. Bilbao, “Pareto Optimal Solutions in Fuzzy Multi Objective Linear Programming,” Fuzzy Sets and Systems, Vol. 160, No. 18, 2009, pp. 2714-2721. doi:10.1016/j.fss.2008.12.005

[10] N. Chakravarti, “Some Results Concerning Post-Infeasibility Analysis,” European Journal of Operational Research, Vol. 73, No. 1, 1994, pp. 139-143. doi:10.1016/0377-2217(94)90152-X

[11] J. W. Chinneck, “MINOS(IIS): Infeasibility Analysis Using MINOS,” Computers and Operations Research, Vol. 21, No. 1, 1994, pp. 1-9. doi:10.1016/0305-0548(94)90057-4

[12] J. W. Chinneck, “Fast Heuristics for the Maximum Feasible Subsystem Problem,” INFORMS Journal on Computing, Vol. 13, No. 3, 2001, pp. 210-223. doi:10.1287/ijoc.13.3.210.12632

[13] G. M. Roodman, “Post-Infeasibility Analysis in Linear Programming,” Management Science, Vol. 25, No. 9, 1979, pp. 916-922. doi:10.1287/mnsc.25.9.916

[14] T. León and V. Liern, “A Fuzzy Method to Repair Infeasibility in Linearly Constrained Problems,” Fuzzy Sets and Systems, Vol. 122, No. 2, 2001, pp. 237-243. doi:10.1016/S0165-0114(00)00010-5

[15] M. Tamiz, S. J. Mardle and D. F. Jones, “Detecting IIS in Infeasible Linear Programming Using Techniques from Goal Programming,” Computers and Operations Research, Vol. 23, No. 2, 1996, pp. 113-119. doi:10.1016/0305-0548(95)00018-H

[16] J. Yang, “Infeasibility Resolution Based on Goal Programming,” Computers and Operations Research, Vol. 35, No. 5, 2008, pp. 1483-1493. doi:10.1016/j.cor.2006.08.006

[17] J. W. Chinneck, “Feasibility and Infeasibility in Optimization. Algorithms and Computational Methods,” Springer, New York, 2008.

[18] J. W. Chinneck and E. W. Dravnieks, “Locating Minimal Infeasible Constraint Sets in Linear Programs,” ORSA Journal on Computing, Vol. 3, No. 2, 1991, pp. 157-168. doi:10.1287/ijoc.3.2.157

[19] J. W. Chinneck, “An Effective Polynomial-Time Heuristic for the Minimum-Cardinality IIS Set-Covering Problem,” Annals of Mathematics and Artificial Intelligence, Vol. 17, No. 1, 1996, pp. 127-144. doi:10.1007/BF02284627

[20] G. Brown and G. Graves, “Elastic Programming: A New Approach to Large-Scale Mixed Integer Optimization,” Presented at ORSA/TIMS Conference, Las Vegas, 1975