Mean value cross decomposition applied to integer programming problems

The mean value cross decomposition method for linear programming problems is a modification of ordinary cross decomposition, that eliminates the need for using the Benders or Dantzig-Wolfe master problems. As input to the dual subproblem the average of a part of all known dual solutions of the primal subproblem is used, and as input to the primal subproblem the average of a part of all known primal solutions of the dual subproblem. In this paper we study the lower bounds on the optimal objective function value of (linear) pure integer programming problems obtainable by the application of mean value cross decomposition, and find that this approach can be used to get lower bounds ranging from the bound obtained by the LP-relaxation to the bound obtained by the Lagrangean dual. We examplify by applying the technique to the clustering problem and give some preliminary computational results.     

Nonanticipative duality,relaxations, and formulations for chance-constrained stochastic programs

We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation bounds can be calculated by solving a set of single scenario subproblems and then solving a single knapsack problem. We also derive two new primal MIP formulations and demonstrate that for chance-constrained linear programs, the continuous relaxations of these formulations yield bounds equal to the proposed dual bounds. We propose a new heuristic method and two new exact algorithms based on these duals and formulations. The first exact algorithm applies to chance-constrained binary programs, and uses either of the proposed dual bounds in concert with cuts that eliminate solutions found by the subproblems. The second exact method is a branch-and-cut algorithm for solving either of the primal formulations. Our computational results indicate that the proposed dual bounds and heuristic solutions can be obtained efficiently, and the gaps between the best dual bounds and the heuristic solutions are small.     

A dual ascent approach to the fixed-charge capacitated network design problem

In this paper we consider the problem of constructing a network over which a number of commodities are to be transported. Fixed costs are associated to the construction of network arcs and variable costs are associated to routing of commodities. In addition, one capacity constraint is related to each arc. The problem is to determine a network design that minimizes the total cost; i.e., it balances the construction and operating costs. A dual ascent procedure for finding improved lower bounds and near-optimal solutions for the fixed-charge capacitated network design problem is proposed. The method is shown to generate tighter lower bounds than the linear programming relaxation of the problem.     

Approximate solutions to Dirichlet control problems for the wave equation in Sobolev classes and dual observation problems

Dual control and observation problems for the wave equation with variable coefficients subject to Dirichlet boundary conditions are solved by a variational method. This method was earlier proposed by the author for an approximate analysis of linear equations with nonuniform perturbations of the operator. Explicit bounds on the constant that are required to implement the method are obtained using the correct solvability property of the dual observation problem. Finite-dimensional approximations of the control and observation problems are obtained by the difference method preserving the duality relation. The convergence of approximate solutions is established in the norms of the corresponding dual spaces.     

The discrete moment problem with fractional moments

Discrete moment problems (DMP) with integer moments were first introduced by Prékopa to provide sharp lower and upper bounds for functions of discrete random variables. Prékopa also developed fast and stable dual type linear programming methods for the numerical solutions of the problem. In this paper, we assume that some fractional moments are also available and propose basic theory and a solution method for the bounding problems. Numerical experiments show significant improvement in the tightness of the bounds.     

Interior dual proximal point algorithm using preconditioned conjugate gradient †

Serial and parallel implementations of the interior dual proximal point algorithm for the solution of large linear programs are described. A preconditioned conjugate gradient method is used to solve the linear system of equations that arises at each interior point interation. Numerical results for a set of multicommodity network flow problems are given. For larger problem preconditioned conjugate gradient method outperforms direct methods of solution. In fact it is impossible to handle very large problems by direct methods     

A Branch and Bound Method for Solving Integer Separable Concave Problems

A branch and bound algorithm is proposed for solving integer separable concave problems. The method uses Lagrangian duality to obtain lower and upper bounds. We show that the dual program of a separable concave problem is a linear program. Moreover, we identify an excellent candidate to test on each region of the branch and we show an optimality sufficient condition for this candidate. Preliminary computational results are reported.     

Linear programming for weighted deviation problems using compact basis techniques

Weighted deviation problems are linear programs in which weights (or penalties) are attached to deviations from upper and lower bounds on particular linear expressions. In turn the deviations may be bracketed by secondary bounds. These problems include statistical problems of minimizing weighted sums of absolute deviations, standard and extended “goal programming” problems, problems with upper bounds on absolute values of linear affine functions, problems with arbitrarily bounded variables, and combinations of these.Previous specialized linear programming methods for related problems have been restricted to specialized cases that involve only a single basis configuration, or else, by means of “extended GUB” techniques, accommodate a diverse variety of basis structures at the cost of substantially increased computation. We show that, of the several basis configurations that can arise for this problem, precisely three are essential. Special rules are identified to allow transitions between these three structures, to yield valid compact versions of both the primal and the dual simplex methods. Finally, we show how these results lead to improved efficiency as well as reduced problem size.     

The dual reciprocity boundary integral equation technique to solve a class of the linear and nonlinear fractional partial differential equations

In this paper, we apply the boundary integral equation technique and the dual reciprocity boundary elements method (DRBEM) for the numerical solution of linear and nonlinear time‐fractional partial differential equations (TFPDEs). The main aim of the present paper is to examine the applicability and efficiency of DRBEM for solving TFPDEs. We employ the time‐stepping scheme to approximate the time derivative, and the method of linear radial basis functions is also used in the DRBEM technique. This method is improved by using a predictor–corrector scheme to overcome the nonlinearity that appears in the nonlinear problems under consideration. To confirm the accuracy of the new approach, several examples are presented. The convergence of the DRBEM is studied numerically by comparing the exact solutions of the problems under investigation. Copyright © 2015 John Wiley & Sons, Ltd.     

Solving Continuous-Time Linear Programming Problems Based on the Piecewise Continuous Functions

The numerical method is proposed in this article to solve a general class of continuous-time linear programming problems in which the functions appeared in the coefficients of this problem are assumed to be piecewise continuous. In order to make sure that all the subintervals of time interval will not contain the discontinuities, a different methodology for not equally partitioning the time interval is proposed. The main issue of this article is to obtain an analytic formula of error upper bound. In this article, we shall propose two kinds of computational procedure to evaluate the error upper bounds. One needs to solve the dual problem of the discretized linear programming problem, and another one does not need to solve the dual problem. Finally, we present a numerical example to demonstrate the usefulness of the numerical method.     

Approximate Operators and Dual Extremum Principles for Linear Problems

The use of approximate operators in the theory of dual extremumprinciples is investigated for certain linear problems. If second-ordertrial functions to certain approximate Lagrangian equationscan be found, bounds which are improvements on the dual boundingfunctions can be constructed. Some simple applications to apartial differential equation and an integral equation are given.It is shown that both upper and lower bounds follow from onetrial function.     

Application of the dual active set algorithm to quadratic network optimization

A new algorithm, the dual active set algorithm, is presented for solving a minimization problem with equality constraints and bounds on the variables. The algorithm identifies the active bound constraints by maximizing an unconstrained dual function in a finite number of iterations. Convergence of the method is established, and it is applied to convex quadratic programming. In its implementable form, the algorithm is combined with the proximal point method. A computational study of large-scale quadratic network problems compares the algorithm to a coordinate ascent method and to conjugate gradient methods for the dual problem. This study shows that combining the new algorithm with the nonlinear conjugate gradient method is particularly effective on difficult network problems from the literature.     

Optimal value range in interval linear programming

We deal with the linear programming problem in which input data can vary in some given real compact intervals. The aim is to compute the exact range of the optimal value function. We present a general approach to the situation the feasible set is described by an arbitrary linear interval system. Moreover, certain dependencies between the constraint matrix coefficients can be involved. As long as we are able to characterize the primal and dual solution set (the set of all possible primal and dual feasible solutions, respectively), the bounds of the objective function result from two nonlinear programming problems. We demonstrate our approach on various cases of the interval linear programming problem (with and without dependencies).     

Preconditioning and globalizing conjugate gradients in dual space for quadratically penalized nonlinear-least squares problems

When solving nonlinear least-squares problems, it is often useful to regularize the problem using a quadratic term, a practice which is especially common in applications arising in inverse calculations. A solution method derived from a trust-region Gauss-Newton algorithm is analyzed for such applications, where, contrary to the standard algorithm, the least-squares subproblem solved at each iteration of the method is rewritten as a quadratic minimization subject to linear equality constraints. This allows the exploitation of duality properties of the associated linearized problems. This paper considers a recent conjugate-gradient-like method which performs the quadratic minimization in the dual space and produces, in exact arithmetic, the same iterates as those produced by a standard conjugate-gradients method in the primal space. This dual algorithm is computationally interesting whenever the dimension of the dual space is significantly smaller than that of the primal space, yielding gains in terms of both memory usage and computational cost. The relation between this dual space solver and PSAS (Physical-space Statistical Analysis System), another well-known dual space technique used in data assimilation problems, is explained. The use of an effective preconditioning technique is proposed and refined convergence bounds derived, which results in a practical solution method. Finally, stopping rules adequate for a trust-region solver are proposed in the dual space, providing iterates that are equivalent to those obtained with a Steihaug-Toint truncated conjugate-gradient method in the primal space.     

On multilevel iterative methods for optimization problems

This paper is concerned with multilevel iterative methods which combine a descent scheme with a hierarchy of auxiliary problems in lower dimensional subspaces. The construction of auxiliary problems as well as applications to elasto-plastic model and linear programming are described. The auxiliary problem for the dual of a perturbed linear program is interpreted as a dual of perturbed aggregated linear program. Coercivity of the objective function over the feasible set is sufficient for the boundedness of the iterates. Equivalents of this condition are presented in special cases.Supported by NSF under grant DMS-8704169, AFOSR under grant 86-0126, and ONR under Contract N00014-83-K-0104. Consulting for American Airlines Decision Technologies, MD 2C55, P.O. Box 619616, DFW, TX 75261-9616, USA.Supported by NSF under grant DMS-8704169 and AFOSR under grant 86-0126.     

Bounding a class of nonconvex linearly-constrained resource allocation problems via the surrogate dual

We consider a class of problems of resource allocation under economies of scale, namely that of minimizing a lower semicontinuous, isotone, and explicitly quasiconcave cost function subject to linear constraints. An important class of algorithms for the linearly constrained minimization of nonconvex cost functions utilize the branch and bound approach, using convex underestimating cost functions to compute the lower bounds.We suggest instead the use of the surrogate dual problem to bound subproblems. We show that the success of the surrogate dual in fathoming subproblems in a branch and bound algorithm may be determined without directly solving the surrogate dual itself, but that a simple test of the feasibility of a certain linear system of inequalities will suffice. This test is interpreted geometrically and used to characterize the extreme points and extreme rays of the optimal value function's level sets.Research partially supported by NSF under grant # ENG77-06555.     

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.     

Valid inequalities for problems with additive variable upper bounds

We study the facial structure of a polyhedron associated with the single node relaxation of network flow problems with additive variable upper bounds. This type of structure arises, for example, in production planning problems with setup times and in network certain expansion problems. We derive several classes of valid inequalities for this polyhedron and give conditions under which they are facet–defining. Our computational experience with large network expansion problems indicates that these inequalities are very effective in improving the quality of the linear programming relaxations. Received: April 15, 1999 / Accepted: October 10, 2000?Published online May 18, 2001     

Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming

In exact arithmetic, the simplex method applied to a particular linear programming problem instance with real data either shows that it is infeasible, shows that its dual is infeasible, or generates optimal solutions to both problems. Most interior-point methods, on the other hand, do not provide such clear-cut information. If the primal and dual problems have bounded nonempty sets of optimal solutions, they usually generate a sequence of primal or primaldual iterates that approach feasibility and optimality. But if the primal or dual instance is infeasible, most methods give less precise diagnostics. There are methods with finite convergence to an exact solution even with real data. Unfortunately, bounds on the required number of iterations for such methods applied to instances with real data are very hard to calculate and often quite large. Our concern is with obtaining information from inexact solutions after a moderate number of iterations. We provide general tools (extensions of the Farkas lemma) for concluding that a problem or its dual is likely (in a certain well-defined sense) to be infeasible, and apply them to develop stopping rules for a homogeneous self-dual algorithm and for a generic infeasible-interior-point method for linear programming. These rules allow precise conclusions to be drawn about the linear programming problem and its dual: either near-optimal solutions are produced, or we obtain certificates that all optimal solutions, or all feasible solutions to the primal or dual, must have large norm. Our rules thus allow more definitive interpretation of the output of such an algorithm than previous termination criteria. We give bounds on the number of iterations required before these rules apply. Our tools may also be useful for other iterative methods for linear programming. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

The dual reciprocity boundary elements method for the linear and nonlinear two‐dimensional time‐fractional partial differential equations

In this paper, we apply the dual reciprocity boundary elements method for the numerical solution of two‐dimensional linear and nonlinear time‐fractional modified anomalous subdiffusion equations and time‐fractional convection–diffusion equation. The fractional derivative of problems is described in the Riemann–Liouville and Caputo senses. We employ the linear radial basis function for interpolation of the nonlinear, inhomogeneous and time derivative terms. This method is improved by using a predictor–corrector scheme to overcome the nonlinearity which appears in the nonlinear problems under consideration. The accuracy and efficiency of the proposed schemes are checked by five test problems. The proposed method is employed for solving some examples in two dimensions on unit square and also in complex regions to demonstrate the efficiency of the new technique. Copyright © 2016 John Wiley & Sons, Ltd.