A Discrete Lagrangian-Based Global-Search Method for Solving Satisfiability Problems

Satisfiability is a class of NP-complete problems that model a wide range of real-world applications. These problems are difficult to solve because they have many local minima in their search space, often trapping greedy search methods that utilize some form of descent. In this paper, we propose a new discrete Lagrange-multiplier-based global-search method (DLM) for solving satisfiability problems. We derive new approaches for applying Lagrangian methods in discrete space, we show that an equilibrium is reached when a feasible assignment to the original problem is found and present heuristic algorithms to look for equilibrium points. Our method and analysis provides a theoretical foundation and generalization of local search schemes that optimize the objective alone and penalty-based schemes that optimize the constraints alone. In contrast to local search methods that restart from a new starting point when a search reaches a local trap, the Lagrange multipliers in DLM provide a force to lead the search out of a local minimum and move it in the direction provided by the Lagrange multipliers. In contrast to penalty-based schemes that rely only on the weights of violated constraints to escape from local minima, DLM also uses the value of an objective function (in this case the number of violated constraints) to provide further guidance. The dynamic shift in emphasis between the objective and the constraints, depending on their relative values, is the key of Lagrangian methods. One of the major advantages of DLM is that it has very few algorithmic parameters to be tuned by users. Besides the search procedure can be made deterministic and the results reproducible. We demonstrate our method by applying it to solve an extensive set of benchmark problems archived in DIMACS of Rutgers University. DLM often performs better than the best existing methods and can achieve an order-of-magnitude speed-up for some problems.     

Algorithms for Unconstrained Optimization Problems via Control Theory

Existing algorithms for solving unconstrained optimization problems are generally only optimal in the short term. It is desirable to have algorithms which are long-term optimal. To achieve this, the problem of computing the minimum point of an unconstrained function is formulated as a sequence of optimal control problems. Some qualitative results are obtained from the optimal control analysis. These qualitative results are then used to construct a theoretical iterative method and a new continuous-time method for computing the minimum point of a nonlinear unconstrained function. New iterative algorithms which approximate the theoretical iterative method and the proposed continuous-time method are then established. For convergence analysis, it is useful to note that the numerical solution of an unconstrained optimization problem is none other than an inverse Lyapunov function problem. Convergence conditions for the proposed continuous-time method and iterative algorithms are established by using the Lyapunov function theorem.     

A stochastic optimal control approach to a class of production and inventory problems

A comprehensible and unified system control approach is presented to solve a class of production/inventory smoothing problems. A nonstationary, non-Gaussian, finite-time linear optimal solution with an attractive computation scheme is obtained for a general quadratic and linear cost structure. A complete solution to a classical production/inventory control problem is given as an example. A general solution to the discrete-time optimal regulator with arbitrary but known disturbance is provided and discussed in detail. A computationally attractive closed-loop suboptimal scheme is presented for problems with constraints or nonquadratic costs. Implementation and interpretation of the results are discussed.     

George B. Dantzig and systems optimization

We pay homage to George B. Dantzig by describing a less well-known part of his legacy–his early and dedicated championship of the importance of systems optimization in solving complex real-world problems.     

Global qualitative analysis of coupled three-level food chains

A coupled model for three-level food chain is considered, the coupling rule is discretized Laplacian diffusion type. The focus of this paper is on the global behavior of solutions. We will show that the differences of the same level population density approach zero as t→∞, provided that the coupling strength is sufficiently large.     

The application of automated reasoning to formal models of combinatorial optimization

Many formalisms have been proposed over the years to capture combinatorial optimization algorithms such as dynamic programming, branch and bound, and greedy. In 1989 Helman [9] presented a common formalism that captures dynamic programming and branch and bound type algorithms. The formalism was later extended to include greedy algorithms. In this paper, we describe the application of automated reasoning techniques to the domain of our model, in particular considering some representational issues and demonstrating that proofs about the model can be obtained by an automated reasoning program. The long-term objective of this research is to develop a methodology for using automated reasoning to establish new results within the theory, including the derivation of new lower bounds and the discovery (and verification) of new combinatorial search strategies.     

Conjugate Gradient Methods with Armijo-type Line Searches

Abstract Two Armijo-type line searches are proposed in this paper for nonlinear conjugate gradient methods.Under these line searches, global convergence results are established for several famous conjugate gradientmethods, including the Fletcher-Reeves method, the Polak-Ribiere-Polyak method, and the conjugate descentmethod.     

Market Power Issues in Bid-Based Hydrothermal Dispatch

The objective of this work is to investigate market power issues in bid-based hydrothermal scheduling. Initially, market power was simulated with a single stage Cournot–Nash equilibrium model. In this static model the equilibrium was calculated analytically. It was shown that the total production of N strategic agents is smaller than the least-cost solution by a factor of (N/(N+1)). Market power analysis for multiple stages was then carried through a stochastic dynamic programming scheme, where the decision in each stage and state is the Cournot–Nash equilibrium of a multi-agent game. Case studies with data taken from the Brazilian system are presented.     

一类拟线性退缩抛物型方程整体解的存在性与衰减估计

本文讨论了一类拟线性抛物型方程初边值问题整体解的存在性和衰减估计.所得结果改进并推广了文献[1]的相应结果.     

On the Finite-Time Dynamics of Ant Colony Optimization

An analytical framework for investigating the finite-time dynamics of ant colony optimization (ACO) under a fitness-proportional pheromone update rule on arbitrary construction graphs is developed. A limit theorem on the approximation of the stochastic ACO process by a deterministic process is demonstrated, and a system of ordinary differential equations governing the process dynamics is identified. As an example for the application of the presented theory, the behavior of ACO on three different construction graphs for subset selection problems is analyzed and compared for some basic test functions. The theory enables first rough theoretical predictions of the convergence speed of ACO. AMS 2000 Subject classification 68W20, 68W40