Duality and statistical tests of optimality for two stage stochastic programs

We present alternative methods for verifying the quality of a proposed solution to a two stage stochastic program with recourse. Our methods revolve around implications of a dual problem in which dual multipliers on the nonanticipativity constraints play a critical role. Using randomly sampled observations of the stochastic elements, we introduce notions of statistical dual feasibility and sampled error bounds. Additionally, we use the nonanticipativity multipliers to develop connections to reduced gradient methods. Finally, we propose a statistical test based on directional derivatives. We illustrate the applicability of these tests via some examples. This work was supported in part by Grant No. NSF-DMI-9414680 from the National Science Foundation     

非凸异分母分式多目标规划解的充分条件及对偶定理

指出了文[6]中的一个错误，基于不变凸性，对异分母分式多目标规划进行了讨论．在简单的正交假设下，给出了一系列解的充分条件，并建立了Mond－Weir型对偶定理．     

Duality and saddle-point type optimality for generalized nonlinear fractional programming

In this paper, we establish two theorems of alternative with generalized subconvexlikeness. We introduce two dual models for a generalized fractional programming problem. Theorems of alternative are then applied to establish duality theorems and a saddle-point type optimality condition.     

Solutions and optimality criteria for nonconvex quadratic-exponential minimization problem

This paper presents a set of complete solutions and optimality conditions for a nonconvex quadratic-exponential optimization problem. By using the canonical duality theory developed by the first author, the nonconvex primal problem in n-dimensional space can be converted into an one-dimensional canonical dual problem with zero duality gap, which can be solved easily to obtain all dual solutions. Each dual solution leads to a primal solution. Both global and local extremality conditions of these primal solutions can be identified by the triality theory associated with the canonical duality theory. Several examples are illustrated.     

On Minimax Fractional Optimality and Duality with Generalized Convexity

In this paper, we establish several sufficient optimality conditions for a class of generalized minimax fractional programming. Based on the sufficient conditions, a new dual model is constructed and duality results are derived. Our study naturally unifies and extends some previously known results in the framework of generalized convexity and dual models. Mathematics Subject Classifications: 90C25, 90C32, 90C47.     

The nonlinear bilevel programming problem:formulations,regularity and optimality conditions

In this paper, we study regularity and optimality conditions for the BLPP by using a marginal function formulation, where the marginal function is defined by the optimal value function of the lower problem. We address the regularity issue by exploring the structure of the tangent cones of the feasible set of the BLPP. These regularity results indicate that the nonlinear/nonlinear BLPP is most likely degenerate and a class of nonlinear/linear BLPP is regular in the conventional sense. Existence of exact penalty function is proved for a class of nonlinear/linear BLPP. Fritz-John type optimality conditions are derived for nonlinear BLPP, while KKT type conditions are obtained for a class of nonlinear/linear BLPP in the framework of nonsmooth analysis. A typical example is examined for these conditions and some applications of these conditions are pointed out     

On the adjustment problem for linear programs

We propose a generalization of the inverse problem which we will call the adjustment problem. For an optimization problem with linear objective function and its restriction defined by a given subset of feasible solutions, the adjustment problem consists in finding the least costly perturbations of the original objective function coefficients, which guarantee that an optimal solution of the perturbed problem is also feasible for the considered restriction. We describe a method of solving the adjustment problem for continuous linear programming problems when variables in the restriction are required to be binary.     

Max-min sum minimization transportation problem

A non-convex optimization problem involving minimization of the sum of max and min concave functions over a transportation polytope is studied in this paper. Based upon solving at most (g+1)(< p) cost minimizing transportation problems with m sources and n destinations, a polynomial time algorithm is proposed which minimizes the concave objective function where, p is the number of pairwise disjoint entries in the m× n time matrix {t _ij } sorted decreasingly and T ^g is the minimum value of the max concave function. An exact global minimizer is obtained in a finite number of iterations. A numerical illustration and computational experience on the proposed algorithm is also included. We are thankful to Prof. S. N. Kabadi, University of New Brunswick-Fredericton, Canada, who initiated us to the type of problem discussed in this paper. We are also thankful to Mr. Ankit Khandelwal, Ms. Neha Gupta and Ms. Anuradha Beniwal, who greatly helped us in the implementation of the proposed algorithm.     

On the combinatorial structure of the permutation flow shop problem

In this paper we investigate the combinatorial structure of then/m/P/C _max permutation flow shop problem. To each solution (a permutation ofn elements) we introduce a network which represents the job and machine orders. Based on the introduced generalized distance between a permutation and a path of a network we derive combinatorial properties with respect to special neighbourhoods which are important for developing iterative heuristics for the considered problem.For several neighbourhood structures we calculate the mean cardinality of reduced neighbourhoods where each neighbour satisfies a necessary condition for an objective improvement.

---

Zusammenfassung In der vorliegenden Arbeit wird die kombinatorische Struktur desn/m/P/C _max Permutationsflußproblems untersucht. Zu jeder zulässigen Lösung, beschreibbar durch eine Permutation vonn Elementen, wird ein Netzplan eingeführt, der die Bearbeitungsreihenfolge der Operationen charakterisiert. Aufbauend auf einem eingeführten verallgemeinerten Abstand zwischen einer Permutation und einem Weg in einem Netzplan werden danach einige kombinatorische Eigenschaften bezüglich spezieller Nachbarschaftsstrukturen abgeleitet, die im Hinblick auf die Entwicklung von iterativen Heuristiken für das betrachtete Problem von Bedeutung sind. So werden u. a. für ausgewählte Nachbarschaftsstrukturen mittlere Mächtigkeiten reduzierter Nachbarschaften, bei denen jeder Nachbar eine notwendige Bedingung für eine Zielfunktionswertverbesserung erfüllt, hergeleitet.

     

Chapter 5 Duality,classification and slacks in DEA

This paper presents seven theorems which expand understanding of the theoretical structure of the Charnes-Cooper-Rhodes (CCR) model of Data Envelopment Analysis, especially with respect to slacks and the underlying structure of facets and faces. These theorems also serve as a basis for new algorithms which will provide optimal primal and dual solutions that satisfy the strong complementary slackness conditions (SCSC) for many (if not most) non-radially efficient DMUs; an improved procedure for identifying the setE of extreme efficient DMUs; and may, for many DEA domains, also settle in a single pass the existence or non-existence of input or output slacks in each of their DMUs. This paper also introduces the concept of a positivegoal vector G, which is applied to characterize the set of all possible maximal optimal slack vectors. The appendix C presents an example which illustrates the need for a new concept,face regular, which focuses on the role of convexity in the intersections of radial efficient facets with the efficient frontier FR. The same example also illustrates flaws in the popular sum of the slacks methodology.R.M. Thrall is Professor of Administration and Noah Harding Professor of Mathematical Sciences, Emeritus, Rice University.     

A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem

In this article, we present and validate a simplicial branch and bound duality-bounds algorithm for globally solving the linear sum-of-ratios fractional program. The algorithm computes the lower bounds called for during the branch and bound search by solving ordinary linear programming problems. These problems are derived by using Lagrangian duality theory. The algorithm applies to a wide class of linear sum-of-ratios fractional programs. Two sample problems are solved, and the potential practical and computational advantages of the algorithm are indicated.     

An exact algorithm for the fixed-charge multiple knapsack problem

We formulate the fixed-charge multiple knapsack problem (FCMKP) as an extension of the multiple knapsack problem (MKP). The Lagrangian relaxation problem is easily solved, and together with a greedy heuristic we obtain a pair of upper and lower bounds quickly. We make use of these bounds in the pegging test to reduce the problem size. We also present a branch-and-bound (B&B) algorithm to solve FCMKP to optimality. This algorithm exploits the Lagrangian upper bound as well as the pegging result for pruning, and at each terminal subproblem solve MKP exactly by invoking MULKNAP code developed by Pisinger [Pisinger, D., 1999. An exact algorithm for large multiple knapsack problems. European Journal of Operational Research 114, 528–541]. As a result, we are able to solve almost all test problems with up to 32,000 items and 50 knapsacks within a few seconds on an ordinary computing environment, although the algorithm remains some weakness for small instances with relatively many knapsacks.     

Necessary optimality conditions in an abnormal optimization problem with equality constraints

An abnormal minimization problem with equality constraints and a finite-dimensional image is examined. Second-order necessary conditions for this problem are given that strengthen previously known results.     

Fractional order boundary value problem with integral boundary conditions involving Pettis integral

In this article, we investigate the existence of Pseudo solutions for some fractional order boundary value problem with integral boundary conditions in the Banach space of continuous function equipped with its weak topology. The class of such problems constitute a very interesting and important class of problems. They include two, three, multi-point and nonlocal boundary-value problems as special cases. In our investigation, the right hand side of the above problem is assumed to be Pettis integrable function. To encompass the full scope of this article, we give an example illustrating the main result.     

Finite-dimensional optimality conditions: B-gradients

The B-gradients are a convex set of generalized gradients contained in Clarke's generalized gradients. These gradients retain many of the nice properties of Clarke's generalized gradients. In this paper, necessary conditions for optimality in finite-dimensional perturbed optimization problems are given. A calmness condition is used for a constraint qualification.     

Local optimality conditions for multicommodity flow problems with separable piecewise convex costs

We consider here a multicommodity flow network optimization problem with non-convex but piecewise convex arc cost functions. We derive complete optimality conditions for local minima based on negative-cost cycles associated with each commodity. These conditions do not extend to the convex non-smooth case.     

A note on the minimum interval cost flow problem

We reduce the problem of minimum interval cost flow problem (MICFP) introduced by Hashemi et al. (2006) to the well-known minimum cost flow problem (MCFP).     

Optimality Conditions and Duality for a Class of Nonlinear Fractional Programming Problems

In this paper, we present sufficient optimality conditions and duality results for a class of nonlinear fractional programming problems. Our results are based on the properties of sublinear functionals and generalized convex functions.     

On optimality and duality theorems of nonlinear disjunctive fractional minmax programs

This paper is concerned with the study of optimality conditions for disjunctive fractional minmax programming problems in which the decision set can be considered as a union of a family of convex sets. Dinkelbach’s global optimization approach for finding the global maximum of the fractional programming problem is discussed. Using the Lagrangian function definition for this type of problem, the Kuhn–Tucker saddle point and stationary-point problems are established. In addition, via the concepts of Mond–Weir type duality and Schaible type duality, a general dual problem is formulated and some weak, strong and converse duality theorems are proven.