Optima of dual integer linear programs

We consider dual pairs of packing and covering integer linear programs. Best possible bounds are found between their optimal values. Tight inequalities are obtained relating the integral optima and the optimal rational solutions.     

The dual simplex method and sensitivity analysis for fuzzy linear programming with symmetric trapezoidal numbers

In this paper, we first extend the dual simplex method to a type of fuzzy linear programming problem involving symmetric trapezoidal fuzzy numbers. The results obtained lead to a solution for fuzzy linear programming problems that does not require their conversion into crisp linear programming problems. We then study the ranges of values we can achieve so that when changes to the data of the problem are introduced, the fuzzy optimal solution remains invariant. Finally, we obtain the optimal value function with fuzzy coefficients in each case, and the results are described by means of numerical examples.     

Using bounds on the data in linear programming: The tolerance approach to sensitivity analysis

In contrast to traditional sensitivity analysis in linear programming, the tolerance approach considers simultaneous and independent variations in a number of parameters. A primary focus of this approach is to determine a maximum tolerance percentage for selected right-hand-side terms in which the same basis is optimal as long as each term is accurate to within that percentage of its estimated value. Similarly, the approach yields a maximum tolerance percentage for selected objective function coefficients. This paper shows how the tolerance approach can exploit information on the range of possible values over which terms and coefficients can vary to yield larger maximum tolerance percentages.     

Optimization and data structure: Seven faces of dual scaling

Dual scaling can be looked at as several different optimization problems, which suggests a number of optimal properties inherent in this scaling method. This study identifies some of its old and new aspects, providing a brief, but comprehensive, characterization of dual scaling. It is important to be aware of its limitations as well as possibilities, particularly because the method is deterministic or mathematical rather than probabilistic or statistical, hence rendering it a greater risk of misapplication. Seven key characteristics of dual scaling are identified and discussed.     

Probabilistic constraints in primal and dual linear programs: Duality results

We present two pairs of dually related probabilistic constrained problems as extensions of the linear programming duality concept. In the first pair, a bilinear function appears in the objectives and each objective directly depends on the feasibility set of the other problem, as in the game theoretical formulation of dual linear programs. In the second pair, we reformulate the objectives and eliminate their direct dependence on the feasibility set of the other problem. We develop conditions under which the dually related problems have no duality gap and conditions under which the two pairs of problems are equivalent as far as their optimality sets are concerned.     

When not to analyze data: Decision making on missing responses in dual scaling

In exploratory data analysis, handling of missing responses requires special considerations because of the absence of a model for them. This study investigates effects of missing responses on dual scaling results, in particular a practical decision rule when to and not to impute for missing responses. More specifically, three questions are asked: when to discard a subject, when to exclude a variable, and when to stop data analysis entirely. The decision rule is based on the concept of substantial discrepancy in the scaling outcome between the best and worst imputations for missing responses. This problem is discussed in the context of the current knowledge on missing responses in data analysis.     

On some relations between a dual pair of multiple objective linear programs

Summary This paper is a contribution to the theory of multiple objective linear programming. Existence and duality properties for multiple objective linear programs are developed which contain the fundamental existence and duality results of linear programming as special cases. Several implications of the duality results will be indicated.

---

Zusammenfassung In diesem Beitrag werden einige Existenz- und Dualitätsaussagen für lineare Programme mit mehreren Zielfunktionen (Vektoroptimierungsprobleme) vorgestellt. Es wird gezeigt, daß diese Aussagen die Existenz- und Dualitätsaussagen der linearen Programmierung als Spezialfälle enthalten.

     

Solving the subproblem in the lagrangian dual of separable discrete programs with linear constraints

This note presents an efficient method for the routine solution of the subproblem associated with the Lagrangian dual of discrete programming problems having separable non-linear objective function and linear constraints. An additional advantage for subgradient methods is described.     

Approaches to sensitivity analysis in linear programming

A continuing priority in sensitivity and parametric analysis is to develop approaches that provide useful information, that are easy for a decision-maker to use, and that are computationally practical. Herein we review approaches to sensitivity analysis in linear programming and discuss how they meet the above needs. Special emphasis is given to sensitivity analysis of the objective function coefficients.The second author gratefully acknowledges financial support from the National Science Foundation under grant ECS-8615302.     

Generalized sensitivity analysis of nonlinear programs using a sequence of quadratic programs

ABSTRACT

Local sensitivity information is obtained for KKT points of parametric NLPs that may exhibit active set changes under parametric perturbations; under appropriate regularity conditions, computationally relevant generalized derivatives of primal and dual variable solutions of parametric NLPs are calculated. Ralph and Dempe obtained directional derivatives of solutions of parametric NLPs exhibiting active set changes from the unique solution of an auxiliary quadratic program. This article uses lexicographic directional derivatives, a newly developed tool in nonsmooth analysis, to generalize the classical NLP sensitivity analysis theory of Ralph and Dempe. By viewing said auxiliary quadratic program as a parametric NLP, the results of Ralph and Dempe are applied to furnish a sequence of coupled QPs, whose unique solutions yield generalized derivative information for the NLP. A practically implementable algorithm is provided. The theory developed here is motivated by widespread applications of nonlinear programming sensitivity analysis, such as in dynamic control and optimization problems.     

Strong duality and sensitivity analysis in semi-infinite linear programming

Finite-dimensional linear programs satisfy strong duality (SD) and have the “dual pricing” (DP) property. The DP property ensures that, given a sufficiently small perturbation of the right-hand-side vector, there exists a dual solution that correctly “prices” the perturbation by computing the exact change in the optimal objective function value. These properties may fail in semi-infinite linear programming where the constraint vector space is infinite dimensional. Unlike the finite-dimensional case, in semi-infinite linear programs the constraint vector space is a modeling choice. We show that, for a sufficiently restricted vector space, both SD and DP always hold, at the cost of restricting the perturbations to that space. The main goal of the paper is to extend this restricted space to the largest possible constraint space where SD and DP hold. Once SD or DP fail for a given constraint space, then these conditions fail for all larger constraint spaces. We give sufficient conditions for when SD and DP hold in an extended constraint space. Our results require the use of linear functionals that are singular or purely finitely additive and thus not representable as finite support vectors. We use the extension of the Fourier–Motzkin elimination procedure to semi-infinite linear systems to understand these linear functionals.     

An iterative method,having linear rate of convergence,for solving a pair of dual linear programs

An iterative method for dual linear programming problems is described, and its rate of convergence is established.On leave of absence from IBM Research Laboratory, Ruschlikon, Switzerland.     

The computational complexity of multi-level linear programs

We show that (L+1)-level linear programs are as difficult as levelL of the polynomial-time hierarchy, even if one only considers problems with unique optimal solutions.Dedicated to Robert Jeroslow (1942–1988)     

The dual of a fractional linear program

A linear fractional program is shown, under certain restrictions, to have a fractional linear program as its dual.     

Error analysis for convex separable programs: Bounds on optimal and dual optimal solutions

Computable lower and upper bounds on the optimal and dual optimal solutions of a nonlinear, convex separable program are obtained from its piecewise linear approximation. They provide traditional error and sensitivity measures and are shown to be attainable for some problems. In addition, the bounds on the solution can be used to develop an efficient solution approach for such programs, and the dual bounds enable us to determine a subdivision interval which insures the objective function accuracy of a prespecified level. A generalization of the bounds to certain separable, but nonconvex, programs is given and some numerical examples are included.     

Second order sensitivity analysis and asymptotic theory of parametrized nonlinear programs

In this paper we study second-order differential properties of an optimal-value function(x). It is shown that under certain conditions(x) possesses second-order directional derivatives, which can be calculated by solving corresponding quadratic programs. Also upper and lower bounds on these derivatives are introduced under weaker assumptions. In particular we show that the second-order directional derivative is infinite if the corresponding quadratic program is unbounded. Finally sensitivity results are applied to investigate asymptotics of estimators in parametrized nonlinear programs.     

Tolerance approach to sensitivity analysis in linear complementarity problems

In this paper, we apply the tolerance approach proposed by Wendell for sensitivity analysis in linear programs to study sensitivity analysis in linear complementarity problems. In the tolerance approach, we find the range or the maximum tolerance within which the coefficients of the right-hand side of the problem can vary simultaneously and independently such that the solution of the original and the perturbed problems have the same index set of nonzero elements.The work of the first author was completed while he was at Virginia Commonwealth University, Richmond, Virginia.     

The impact of sampling methods on bias and variance in stochastic linear programs

Stochastic linear programs can be solved approximately by drawing a subset of all possible random scenarios and solving the problem based on this subset, an approach known as sample average approximation (SAA). The value of the objective function at the optimal solution obtained via SAA provides an estimate of the true optimal objective function value. This estimator is known to be optimistically biased; the expected optimal objective function value for the sampled problem is lower (for minimization problems) than the optimal objective function value for the true problem. We investigate how two alternative sampling methods, antithetic variates (AV) and Latin Hypercube (LH) sampling, affect both the bias and variance, and thus the mean squared error (MSE), of this estimator. For a simple example, we analytically express the reductions in bias and variance obtained by these two alternative sampling methods. For eight test problems from the literature, we computationally investigate the impact of these sampling methods on bias and variance. We find that both sampling methods are effective at reducing mean squared error, with Latin Hypercube sampling outperforming antithetic variates. For our analytic example and the eight test problems we derive or estimate the condition number as defined in Shapiro et al. (Math. Program. 94:1–19, 2002). We find that for ill-conditioned problems, bias plays a larger role in MSE, and AV and LH sampling methods are more likely to reduce bias.     

Bi-parametric optimal partition invariancy sensitivity analysis in linear optimization

In bi-parametric linear optimization (LO), perturbation occurs in both the right-hand-side and the objective function data with different parameters. In this paper, the bi-parametric LO problem is considered and we are interested in identifying the regions where the optimal partitions are invariant. These regions are referred to as invariancy regions. It is proved that invariancy regions are separated by vertical and horizontal lines and generate a mesh-like area. It is proved that the boundaries of these regions can be identified in polynomial time. The behavior of the optimal value function on these regions is investigated too.