Elias Munapo - Linear Integer Programming: Theory, Applications, Recent Developments

De Gruyter Series on the Applications of Mathematics in Engineering and Information Sciences

Edited by

Volume

ISBN 9783110702927

e-ISBN (PDF) 9783110703023

e-ISBN (EPUB) 9783110703115

Bibliographic information published by the Deutsche Nationalbibliothek

The Deutsche Nationalbibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data are available on the Internet at http://dnb.dnb.de.

2022 Walter de Gruyter GmbH, Berlin/Boston

To our families, and past, present, and future students

EM and SK

The work in this book is based on our recently published papers in various journals. We wish to express our sincere gratitude to many anonymous referees who raised searching questions and made suggestions for improving the paper. We learn from their comments and remarks, and while improving the presentation of the paper, we also improved our own understanding of the subject. We are thankful to these referees, to our students and to our colleagues who redirected us on the right path, when we found ourselves a bit lonely and off the track.

The authors would also like to express sincere thanks to their respective universities, i.e., the North West University, South Africa and the RMIT University, Australia.

We also want to say thank you to our families for their patience and understanding.

Elias Munapo

Santosh Kumar OAM

Hide-and-seek is a universal game played by children all over the world. Irrespective of their background, nationality, and race; the game enters everyones life in one or the other form. For example, on Easter, children enjoy playing the Hide-and-Seek with Easter eggs. Many of us associate the Hide-and-seek phenomenon only with children, but a closer examination reveals that our lives are full of hides-and-seeks in the form of decision making. Good decisions hide and one is required to seek them. These good-decisions on one hand can bring prosperity, however, danger associated with a bad-decision also stays with us. These decisions in some commerce, business, and industrial environments can be a matter of life and death. Some of these situations are so complex that we make use of mathematical modelling tools to examine their complexities and seek better outcomes from the situation. Therefore, this Hide-and-seek game never ends; and one is surrounded by the consequences of decisions. The outcome of a bad decision can challenge the very existence of the company. Mathematical programming is an abstract form of the Hide-and-Seek game, where good decisions are hiding and with the help of mathematical rigour, we try to unearth the good decisions.

This book is an attempt to develop some strategies to unearth good decisions for a class of problems that can be represented in the form of a mathematical model of the form:

Subject to

Here, we discuss only those cases where fxandgix are linear functions and xj are restricted to integer values. The authors have developed some new strategies during their journey in the field of integer programming. Many pioneering ideas have existed, and where possible, we added a bit more during our journey in this fascinating field. The journey will never end; it will continue.

This book outlines some of our attempts in this fascinating field of mathematical programming.

Before we conclude this preface, we briefly recall a few pioneers in the general field of Mathematical Programming. It is difficult to do proper justice to their contributions, however, our tribute is just a symbol of our respect for them.

First let us recall the father of linear programming, George B. Dantzig (8-11-1914 to 13-5-2005) an American mathematician, Professor Emeritus of Operations Research and Computer Science who made significant contributions to industrial engineering, operations research, computer science, economics, and statistics. He developed the LP model and devised the Simplex Method for solving the LP model. This mathematical model has found immense applications in various fields and helped decision makers. The integer programming is a variation of a LP, where variables are restricted to integer values. Most approaches dealing with integer programming commence the integer optimal search from the LP optimal solutions.

While linear programming was being developed, Richard Bellman (26-8-1920 to19-3-1984) was developing dynamic programming. He was at Rand Corporation, where the concept of dynamic programming was developed. Later he moved to University of Southern California, Los Angeles. The dynamic programming has applications in many real-life industrial engineering and control engineering processes. The dynamic programming creates a new approach to problem solving, fundamentally it is a process of solving a n dimensional problem as n problems of one dimension each. It is a simple but very powerful concept, and it is an art of problem solving.

A transition from linear programming to integer programming occurred by the pioneering work of Ralph E. Gomory (born 7 -5 -1929). He is an American applied mathematician and served as Chairman of IBM Mathematical Sciences Department, Director of Research for the IBM and a research professor at New York University.

The above scientists along with many other researchers have developed the fascinating filed of mathematical programming, that has unending applications in industry and commerce. The authors have made a few advances in this fascinating field. More results will continue to make the field richer and helpful to its users in various decision-making situations.

Elias Munapo and Santosh Kumar OAM

Elias Munapo is a Professor of Operations Research at the North West University, Mafikeng Campus in South Africa. He is a guest editor of the Applied Sciences journal, has published two books, edited several books, a reviewer for several journals. He has published a significant number of journal articles and book chapters. In addition, he has presented at both local and international conferences and has supervised doctoral students to completion. His research interests are in the broad area of operations research.

Prof Kumar OAM is author and co-author of 197 papers and 3 books in the field of Operations Research. His contributions to the field of OR have been recognised in the form of Ren Pot Award from the Australian Society for Operations Research (ASOR) in 2009 and a recognition award from the South African OR society as a non-member of the society in 2011. He has served as the President of the Asia Pacific Operations Research societies (199597), where ASOR was a member along with China, India, Japan, Korea, Malaysia, New Zealand, and Singapore. He is currently an Adjunct Professor at the RMIT University, Melbourne. He is a Fellow of the Institute of Mathematics and its Applications, UK. Recently, on Queens birthday, 14 June 2021 he was awarded a Medal of the Order of Australia.