A comprehensive simplex-like algorithm for network optimization and perturbation analysis

The family of network optimization problems includes the following prototype models: assignment, critical path, max flow, shortest path, and transportation. Although it is long known that these problems can be modeled as linear programs (LP), this is generally not done. Due to the relative inefficiency and complexity of the simplex methods (primal, dual, and other variations) for network models, these problems are usually treated by one of over 100 specialized algorithms. This leads to several difficulties. The solution algorithms are not unified and each algorithm uses a different strategy to exploit the special structure of a specific problem. Furthermore, small variations in the problem, such as the introduction of side constraints, destroys the special structure and requires modifying andjor restarting the algorithm. Also, these algorithms obtain solution efficiency at the expense of managerial insight, as the final solutions from these algorithms do not have sufficient information to perform postoptimality analysis.

Another approach is to adapt the simplex to network optimization problems through network simplex. This provides unification of the various problems but maintains all the inefficiencies of simplex, as well as, most of the network inflexibility to handle changes such as side constraints. Even ordinary sensitivity analysis (OSA), long available in the tabular simplex, has been only recently transferred to network simplex.

This paper provides a single unified algorithm for all five network models. The proposed solution algorithm is a variant of the self-dual simplex with a warm start. This algorithm makes available the full power of LP perturbation analysis (PA) extended to handle optimal degeneracy. In contrast to OSA, the proposed PA provides ranges for which the current optimal strategy remains optimal, for simultaneous dependent or independent changes from the nominal values in costs, arc capacities, or suppliesJdemands. The proposed solution algorithm also facilitates incorporation of network structural changes and side constraints. It has the advantage of being computationally practical, easy for managers to understand and use, and provides useful PA information in all cases. Computer implementation issues are discussed and illustrative numerical examples are provided in the Appendix     

Parallel collocation solution of index-1 BVP-DAEs arising from constrained optimal control problems

The indirect solution of constrained optimal control problems gives rise to two-point boundary value problems (BVPs) that involve index-1 differential-algebraic equations (DAEs) and inequality constraints. This paper presents a parallel collocation algorithm for the solution of these inequality constrained index-1 BVP-DAEs. The numerical algorithm is based on approximating the DAEs using piecewise polynomials on a nonuniform mesh. The collocation method is realized by requiring that the BVP-DAE be satisfied at Lobatto points within each interval of the mesh. A Newton interior-point method is used to solve the collocation equations, and maintain feasibility of the inequality constraints. The implementation of the algorithm involves: (i) parallel evaluation of the collocation equations; (ii) parallel evaluation of the system Jacobian; and (iii) parallel solution of a boarded almost block diagonal (BABD) system to obtain the Newton search direction. Numerical examples show that the parallel implementation provides significant speedup when compared to a sequential version of the algorithm.     

Network planning under uncertainty with an application to hydropower generation

Summary We present a general modeling framework for therobust optimization of linear network problems with uncertainty in the values of the right-hand side. In contrast to traditional approaches in mathematical programming, we use scenarios to characterize the uncertainty. Solutions are obtained for each scenario and these individual scenarios are aggregated to yield a nonanticipative or implementable policy that minimizes the regret of wrong decisions. A given solution is termed robust if it minimizes the sum over the scenarios of the weighted upper difference between the objective function value for the solution and the objective function value for the optimal solution for each scenario, while satisfying certain nonanticipativity constraints. This approach results in a huge model with a network submodel per scenario plus coupling constraints. Several decomposition approaches are considered, namely Dantzig-Wolfe decomposition, various types of Benders decomposition and different quadratic network approaches for approximating Augmented Lagrangian decomposition. We present computational results for these methods, including two implementation versions of the Lagrangian based method: a sequential implementation and a parallel implementation on a network of three workstations.     

A semismooth sequential quadratic programming method for lifted mathematical programs with vanishing constraints

Mathematical programs with vanishing constraints are a difficult class of optimization problems with important applications to optimal topology design problems of mechanical structures. Recently, they have attracted increasingly more attention of experts. The basic difficulty in the analysis and numerical solution of such problems is that their constraints are usually nonregular at the solution. In this paper, a new approach to the numerical solution of these problems is proposed. It is based on their reduction to the so-called lifted mathematical programs with conventional equality and inequality constraints. Special versions of the sequential quadratic programming method are proposed for solving lifted problems. Preliminary numerical results indicate the competitiveness of this approach.     

The minimization of lower subdifferentiable functions under nonlinear constraints: An all feasible cutting plane algorithm

Nonlinear, possibly nonsmooth, minimization problems are considered with boundedly lower subdifferentiable objective and constraints. An algorithm of the cutting plane type is developed, which has the property that the objective needs to be considered at feasible points only. It generates automatically a nondecreasing sequence of lower bounds converging to the optimal function value, thus admitting a rational rule for stopping the calculations when sufficient precision in the objective value has been obtained. Details are given concerning the efficient implementation of the algorithm. Computational results are reported concerning the algorithm as applied to continuous location problems with distance constraints. The author thanks the referees for several constructive remarks and for pointing out an error in an earlier version of the proof of Lemma 2.1.     

Discrete ill-posed least-squares problems with a solution norm constraint

Straightforward solution of discrete ill-posed least-squares problems with error-contaminated data does not, in general, give meaningful results, because propagated error destroys the computed solution. Error propagation can be reduced by imposing constraints on the computed solution. A commonly used constraint is the discrepancy principle, which bounds the norm of the computed solution when applied in conjunction with Tikhonov regularization. Another approach, which recently has received considerable attention, is to explicitly impose a constraint on the norm of the computed solution. For instance, the computed solution may be required to have the same Euclidean norm as the unknown solution of the error-free least-squares problem. We compare these approaches and discuss numerical methods for their implementation, among them a new implementation of the Arnoldi–Tikhonov method. Also solution methods which use both the discrepancy principle and a solution norm constraint are considered.     

Preconditioning by Projectors in the Solution of Contact Problems: A Parallel Implementation

A non-overlapping domain decomposition algorithm of the Neumann–Neumann type for solving contact problems of elasticity is presented. Using the duality theory of convex programming, the discretized problem turns into a quadratic one with equality and bound constraints. The dual problem is modified by orthogonal projectors to the natural coarse space. The resulting problem is solved by an augmented Lagrangian algorithm. The projectors ensure an optimal convergence rate for the solution of the auxiliary linear problems by the preconditioned conjugate gradient method. Relevant aspects on the numerical linear algebra of these problems are presented, together with an efficient parallel implementation of the method.     

Experiments with primal - dual decomposition and subgradient methods for the uncapacitatied facility location problem

For optimization problems that are structured both with respect to the constraints and with respect to the variables, it is possible to use primal–dual solution approaches, based on decomposition principles. One can construct a primal subproblem, by fixing some variables, and a dual subproblem, by relaxing some constraints and king their Lagrange multipliers, so that both these problems are much easier to solve than the original problem. We study methods based on these subproblems, that do not include the difficult Benders or Dantzig-Wolfe master problems, namely primal–dual subgradient optimization methods, mean value cross decomposition, and several comtbinations of the different techniques. In this paper, these solution approaches are applied to the well-known uncapacitated facility location problem. Computational tests show that some combination methods yield near-optimal solutions quicker than the classical dual ascent method of Erlenkotter     

On the Geometry of Point-Plane Constraints on Rigid-Body Displacements

In this paper the rigid-body displacements that transform a point in such a way that it remains on a particular plane are studied. These sets of rigid displacements are referred to as point-plane constraints and are given by the intersection of the Study quadric of all rigid displacements with another quadric in 7-dimensional projective space. The set of all possible point-plane constraints comprise a Segre variety. Two different classes of problems are investigated. First instantaneous kinematics, for a given rigid motion there are points in space which, at some instant, have no torsion or have no curvature to some order. The dimension and degrees of these varieties are found by very simple computations. The corresponding problems for point-sphere constraints are also found. The second class of problems concern the intersections of several given constraints. Again the characteristics of these varieties for different numbers of constraints are found using very simple techniques.     

A Dual Simplex Implementation of a Constraint Selection Algorithm for Linear Programming

The constraint selection approach to linear programming begins by solving a relaxed version of the problem using only a few of the original constraints. If the solution obtained to this relaxation satisfies the remaining constraints it is optimal for the original LP. Otherwise, additional constraints must be incorporated in a larger relaxation. The procedure successively generates larger subproblems until an optimal solution is obtained which satisfies all of the original constraints. Computational results for a dual simplex implementation of this technique indicate that solving several small subproblems in this manner is more computationally efficient than solving the original LP using the revised simplex method.     

Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints

Mathematical programs with equilibrium constraints (MPECs) are difficult optimization problems whose feasible sets do not satisfy most of the standard constraint qualifications. Hence MPECs cause difficulties both from a theoretical and a numerical point of view. As a consequence, a number of MPEC-tailored solution methods have been suggested during the last decade which are known to converge under suitable assumptions. Among these MPEC-tailored solution schemes, the relaxation methods are certainly one of the most prominent class of solution methods. Several different relaxation schemes are available in the meantime, and the aim of this paper is to provide a theoretical and numerical comparison of these schemes. More precisely, in the theoretical part, we improve the convergence theorems of several existing relaxation methods. There, we also take a closer look at the properties of the feasible sets of the relaxed problems and show which standard constraint qualifications are satisfied for these relaxed problems. Finally, the numerical comparison is based on the MacMPEC test problem collection.     

Feasible Direction Algorithm for Optimal Control Problems with State and Control Constraints: Implementation

In this paper, we describe the implementation aspects of an optimization algorithm for optimal control problems with control, state, and terminal constraints presented in our earlier paper. The important aspect of the implementation is that, in the direction-finding subproblems, it is necessary only to impose the state constraint at relatively few points in the time involved. This contributes significantly to the algorithmic efficiency. The algorithm is applied to solve several optimal control problems, including the problem of the abort landing of an aircraft in the presence of windshear.     

Tropical optimization problems in time-constrained project scheduling

We consider a project that consists of activities to be performed in parallel under various temporal constraints, which include start-start, start-finish and finish-start precedence relationships, release times, deadlines and due dates. Scheduling problems are formulated to find optimal schedules for the project with respect to different objective functions to be minimized, such as the project makespan, the maximum deviation from the due dates, the maximum flow-time and the maximum deviation of finish times. We represent these problems as optimization problems in terms of tropical mathematics, and then solve them by applying direct solution methods of tropical optimization. As a result, new direct solutions of the scheduling problems are obtained in a compact vector form, which is ready for further analysis and practical implementation. The solutions are illustrated by simple numerical examples.     

An augmented Lagrangian method for optimization problems with structured geometric constraints

This paper is devoted to the theoretical and numerical investigation of an augmented Lagrangian method for the solution of optimization problems with geometric constraints. Specifically, we study situations where parts of the constraints are nonconvex and possibly complicated, but allow for a fast computation of projections onto this nonconvex set. Typical problem classes which satisfy this requirement are optimization problems with disjunctive constraints (like complementarity or cardinality constraints) as well as optimization problems over sets of matrices which have to satisfy additional rank constraints. The key idea behind our method is to keep these complicated constraints explicitly in the constraints and to penalize only the remaining constraints by an augmented Lagrangian function. The resulting subproblems are then solved with the aid of a problem-tailored nonmonotone projected gradient method. The corresponding convergence theory allows for an inexact solution of these subproblems. Nevertheless, the overall algorithm computes so-called Mordukhovich-stationary points of the original problem under a mild asymptotic regularity condition, which is generally weaker than most of the respective available problem-tailored constraint qualifications. Extensive numerical experiments addressing complementarity- and cardinality-constrained optimization problems as well as a semidefinite reformulation of MAXCUT problems visualize the power of our approach.

     

三本高等数学教学方法的探索和实践

针对三类本科高等数学教学质量难以提高的困难,结合作者长期从事三本高数教学的经验,分析了三本高等数学教学的几个制约因素,探索了三本高等数学教学实践中可行的新方法,给出了相关实施建议.     

A Computational Study of the Homogeneous Algorithm for Large-scale Convex Optimization

Recently the authors have proposed a homogeneous and self-dual algorithm for solving the monotone complementarity problem (MCP) [5]. The algorithm is a single phase interior-point type method; nevertheless, it yields either an approximate optimal solution or detects a possible infeasibility of the problem. In this paper we specialize the algorithm to the solution of general smooth convex optimization problems, which also possess nonlinear inequality constraints and free variables. We discuss an implementation of the algorithm for large-scale sparse convex optimization. Moreover, we present computational results for solving quadratically constrained quadratic programming and geometric programming problems, where some of the problems contain more than 100,000 constraints and variables. The results indicate that the proposed algorithm is also practically efficient.     

An optimization-based approach to assess non-interference in labeled and bounded Petri net systems

An optimization-based approach to assess both strong non-deterministic non- interference (SNNI) and bisimulation SNNI (BSNNI) in discrete event systems modeled as labeled Petri nets is presented in this paper. The assessment of SNNI requires the solution of feasibility problems with integer variables and linear constraints, which is derived by extending a previous result given in the case of unlabeled net systems. Moreover, the BSNNI case can be addressed in two different ways. First, similarly to the case of SNNI, a condition to assess BSNNI, which is necessary and sufficient, can be derived from the one given in the unlabeled framework, requiring the solution of feasibility problems with integer variables and linear constraints. Then, a novel necessary and sufficient condition to assess BSNNI is given, which requires the solution of integer feasibility problems with nonlinear constraints. Furthermore, we show how to recast these problems into equivalent mixed-integer linear programming (MILP) ones. The effectiveness of the proposed approaches is shown by means of several examples. It turns out that there are relevant cases where the new condition to assess BSNNI that requires the solution of MILP problems is computationally more efficient, when compared to the one that requires the solution of feasibility problems.     

A library of local search heuristics for the vehicle routing problem

The vehicle routing problem (VRP) is a difficult and well-studied combinatorial optimization problem. Real-world instances of the VRP can contain hundreds and even thousands of customer locations and can involve many complicating constraints, necessitating the use of heuristic methods. We present a software library of local search heuristics that allows one to quickly generate solutions to VRP instances. The code has a logical, object-oriented design and uses efficient data structures to store and modify solutions. The core of the library is the implementation of seven local search operators that share a similar interface and are designed to be extended to handle additional options with minimal code change. The code is well-documented, straightforward to compile, and is freely available online. The code contains several applications that can be used to generate solutions to the capacitated VRP. Computational results indicate that these applications are able to generate solutions that are within about one percent of the best-known solution on benchmark problems.     

Second-order necessary and sufficient conditions in multiobjective programming ∗

In this paper we study second-order optimality conditions for the multi-objective programming problems with both inequality constraints and equality constraints. Two weak second-order constraint qualifications are introduced, and based on them we derive several second-order necessary conditions for a local weakly efficient solution. Two second-order sufficient conditions are also presented.     

Adjustable robust optimization with objective uncertainty

In this work, we study optimization problems where some cost parameters are not known at decision time and the decision flow is modeled as a two-stage process within a robust optimization setting. We address general problems in which all constraints (including those linking the first and the second stages) are defined by convex functions and involve mixed-integer variables, thus extending the existing literature to a much wider class of problems. We show how these problems can be reformulated using Fenchel duality, allowing to derive an enumerative exact algorithm, for which we prove asymptotic convergence in the general case, and finite convergence for cases where the first-stage variables are all integer.An implementation of the resulting algorithm, embedding a column generation scheme, is then computationally evaluated on a variant of the Capacitated Facility Location Problem with uncertain transportation costs, using instances that are derived from the existing literature. To the best of our knowledge, this is the first approach providing results on the practical solution of this class of problems.