Reduction of indefinite quadratic programs to bilinear programs

Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such reductions are studied in which: (i) the number of additional variables is minimum or (ii) the number of complicating variables, i.e., variables to be fixed in order to obtain a linear program, in the resulting bilinear program is minimum. These two problems are shown to be equivalent to a maximum bipartite subgraph and a maximum stable set problem respectively in a graph associated with the quadratic program. Non-polynomial but practically efficient algorithms for both reductions are thus obtaine.d Reduction of more general global optimization problems than quadratic programs to bilinear programs is also briefly discussed.     

Can restrictions on redemption timing boost profitability of loyalty programs in competitive environments?

Computational Management Science - This research investigates whether it is beneficial for competing firms offering loyalty programs (LPs) to restrict the reward redemption time. We develop a...     

Model development and optimization in interactive computing environments

Integrated computing systems—such as Maple, Mathematica, and MATLAB—enable the development of “live” electronic documents that include explanatory text, calculations, custom programming (code development), visualization, and other features. As a result, teachers and students, researchers and practitioners can develop applications in a completely interactive format. Such e-documents can be put to good use in developing textbooks, lecture notes, assignments and presentations, as well as in the context of research and development (R&D) projects. The interactive approach accelerates and enhances the process of learning and research. To illustrate this approach, we discuss a nonlinear (global and local) optimization software product and a topical electronic book that support interactive model development and optimization in Maple. We highlight the key features of the e-book and the software, present illustrative examples, and point towards a range of scientific and engineering applications.      

A mathematical model for fungal development in heterogeneous environments

A mathematical model for the development of fungal mycelia in heterogeneous environmental conditions is presented. The validity of this model is tested by comparison of numerical simulations with experimental observations.     

Using video representations of teaching in practice-based professional development programs

This article explores how video can be used in practice-based professional development (PD) programs to serve as a focal point for teachers’ collaborative exploration of the central activities of teaching. We argue that by choosing video clips, posing substantive questions, and facilitating productive conversations, professional developers can guide teachers to examine central aspects of learning and instruction. We draw primarily from our experiences developing and studying two mathematics PD programs, the Problem-Solving Cycle (PSC) and Learning and Teaching Geometry (LTG). While both programs feature classroom video in a central role, they illustrate different approaches to practice-based PD. The PSC, an adaptive model of PD, provides a framework within which facilitators tailor activities to suit their local context. By contrast, LTG is a highly specified model of PD, which details in advance particular learning goals, design characteristics, and extensive support materials for facilitators. We propose a continuum of video use in PD from highly adaptive to highly specified and consider the affordances and constraints of different approaches exemplified by the PSC and LTG programs.     

Bounding multi-stage stochastic programs from above

The purpose of this paper is to present general approaches for bounding some multi-stage stochastic programs from above. The results are based on restricting the solution set, such that the remaining multi-stage stochastic program is easy to solve. An example where the methods can be applied is presented.Supported in part by NATO Collaborative Research Grant No. 0785/87.     

Solving linear programs from sign patterns

This paper is an attempt to provide a connection between qualitative matrix theory and linear programming. A linear program is said to be sign-solvable if the set of sign patterns of the optimal solutions is uniquely determined by the sign patterns of A, b, and c. It turns out to be NP-hard to decide whether a given linear program is sign-solvable or not. We then introduce a class of sign-solvable linear programs in terms of totally sign-nonsingular matrices, which can be recognized in polynomial time. For a linear program in this class, we devise an efficient combinatorial algorithm to obtain the sign pattern of an optimal solution from the sign patterns of A, b, and c. The algorithm runs in O(mγ) time, where m is the number of rows of A and γ is the number of all nonzero entries in A, b, and c.     

On the transformation of lexicographic nonlinear multiobjective programs to single objective programs

This paper deals with multiobjective optimization programs in which the objective functions are ordered by their degree of priority. A number of approaches have been proposed (and several implemented) for the solution of lexicographic (preemptive priority) multiobjective optimization programs. These approaches may be divided into two classes. The first encompasses the development of algorithms specifically designed to deal directly with the initial model. Considered only for linear multiobjective programs and multiobjective programs with a finite discrete feasible region, the second one attempts to transform, efficiently, the lexicographic multiobjective model into an equvivalent model, i.e. a single objective programming problem. In this paper, we deal with the second approach for lexicographic nonlinear multiobjective programs.     

Parametric approaches to fractional programs

The fractional program P is defined by maxf(x)/g(x) subject tox∈X. A class of methods for solving P is based on the auxiliary problem Q(λ) with a parameter λ: maxf(x)?λg(x) subject tox∈X. Starting with two classical methods in this class, the Newton method and the binary search method, a number of variations are introduced and compared. Among the proposed methods. the modified binary search method is theoretically interesting because of its superlinear convergence and the capability to provide an explicit interval containing the optimum parameter value \(\bar \lambda \) . Computational behavior is tested by solving fractional knapsack problems and quadratic fractional programs. The interpolated binary search method seems to be most efficient, while other methods also behave surprisingly well.     

Evaluating green supplier development programs with a grey-analytical network process-based methodology

Under circumstances of increasing environmental pressures from markets and regulators, focal companies in supply chains have recognized the importance of greening their supply chain through green supplier development programs. Various studies have started to explore the inter-relationships between green supply chain management and supplier performance. Much of this performance can be achieved only with suppliers’ involvement in green supplier development programs. But, the literature focusing on green supplier development programs and supplier involvement propensity is very limited. In addition, formal tools and models for focal companies to evaluate these inter-relationships, especially considering propensity of suppliers’ involvement, are even rarer. To help address this gap in the literature, we introduce a grey analytical network process-based (grey ANP-based) model to identify green supplier development programs that will effectively improve suppliers’ performance. We further comprehensively evaluate green supplier development programs with explicit consideration of suppliers’ involvement propensity levels. A real world example is introduced to demonstrate the effectiveness of the model. We end with a discussion of managerial implications and present some directions for further research.     

A preliminary set of applications leading to stochastic semidefinite programs and chance-constrained semidefinite programs

Ariyawansa and Zhu have recently introduced (two-stage) stochastic semidefinite programs (with recourse) (SSDPs) [1] and chance-constrained semidefinite programs (CCSDPs) [2] as paradigms for dealing with uncertainty in applications leading to semidefinite programs. Semidefinite programs have been the subject of intense research during the past 15 years, and one of the reasons for this research activity is the novelty and variety of applications of semidefinite programs. This research activity has produced, among other things, efficient interior point algorithms for semidefinite programs. Semidefinite programs however are defined using deterministic data while uncertainty is naturally present in applications. The definitions of SSDPs and CCSDPs in [1] and [2] were formulated with the expectation that they would enhance optimization modeling in applications that lead to semidefinite programs by providing ways to handle uncertainty in data. In this paper, we present results of our attempts to create SSDP and CCSDP models in four such applications. Our results are promising and we hope that the applications presented in this paper would encourage researchers to consider SSDP and CCSDP as new paradigms for stochastic optimization when they formulate optimization models.     

Finite-state approximations to denumerable-state dynamic programs

We show how to find a sequence of policies for essentially finite-state dynamic programs such that the corresponding vector of optimal returns converges pointwise to that of a denumerable-state dynamic program. The corresponding result for stochastic games is also given.     

An application of homotopy to solving linear programs

Consider a linear program inm inequality constraints andn nonnegative variables. An application of homotopy to the problem gives an algorithm similar to Dantzig's self-dual method. Howeve, the homotopy approach allows one to recognize several previously undescribed and potentially interesting properties. For example, the algorithm can be initiated in such a way as to produce a path which is primal-dual feasible. Moreover, one can theoretically identify an orthant with the property that if one initiates the algorithm at any point in that orthant then, after a ‘phase I’ requiring at most min{m, n} pivots, convergence is obtained in one step.     

On the uniqueness of solutions to linear programs

We provide a constructive method of checking whether a linear programming problem (LPP) has a unique feasible or a unique optimal solution. Our method requires the solution of only one extra LPP such that the original problem has alternative solutions if and only if the optimal value of the new LPP is positive. If the original solution is not unique, an alternative solution is displayed. Possible applications are discussed.     

The lagrange approach to infinite linear programs

In this paper, we use the Lagrange multipliers approach to study a general infinite-dimensionalinequality-constrained linear program IP. The main problem we are concerned with is to show that thestrong duality condition for IP holds, so that IP and its dual IP* are both solvable and their optimal values coincide. To do this, we first express IP as a convex program with a Lagrangian function L, say. Then we show that the strong duality condition implies the existence of a saddle point for L, and that, under an additional, mild condition, theconverse is also true. Moreover, the saddle point gives optimal solutions for IP and IP*. Thus, our original problem is essentially reduced to prove the existence of a saddle point for L, which is shown to be the case under suitable assumptions. We use this fact to studyequality-constrained programs, and we illustrate our main results with applications to thegeneral capacity and themass transfer problems. This research was partially supported by the Consejo Nacional de Ciencia y Tecnología (CONACYT) grants 32299-E and 37355-E. It was also supported by CONACYT (for JRG and RRLM) and PROMEP (for JRG) scholarships.     

An LPCC approach to nonconvex quadratic programs

Filling a gap in nonconvex quadratic programming, this paper shows that the global resolution of a feasible quadratic program (QP), which is not known a priori to be bounded or unbounded below, can be accomplished in finite time by solving two linear programs with linear complementarity constraints, i.e., LPCCs. Specifically, this task can be divided into two LPCCs: the first confirms whether the QP is bounded below on the feasible set and, if not, computes a feasible ray on which the QP is unbounded; the second LPCC computes a globally optimal solution if it exists, by identifying a stationary point that yields the best quadratic objective value. In turn, the global resolution of these LPCCs can be accomplished by a parameter-free, mixed integer-programming based, finitely terminating algorithm developed recently by the authors, which can be enhanced in this context by a new kind of valid cut derived from the second-order conditions of the QP and by exploiting the special structure of the LPCCs. Throughout, our treatment makes no boundedness assumption of the QP; this is a significant departure from much of the existing literature which consistently employs the boundedness of the feasible set as a blanket assumption. The general theory is illustrated by 3 classes of indefinite problems: QPs with simple upper and lower bounds (existence of optimal solutions is guaranteed); same QPs with an additional inequality constraint (extending the case of simple bound constraints); and nonnegatively constrained copositive QPs (no guarantee of the existence of an optimal solution). We also present numerical results to support the special cuts obtained due to the QP connection.     

Unconstrained duals to partially separable constrained programs

In this note partially separable convex programs are dualized in such a way that, under certain assumptions, unconstrained concave duals arise. A return formula is given by which the solution of the primal is directly computed if a solution of the dual is known. Further, the solvability of both the primal and the dual is shown to depend essentially on the behaviour of the lower dimensional programs for determining the Fenchel conjugates.     

An approach to the numerical solutions of geometric programs

An algorithm for solving ordinary geometric programs is presented. The algorithm is based on the reduced system associated with geometric programs and is highly flexible in that it allows the use of several nonlinear optimization techniques.     

Relaxation of optimal control problems to equivalent convex programs

Relaxed controls induce convexity of the velocity sets in optimal control problems, permitting a general existence theory. Here we obtain complete convexity, of the set of control-trajectory pairs, by relaxing the problem constraints to admit certain measures on the product of the control and trajectory spaces. It is proved that these measures are just unit mixtures of control-trajectory pairs and that admitting them does not alter the minimum value of the control problems. This can be used to derive necessary and sufficient conditions for optimality of dynamic programming type.