<p>Shiv Nadar University is a comprehensive, multidisciplinary, research-focused, and student-centric University offering a full range of academic programs at the undergraduate, postgraduate and doctoral level. With state-of-the-art infrastructure, the University comprises of academic wings, sophisticated labs, international standard sports facilities, amphitheaters, auditorium, conference rooms and smart classrooms. The University&rsquo;s goal is to become internationally recognized for the quality of its research and creative endeavors and their applicability to improving quality of life, generating new insights and expanding the boundaries of human knowledge creativity. Committed to excellence in teaching, research and service, the University aims to serve the higher education needs of India and the world beyond.</p>

Shiv Nadar University

The matrix M of a linear complementarity problem can be viewed as a payoff matrix of a two-person zero-sum game. Lemke's algorithm can be successfully applied to reach a complementary solution or infeasibility when the game satisfies the following conditions: (i) Value of M is equal to zero. (ii) For all principal minors of MT (transpose of M) value is non-negative. (iii) For any optimal mixed strategy y of the maximizer either yi > 0 or (My)i > 0 for each coordinate i. © 2022 World Scientific Publishing Company.

World University root node

Mathematics

(SoNS) School of Natural Sciences

International Game Theory Review

A Note on Linear Complementarity via Two-Person Zero-Sum Games

A real square matrix is a Z-matrix if it’s off diagonal elements are nonpositive. A Z-matrix with nonnegative principal minors is called an M-matrix. The problem of testing whether a given matrix is an M-matrix or not is an important research problem in matrix theory as M-matrices arise naturally in a wide range of applications including finite difference methods for partial differential equations, input-output models in economics, linear complementarity problems in operations research, and Markov processes in probability and statistics. In this paper, we present a polynomial-time algorithm for testing whether a Z-matrix is an M-matrix based on modified simplex method. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

Annals of Operations Research

On testing nonnegativity of principal minors of Z -matrices using simplex method

Max-plus algebra has been applied to several fields like matrix algebra, cryptography, transportation, manufacturing, information technology and study of discrete event systems like subway traffic networks, parallel processing systems, telecommunication networks for many years. In this paper, we discuss various optimization problem using methods based on max-plus algebra, which has maximization and addition as its basic arithmetic operations. We present some sub-classes of mathematical optimization problems like linear programming, convex quadratic programming problem, fractional programming problem, bimatrix game problem and some classes of stochastic game problem in max algebraic framework and discuss various connections between max-plus algebra and optimization. © 2020, Springer Nature Singapore Pte Ltd.

Springer Proceedings in Mathematics and Statistics

Max Plus Algebra, Optimization and Game Theory

Preface to the Special Issue on-Operations Research and Game Theory: Modeling and Computation

Quadratic programming problems involving distance matrix (D) that arises in trees are considered in the literature by Dankelmann (Discrete Math 312:12–20, 2012), Bapat and Neogy (Ann Oper Res 243:365–373, 2016). In this paper, we consider the question of solving the quadratic programming problem of finding maximum of xTRx subject to x being a nonnegative vector with sum 1 and show that for the class of simple graphs with resistance distance matrix (R) which are not necessarily a tree, this problem can be reformulated as a strictly convex quadratic programming problem. An application to symmetric bimatrix game is also presented. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

On solving a non-convex quadratic programming problem involving resistance distances in graphs

In this paper, we introduce the notion of generalized positive subdefinite matrices of level k by generalizing the definition of generalized positive subdefinite matrices introduced by Crouzeix and Komlósi in [Applied optimization. Vol. 59, Dordrecht: Kluwer Academic Publications; 2001. p. 45–63]. The main motivation behind this generalization is to identify new subclasses of row sufficient matrices [Cottle, Pang and Venkateswaran, Linear Algebra Appl. 1989;114/115:231–249] which are not a subclass of copositive matrices. We establish new sufficient conditions for a matrix to be a non-copositive P0 matrix and a non-copositive row sufficient matrix using the notion of generalized positive subdefinite matrices of level k. We present a new termination result for Lemke’s algorithm which supplements Jones’ result [Math Program. 1986;35:239–242]. © 2017, © 2017 Informa UK Limited, trading as Taylor & Francis Group.

Linear and Multilinear Algebra

On generalizations of positive subdefinite matrices and the linear complementarity problem

This paper deals with the problem of finding an integer solution to a linear complementarity problem (LCP). Chandrasekaran et al. [1] introduced the class I of integral matrices for which the corresponding LCP has an integer solution for every integral vector q, for which it has a solution and proved that for some well-known matrix classes principal unimodularity forms a necessary and sufficient condition for inclusion in the class I. In this paper, we identify some more well-known matrix classes for which principal unimodularity forms a necessary and sufficient condition for inclusion in the class I. The concept of total dual integrality is utilized to obtain a necessary and sufficient condition for existence of an integer solution to LCP with a hidden K-matrix. We interconnect the concept of Hilbert basis with principal unimodularity of a matrix and the corresponding complementary cones. A necessary and sufficient condition is given for the existence of an integer solution of a linear fractional programming problem by using its LCP formulation. © 2018 Elsevier Inc.

Linear Algebra and Its Applications

Total dual integrality and integral solutions of the linear complementarity problem

In this chapter, we study various mathematical programming problems in a common framework known as linear complementarity problem. Solving a linear complementarity problem depends on the properties of its underlying matrix class. In this chapter, we discuss matrix theoretic properties of some recent matrix classes encountered in linear complementarity literature and its processability using Lemke’s algorithm. © 2018, Springer Nature Singapore Pte Ltd.

Indian Statistical Institute Series

A Unified Framework for a Class of Mathematical Programming Problems

Preface

We report a discrete variant of Farkas’ Lemma in the setting of a module over a linearly ordered commutative ring. The ring may contain zero divisors, and need not be associative nor unital, but we need a certain hypothesis about the ring. Finally, we discuss the result and compare it with other related results found in the literature. © 2017 Elsevier B.V.

Operations Research Letters

A discrete variant of Farkas’ Lemma

In this paper, we revisit a result by Jurg et al. (Linear Algebra Appl 141:61–74, 1990) where the necessary and sufficient condition for a bimatrix game to be weakly completely mixed is given. We present an alternate proof of this result using linear complementarity approach. We extend this result to a generalization of bimatrix game introduced by Gowda and Sznajder (Int J Game Theory 25:1–12, 1996) via a generalization of linear complementarity problem introduced by Cottle and Dantzig (J Comb Theory 8:79–90, 1970). We further study completely mixed switching controller stochastic game (in which transition structure is a natural generalization of the single controller games) and extend the results obtained by Filar (Proc Am Math Soc 95:585–594, 1985) for completely mixed single controller stochastic game to completely mixed switching controller stochastic game. A numerical method is proposed to compute a completely mixed strategy for a switching controller stochastic game. © 2016, Springer Science+Business Media New York.

Dynamic Games and Applications

Completely Mixed Strategies for Generalized Bimatrix and Switching Controller Stochastic Game

The aim of this paper is twofold. Firstly, to define a solution concept of Pareto-optimality for a multi-objective flexible linear programming (MOFLP) problem (or multi-objective fuzzy linear programming problem) and design a method to extract a Pareto-optimal solution of MOFLP problem from the set of optimal solutions of equivalent optimization problem formulated by Dubey and Mehra (2013). Secondly, to extend this study to multi-objective linear programming problem involving hard and flexible constraints with interval uncertainty. A flexible constraint with interval uncertainty generalizes a flexible constraint by allowing preferences to be expressed in the form of intervals. An optimistic-pessimistic approach is proposed to solve multi-objective flexible linear programming with interval uncertainty (MOFLPIU) using an interval-valued fuzzy set representation and the Hurwicz optimism-pessimism criterion. © 2016 - IOS Press and the authors. All rights reserved.

Journal of Intelligent and Fuzzy Systems

Pareto-optimal solutions for multi-objective flexible linear programming

In this paper, we explore various matrix-theoretic aspects of the hidden Z class and demonstrate how the concept of principal pivot transform can be effectively used to extend many existing results. In fact, we revisit various results obtained for hidden Z class by Mangasarian, Cottle and Pang in context of solving linear complementarity problems as linear programs. We identify hidden Z-matrices of special category and discuss the number of solutions of the associated linear complementarity problems. We also present game theoretic interpretation of various results related to hidden Z class and obtain proofs following the game theoretic approach of Raghavan for a subclass of Z-matrices. © 2016 Published by Elsevier Inc.

On hidden Z-matrices and the linear complementarity problem

In this paper, we study the multi-objective flexible linear programming (MOFLP) problems (or fuzzy multi-objective linear programming problems) in the heterogeneous bipolar framework. Bipolarity allows us to distinguish between the negative and the positive preferences. Negative preferences denote what is unacceptable while positive preferences are less restrictive and express what is desirable. This viewpoint enables us to handle fuzzy sets representing constraints and objective functions separately and combine them in distinct ways. In this paper, a solution concept of Pareto-optimality for MOFLP problems is defined and an approach is proposed to single out such a solution for MOFLP with highest possible degree of feasibility. © 2014 Taylor & Francis.

International Journal of General Systems

Computing a Pareto-optimal solution for multi-objective flexible linear programming in a bipolar framework

The traditional frameworks for fuzzy linear optimization problems are inspired by the max-min model proposed by Zimmermann using the Bellman-Zadeh extension principle to aggregate all the fuzzy sets representing flexible (fuzzy) constraints and objective functions together. In this paper, we propose an alternative approach to model fuzzy multi-objective linear programming problems (FMOLPPs) from a perspective of bipolar view in preference modeling. Bipolarity allows us to distinguish between the negative and the positive preferences. Negative preferences denote what is unacceptable while positive preferences are less restrictive and express what is desirable. This framework facilitate a natural fusion of bipolarity in FMOLPPs. The flexible constraints in a fuzzy multi-objective linear programming problem (FMOLPP) are viewed as negative preferences for describing what is somewhat tolerable while the objective functions of the problem are viewed as positive preferences for depicting satisfaction to what is desirable. This approach enables us to handle fuzzy sets representing constraints and objective functions separately and combine them in distinct ways. After aggregating these fuzzy sets separately, coherence (or consistency) condition is used to define the fuzzy decision set. © 2013 Elsevier B.V.

Fuzzy Sets and Systems

A bipolar approach in fuzzy multi-objective linear programming

The traditional frameworks for fuzzy linear optimization problems are inspired by the max-min model proposed by Zimmermann using the Bellman-Zadeh extension principle. This paper attempts to view fuzzy multiobjective linear programming problem (FMOLPP) from a perspective of preference modeling. The fuzzy constraints are viewed as negative preferences for rejecting what is unacceptable while the objective functions are viewed as positive preferences for depicting satisfaction to what is desired. This bipolar view enable us to handle fuzzy constraints and objectives separately and help to combine them in distinct ways. The optimal solution of FMOLPP is the one which maximizes the disjunctive combination of the weighted positive preferences provided it satisfy the negative preferences combined in conjunctive way. © 2012 Springer-Verlag.

Communications in Computer and Information Science

Fuzzy multiobjective linear programming: A bipolar view

The equivalence between the interval-valued fuzzy set (IVFS) and the intuitionistic fuzzy set (IFS) is exploited to study linear programming problems involving interval uncertainty modeled using IFS. The non-membership of IFS is constructed with three different viewpoints viz., optimistic, pessimistic, and mixed. These constructions along with their indeterminacy factors result in S-shaped membership functions in the fuzzy counterparts of the intuitionistic fuzzy linear programming models. The solution methodology of Yang et al. [45], and its subsequent generalization by Lin and Chen [33] are used to compute the optimal solutions of the three fuzzy linear programming models. © 2011 Elsevier B.V. All rights reserved.

Fuzzy linear programming under interval uncertainty based on IFS representation

This paper presents an approach based on value and ambiguity indexes defined in [1] to solve linear programming problems with data as triangular intuitionistic fuzzy numbers. © 2011. The authors-Published by Atlantis Press.

Proceedings of the 7th Conference of the European Society for Fuzzy Logic and Technology, EUSFLAT 2011 and French Days on Fuzzy Logic and Applications, LFA 2011