Linear bilevel multi-follower programming with independent followers

This paper considers a particular case of linear bilevel programming problems with one leader and multiple followers. In this model, the followers are independent, meaning that the objective function and the set of constraints of each follower only include the leader’s variables and his own variables. We prove that this problem can be reformulated into a linear bilevel problem with one leader and one follower by defining an adequate second level objective function and constraint region. In the second part of the paper we show that the results on the optimality of the linear bilevel problem with multiple independent followers presented in Shi et al. [The kth-best approach for linear bilevel multi-follower programming, J. Global Optim. 33, 563–578 (2005)] are based on a misconstruction of the inducible region.     

Infrastructure development for conversion to environmentally friendly fuel

An important concern for any nation wishing to convert to alternate, environmentally friendly energy sources is the development of appropriate fuel distribution infrastructure. We address the problem of optimally locating gas station facilities for developing nations, like India, which are in the process of converting from leaded to unleaded fuel. Importantly, a similar approach may be used in developed countries, which are in the process of converting to automobiles using hydrogen or electrical energy. An integer-programming model with the objective of balancing the perspectives of coverage and cost is presented for this facility location problem. Given the existing network of roads, the model considers the traveling population, the location of existing facilities and the cost of, either converting these facilities to carry unleaded fuel, or of installing new facilities in an attempt to minimize cost and simultaneously maximize coverage of population. We develop a heuristic solution procedure for this problem. The methodology is applied to data sets obtained from Current et al. [J.R. Current, C.S. ReVelle, J.L. Cohon, Decision Sciences 19 (1988) 490] representing the Ohio state limited access highway network, and to the Indian national highway network. Additionally, extensive simulations are carried out in order to examine where our approach compares with the maximum weighted spanning tree approach. This work extends the Maximum Covering/Shortest Path problem (MCSPP) formulated by Current et al. [J.R. Current, C.S. ReVelle, J.L. Cohon, European Journal of Operational Research 21 (1985) 189] to accommodate multiple sources and destinations.     

The complexity of anl p method for discrete Tchebycheff approximation in exact arithmetic

A discrete Tchebycheff problem is approximated by a sequence ofl _p norm problems. This is an algorithm to be used if a large number of variables is involved as is the case in the approximation of a function of several variables by a polynomial. The complexity of this procedure is investigated and a lower bound for the number of steps to reach ε-optimality is established. Supported by NIH Grant RR01243 at the University of Washington     

Efficient solution methods for covering tree problems

In recent years, interest has been shown in the optimal location of ‘extensive’ facilities in a network. Two such problems—the Maximal Direct and Indirect Covering Tree problems—were introduced by Hutson and ReVelle. Previous solution techniques are extended to provide an efficient algorithm for the Indirect Covering Tree problem and the generalization in which demand covered is attenuated by distance. It is also shown that the corresponding problem is NP-hard when the underlying network is not a tree.     

Spline smoothing under constraints on derivatives

An efficient algorithm for computing a smoothing polynomial splines under inequality constraints on derivatives is introduced where both order and breakpoints ofs can be prescribed arbitrarily. By using the B-spline representation ofs, the original semi-infinite constraints are replaced by stronger finite ones, leading to a least squares problem with linear inequality constraints. Then these constraints are transformed into simple box constraints by an appropriate substitution of variables so that efficient standard techniques for solving such problems can be applied. Moreover, the smoothing term commonly used is replaced by a cheaply computable approximation. All matrix transformations are realized by numerically stable Givens rotations, and the band structure of the problem is exploited as far as possible.     

BFC-MSMIP: an exact branch-and-fix coordination approach for solving multistage stochastic mixed 0–1 problems

We present an exact algorithmic framework, so-called BFC-MSMIP, for optimizing multistage stochastic mixed 0–1 problems with complete recourse. The uncertainty is represented by using a scenario tree and lies anywhere in the model. The problem is modeled by a splitting variable representation of the Deterministic Equivalent Model of the stochastic problem, where the 0–1 variables and the continuous variables appear at any stage. The approach uses the Twin Node Family concept within the algorithmic framework, so-called Branch-and-Fix Coordination, for satisfying the nonanticipativity constraints in the 0–1 variables. Some blocks of additional strategies are used in order to show the performance of the proposed approach. The blocks are related to the scenario clustering, the starting branching and the branching order strategies, among others. Some computational experience is reported. It shows that the new approach obtains the optimal solution in all instances under consideration.      

A single facility stochastic location problem undera-distance

In this paper we consider a stochastic facility location model in which the weights of demand points are not deterministic but independent random variables, and the distance between the facility and each demand point isA-distance. Our objective is to find a solution which minimizes the total cost criterion subject to a chance constraint on cost restriction. We show a solution method which solves the problem in polynomial order computational time. Finally the case of rectilinear distance, which is used in many facility location models, is discussed.     

<Emphasis Type="Italic">m</Emphasis> Components-admissible solutions of systems of higher-order partial differential equations on <Emphasis Type="Italic">C</Emphasis><Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

Using value distribution theory and techniques in several complex variables,we investigate the problem of existence of m components-admissible solutions of a class of systems of higher-order partial differential equations in several complex variables and estimate the number of admissible components of solutions.Some related results will also be obtained.     

An infeasible-interior-point predictor-corrector algorithm for theP *-geometric LCP

AP _*-geometric linear complementarity problem (P _*GP) as a generalization of the monotone geometric linear complementarity problem is introduced. In particular, it contains the monotone standard linear complementarity problem and the horizontal linear complementarity problem. Linear and quadratic programming problems can be expressed in a “natural” way (i.e., without any change of variables) asP _*GP. It is shown that the algorithm of Mizunoet al. [6] can be extended to solve theP _*GP. The extended algorithm is globally convergent and its computational complexity depends on the quality of the starting points. The algorithm is quadratically convergent for problems having a strictly complementary solution. The work of F. A. Potra was supported in part by NSF Grant DMS 9305760     

The simplex method and unrestricted variables

Suppose that the simplex method is applied to a linear programming problem havingm equality constraints andr unrestricted variables. We give a method of performing the steps of the simplex method which reduces the arithmetic operation count byrm at each iteration. This savings in operations is achieved, since the method does not update the rows of the basis inverse associated with the unrestricted variables. Similar computational savings are achieved when the method is applied to the updating of anLU-factorization of the basis matrix.This research was supported by the Natural Sciences and Engineering Research Council of Canada under Grant No. A8189 and by a postgraduate fellowship.     

A maximumb-matching problem arising from median location models with applications to the roommates problem

We consider maximumb-matching problems where the nodes of the graph represent points in a metric space, and the weight of an edge is the distance between the respective pair of points. We show that if the space is either the rectilinear plane, or the metric space induced by a tree network, then theb-matching problem is the dual of the (single) median location problem with respect to the given set of points. This result does not hold for the Euclidean plane. However, we show that in this case theb-matching problem is the dual of a median location problem with respect to the given set of points, in some extended metric space. We then extend this latter result to any geodesic metric in the plane. The above results imply that the respective fractionalb-matching problems have integer optimal solutions. We use these duality results to prove the nonemptiness of the core of a cooperative game defined on the roommate problem corresponding to the above matching model. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

Choosing the best set of variables in regression analysis using integer programming

This paper is concerned with an algorithm for selecting the best set of s variables out of k(> s) candidate variables in a multiple linear regression model. We employ absolute deviation as the measure of deviation and solve the resulting optimization problem by using 0-1 integer programming methodologies. In addition, we will propose a heuristic algorithm to obtain a close to optimal set of variables in terms of squared deviation. Computational results show that this method is practical and reliable for determining the best set of variables.     

New Models of the Generalized Minimum Spanning Tree Problem

We consider a generalization of the Minimum Spanning Tree Problem, called the Generalized Minimum Spanning Tree Problem, denoted by GMST. It is known that the GMST problem is NP-hard. We present a stronger result regarding its complexity, namely, the GMST problem is NP-hard even on trees as well an exact exponential time algorithm for the problem based on dynamic programming. We describe new mixed integer programming models of the GMST problem, mainly containing a polynomial number of constraints. We establish relationships between the polytopes corresponding to their linear relaxations. Based on a new model of the GMST we present a solution procedure that solves the problem to optimality for graphs with nodes up to 240. We discuss the advantages of our method in comparison with earlier methods.     

Analysis of Decomposition Algorithms with Benders Cuts for p-Median Problem

In this paper the algorithms for solving the p-median problem based on the Benders decomposition are investigated. A family of problems hard for solving with such algorithms is constructed and then generalized to a special NP-hard case of the p-median problem. It is shown that the effectiveness of the considered algorithms depends on the choice of the optimal values of the dual variables used in Benders cuts. In particular, the depth of the cuts can be equal to one.     

A safe minimum standard,the elasticity of substitution,and the cleanup of the Ganges in Varanasi

Despite repeated calls for a thorough cleanup of water pollution in the Ganges river, there are only two papers in the social sciences by Batabyal and Beladi (2017, 2019) that have shed theoretical light on this cleanup problem and its connection to the sustainability of tourism in Varanasi. Hence, we extend the above‐mentioned analyses and focus on two specific questions. First, we introduce the notion of a safe minimum standard (SMS) into the study and show how to analyze a probabilistic model of the Ganges cleanup problem when the SMS is accounted for. Second, for a representative citizen of Varanasi, we study how the magnitude of the elasticity of substitution between a composite consumption good and water quality in the Ganges—modeled by the SMS—affects the tradeoff between consumption and water quality maintenance.     

Competitive Analysis for the On-line Truck Transportation Problem

In this paper, the on-line k-truck transportation problem (k-OLTTP) whose objects are to be transported between the vertices of a given graph on which there are k mobile trucks to be scheduled is proposed. It is motivated by the research concerning on-line k-truck problem and on-line transportation problem. The goal is to minimize the makespan which is consumed to complete some on-line request sequence. Some preliminary knowledge is introduced and the model of k-OLTTP is established firstly. Two versions of a special case of k-OLTTP, namely 1-OLTTP, have been studied and some results are obtained. For the first version, Open-1-OLTTP, a lower bound of competitive ratio 2 is presented and two optimal on-line algorithms, Reschedule Strategy (RS) and Lay Over Strategy (LOS) respectively, are analyzed. For the second version, Close-1-OLTTP, a lower bound of competitive ratio , where θ is the ratio between the time consumed by the loaded truck and the empty truck to travel the same distance, is also developed and on-line algorithms RS and LOS are proved to have competitive ratio 2. Finally, some interesting remarks concerning OLTTP and its future research are discussed.     

Functional Integration with an “Automorphic” Boundary Condition and Correlators of Third Components of Spins in the XX Heisenberg Model

For the generating function of static correlators of the third components of spins in the XX Heisenberg model, we derive a new representation given by a combination of Gaussian functional integrals over anticommuting variables. A peculiarity of the resulting functional integral is that a part of the integration variables depend on the imaginary time automorphically: these variables are multiplied by a certain complex number under the shift of the imaginary time by the period. The other variables satisfy the standard boundary conditions of the fermionic/bosonic type. Functional integration results are represented as determinants of matrix operators. We finally evaluate the generating function of correlators and the partition function of the model in the zeta-function regularization. The consistency of the suggested functional definition is confirmed by calculating several correlation functions of the third components of spins at a nonzero temperature.     

Inverse nodal problem for p–laplacian dirac system

In this study, we solve an inverse nodal problem for p‐Laplacian Dirac system with boundary conditions depending on spectral parameter. Asymptotic formulas of eigenvalues, nodal points and nodal lengths are obtained by using modified Prüfer substitution. The key step is to apply modified Prüfer substitution to derive a detailed asymptotic estimate for eigenvalues. Furthermore, we have shown that the functions r(x) and q(x) in Dirac system can be established uniquely by using nodal parameters with the method used by Wang et al. Obtained results are more general than the classical Dirac system. Copyright © 2016 John Wiley & Sons, Ltd.     

Design of induction motors using a mixed-variable approach

In this paper we are concerned with the problem of optimally designing three-phase induction motors. This problem can be formulated as a mixed variable programming problem. Two different solution strategies have been used to solve this problem. The first one consists in solving the continuous nonlinear optimization problem obtained by suitably relaxing the discrete variables. On the opposite, the second strategy tries to manage directly the discrete variables by alternating a continuous search phase and a discrete search phase. The comparison between the numerical results obtained with the above two strategies clearly shows the fruitfulness of taking directly into account the presence of both continuous and discrete variables.This work was supported by CNR/MIUR Research Program “Metodi e sistemi di supporto alle decisioni”, Rome, Italy.