Volume 7, numéro 2, winter 2012

EN :

There are 833 thousand polling stations in all of the 543 parliamentary constituencies spread over 35 states of India. On the day elections are being held in any one of these polling stations, a minimum of 4 Central Police Force(CPF) personnel must be deployed there, to maintain law and order and guarantee that voters can vote freely without being intimidated by anyone. As the number of CPF personnel available for this activity is limited, it is not possible to hold the Indian General elections on a single day over the whole country. So the set of 35 States of India is partitioned into a number of subsets, with elections in each subset of states being held on a single day. This partition is required to satisfy the constraints that the states in each subset are contiguous, and the subsets themselves must be contiguous. We present a method for organizing the Indian General Elections subject to these constraints, and minimizing the total number of election days required, and the total cost for the movement of CPF personnel involved. The method is based on the shortest Hamiltonian path problem, a tour segmentation problem defined in the paper, and the bipartite minimum cost flow problem.

EN :

The need for adopting efficient designs in industrial experiments is well understood. Often situations arise where the existing designs such as orthogonal arrays are not suitable for designing required experiments. This paper deals with one such situation where there was a need for designing an asymmetrical factorial experiment involving interactions. Failing to get a satisfactory answer to this problem from the literature, the authors have developed an ad hoc method of constructing a design. It is transparent from the method of construction that the design provides efficient estimates for all the required main effects and interactions. The later part of this paper deals with the issues of how this method is extended to more general situations and how this ad hoc method is translated into a systematic approach. The method consists of formulating the construction problem as certain integer programming problems. It is believed that this method will be very useful in practical applications. The ideas are illustrated with a number of examples.

EN :

Irrigation water management plays a crucial role in the growth and prosperity of countries like India. Optimization Techniques can be effectively used in the management of irrigation water. Motivated by a real crisis in Andhra Pradesh, India, the authors made an attempt to provide scientific solution to the problem of management of Pennar Delta System of Nellore District in Andhra Pradesh. The problem concerns the management of water distribution and scheduling for given requirements and availabilities of water at various nodes of the irrigation network of the system. This article provides a model and framework for the problem in question. The problem is formulated as a dynamic minimum cost network flow problem and provides an approach to solve the problem using static network flow models. A need based software is also developed to solve the network flow problems. Some issues in the programming are discussed.

EN :

The class of positive definite and positive semidefinite matrices is one of the most frequently encountered matrix classes both in theory and practice. In statistics, these matrices appear mostly with symmetry. However, in complementarity problems generally symmetry in not necessarily an accompanying feature. Linear complementarity problems defined by positive semidefinite matrices have some interesting properties such as the solution sets are convex and can be processed by Lemke’s algorithm as well as Graves’ principal pivoting algorithm. It is known that the principal pivotal transforms (PPTs) (defined in the context of linear complementarity problem) of positive semidefinite matrices are all positive semidefinite. In this article, we introduce the concept of generalized PPTs and show that the generalized PPTs of a positive semidefinite matrix are also positive semidefinite. One of the important characterizations of P -matrices (that is, the matrices with all principle minors positive) is that the corresponding linear complementarity problems have unique solutions. In this article, we introduce a linear transformation and characterize positive definite matrices as the matrices with corresponding semidefinite linear complementarity problem having unique solutions. Furthermore, we present some simplification procedure in solving a particular type of semidefinite linear complementarity problems involving positive definite matrices.

EN :

We study a variant of the two-phase method for general bi-objective combinatorial optimization problems. First, we analyze a basic enumerative procedure, often used in literature to solve specific bi-objective combinatorial optimization problems, making it suitable to solve general problems. We show that the procedure generates the exact set E of efficient points by solving exactly 2[notdef]E[notdef] − 1 single objective problems. Second, we embed the procedure in a classic two-phase framework, where supported points are computed in the first phase and unsupported points are computed in the second phase.

We test the refined approach on a hard problem, namely the Traveling Salesman Problem with Profits, a bi-objective generalization of the well known Traveling Salesman Problem. On the tested instances, the procedure outperforms the [epsilon1]-constraint method, one of the most used approaches to solve exactly general bi-objective combinatorial optimization problems.