An exact solution method for unconstrained quadratic 0–1 programming: a geometric approach

We explore in this paper certain rich geometric properties hidden behind quadratic 0–1 programming. Especially, we derive new lower bounding methods and variable fixation techniques for quadratic 0–1 optimization problems by investigating geometric features of the ellipse contour of a (perturbed) convex quadratic function. These findings further lead to some new optimality conditions for quadratic 0–1 programming. Integrating these novel solution schemes into a proposed solution algorithm of a branch-and-bound type, we obtain promising preliminary computational results.     

W∞ gravity — A geometric approach

A brief review is given of an adaptation of the coadjoint orbit method appropriate for the study of models with infinite-dimensional symmetry groups. It is illustrated on several examples, including derivation of the WZNW action of induced D=2 (N,0) supergravity. As the main application, we present the geometric action on a generic coadjoint orbit of the deformed group of area-preserving diffeomorphisms. This action is precisely the anomalous effective WZNW action of D=2 matter fields coupled to a chiralW gravity background. Similar actions are given which produce the KP hierarchy as on-shell equations of motion.In Memoriam M. C. PolivanovDepartment of Physics, Ben-Gurion University of the Negev, Box 653, 84105 Beer Sheva, Israel. Published in Teoreticheskaya i Matematicheskaya Fizika, Vol. 93, No. 2, pp. 273–285, November, 1992.On leave from the Institute of Nuclear Research and Nuclear Energy, Boul. Trakia 72, BG-1784, Sofia, Bulgaria     

A geometric approach to Euler’s addition formula

Plane quartic curves given by equations of the form y ²=P(x) with polynomials P of degree 4 represent singular models of elliptic curves which are directly related to elliptic integrals in the form studied by Euler and for which he developed his famous addition formulas. For cubic curves, the well-known secant and tangent construction establishes an immediate connection of addition formulas for the corresponding elliptic integrals with the structure of an algebraic group. The situation for quartic curves is considerably more complicated due to the presence of the singularity. We present a geometric construction, similar in spirit to the secant method for cubic curves, which defines an addition law on a quartic elliptic curve given by rational functions. Furthermore, we show how this addition on the curve itself corresponds to the addition in the (generalized) Jacobian variety of the curve, and we show how any addition formula for elliptic integrals of the form \(\int (1/\sqrt{P(x)})\,\mathrm{d}x\) with a quartic polynomial P can be derived directly from this addition law.     

A quadratic programming approach to the Randić index

Let G(k, n) be the set of connected graphs without multiple edges or loops which have n vertices and the minimum degree of vertices is k. The Randi? index χ = χ(G) of a graph G   is defined by χ(G)=_∑(uv)(_δuδv)^-1/2$\chi (G)={\sum }_{(\mathit{uv})}({\delta }_u{\delta }_v{)}^{-1/2}$, where δ_u is the degree of vertex u and the summation extends over all edges (uv) of G. Caporossi et al. [G. Caporossi, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs IV: Chemical trees with extremal connectivity index, Computers and Chemistry 23 (1999) 469–477] proposed the use of linear programming as one of the tools for finding the extremal graphs. In this paper we introduce a new approach based on quadratic programming for finding the extremal graphs in G(k, n) for this index. We found the extremal graphs or gave good bounds for this index when the number n_k of vertices of degree k is between n − k and n. We also tried to find the graphs for which the Randi? index attained its minimum value with given k (k ? n/2) and n. We have solved this problem partially, that is, we have showed that the extremal graphs must have the number n_k of vertices of degree k less or equal n − k and the number of vertices of degree n − 1 less or equal k.     

Stochastic goal programming: A mean–variance approach

We propose a stochastic goal programming (GP) model leading to a structure of mean–variance minimisation. The solution to the stochastic problem is obtained from a linkage between the standard expected utility theory and a strictly linear, weighted GP model under uncertainty. The approach essentially consists in specifying the expected utility equation corresponding to every goal. Arrow's absolute risk aversion coefficients play their role in the calculation process. Once the model is defined and justified, an illustrative example is developed.     

The multiparametric 0–1-integer linear programming problem: A unified approach

We designed an algorithm for the multiparametric 0–1-integer linear programming (ILP) problem with the perturbation of the constraint matrix, the objective function and the right-hand side vector simultaneously considered. Our algorithm works by choosing an appropriate finite sequence of non-parametric mixed integer linear programming (MILP) problems in order to obtain a complete multiparametrical analysis. The algorithm may be implemented by using any software capable of solving MILP problems.     

Precise asymptotics – A general approach

The legendary 1947-paper by Hsu and Robbins, in which the authors introduced the concept of “complete convergence”, generated a series of papers culminating in the like-wise famous Baum–Katz 1965-theorem, which provided necessary and sufficient conditions for the convergence of the series $\sum_{n=1}^{\infty}n^{r/p-2}P (|S_{n}| \geqq \varepsilon n^{1/p})$ for suitable values of r and p, in which S _n denotes the n-th partial sum of an i.i.d. sequence. Heyde followed up the topic in his 1975-paper where he investigated the rate at which such sums tend to infinity as ε↘0 (for the case r=2 and p=1). The remaining cases have been taken care later under the heading “precise asymptotics”. An abundance of papers have since then appeared with various extensions and modifications of the i.i.d.-setting. The aim of the present paper is to show that the basis for the proof is essentially the same throughout, and to collect a number of examples. We close by mentioning that Klesov, in 1994, initiated work on rates in the sense that he determined the rate, as ε↘0, at which the discrepancy between such sums and their “Baum–Katz limit” converges to a nontrivial quantity for Heyde’s theorem. His result has recently been extended to the complete set of r- and p-values by the present authors.     

A new line search inexact restoration approach for nonlinear programming

A new general scheme for Inexact Restoration methods for Nonlinear Programming is introduced. After computing an inexactly restored point, the new iterate is determined in an approximate tangent affine subspace by means of a simple line search on a penalty function. This differs from previous methods, in which the tangent phase needs both a line search based on the objective function (or its Lagrangian) and a confirmation based on a penalty function or a filter decision scheme. Besides its simplicity the new scheme enjoys some nice theoretical properties. In particular, a key condition for the inexact restoration step could be weakened. To some extent this also enables the application of the new scheme to mathematical programs with complementarity constraints.     

A goal programming approach for farm planning with?resources dimensionality

Crop production entails many decision making processes aimed at improving productivity and achieving the best yield from scarce resources, which are normally limited. Assuming that there is a certain technical path of tasks to be carried out within a period, and that each task can be done in different ways, the problem addressed in this paper consists of choosing how and when to carry out each one, in such a way that the tasks are scheduled in sequence at the lowest possible cost, taking account of any relations of precedence among them, and in such a way that each task is done within its time window and with the resources being assigned in a feasible way. Time windows are usually defined in a strict way, and thus, if adjusted, can be a cause of infeasibility for some of the problems, implying the need to acquire new resources. Nevertheless, in most cases small deviations from time windows could be acceptable. In this paper a mixed 0-1 programming model to attain the proposed objective is proposed, applying goal programming to model time windows in a more flexible way.     

Multiobjective programming in optimization of interval objective functions — A generalized approach

We generalize known concepts (those introduced by Ishihuchi and Tanaka [1] and Rommerlfanger et al. [2]) of the solution of the linear programming problem with interval coefficients in the objective function based on preference relations between intervals. We unify all the discussed concepts as well as the corresponding solution methods into one general framework.     

A stable primal–dual approach for linear programming under nondegeneracy assumptions

This paper studies a primal–dual interior/exterior-point path-following approach for linear programming that is motivated on using an iterative solver rather than a direct solver for the search direction. We begin with the usual perturbed primal–dual optimality equations. Under nondegeneracy assumptions, this nonlinear system is well-posed, i.e. it has a nonsingular Jacobian at optimality and is not necessarily ill-conditioned as the iterates approach optimality. Assuming that a basis matrix (easily factorizable and well-conditioned) can be found, we apply a simple preprocessing step to eliminate both the primal and dual feasibility equations. This results in a single bilinear equation that maintains the well-posedness property. Sparsity is maintained. We then apply either a direct solution method or an iterative solver (within an inexact Newton framework) to solve this equation. Since the linearization is well posed, we use affine scaling and do not maintain nonnegativity once we are close enough to the optimum, i.e. we apply a change to a pure Newton step technique. In addition, we correctly identify some of the primal and dual variables that converge to 0 and delete them (purify step). We test our method with random nondegenerate problems and problems from the Netlib set, and we compare it with the standard Normal Equations NEQ approach. We use a heuristic to find the basis matrix. We show that our method is efficient for large, well-conditioned problems. It is slower than NEQ on ill-conditioned problems, but it yields higher accuracy solutions.     

A DC programming approach for solving the symmetric Eigenvalue Complementarity Problem

In this paper, we investigate a DC (Difference of Convex functions) programming technique for solving large scale Eigenvalue Complementarity Problems (EiCP) with real symmetric matrices. Three equivalent formulations of EiCP are considered. We first reformulate them as DC programs and then use DCA (DC Algorithm) for their solution. Computational results show the robustness, efficiency, and high speed of the proposed algorithms.     

A hybrid constraint programming approach to?the?log-truck scheduling problem

Scheduling problems in the forest industry have received significant attention in the recent years and have contributed many challenging applications for optimization technologies. This paper proposes a solution method based on constraint programming and mathematical programming for a log-truck scheduling problem. The problem consists of scheduling the transportation of logs between forest areas and woodmills, as well as routing the fleet of vehicles to satisfy these transportation requests. The objective is to minimize the total cost of the non-productive activities such as the waiting time of trucks and forest log-loaders and the empty driven distance of vehicles. We propose a constraint programming model to address the combined scheduling and routing problem and an integer programming model to deal with the optimization of deadheads. Both of these models are combined through the exchange of global constraints. Finally the whole approach is validated on real industrial data.     

A computational approach to Lüroth quartics

A plane quartic curve is called Lüroth if it contains the ten vertices of a complete pentalateral. White and Miller constructed in 1909 a covariant quartic fourfold, associated to any plane quartic. We review their construction and we show how it gives a computational tool to detect if a plane quartic is Lüroth. As a byproduct, we show that the 28 bitangents of a general plane quartic correspond to 28 singular points of the associated White–Miller quartic fourfold.     

A linear programming algorithm for curve fitting in the L∞ norm

The L_∞ norm has been widely studied as a criterion for curve fitting problems. This paper presents an algorithm to solve discrete approximation problems in the L_∞ norm. The algorithm is a special-purpose linear programming method using the dual form of the problem, which employs a reduced basis and multiple pivots. Results of the computational experience with a computer code version of the algorithm are presented.     

Investments in EOP-technologies and emissions trading – Results from a linear programming approach and sensitivity analysis

This paper offers a general approach to valuating investments in end-of-pipe-technologies (EOP-technologies) with special regard to an emissions trading scheme. Since investments of this kind affect production, it is necessary to derive the required payments for a financial valuation and the constraints from production theory and production planning. On this basis, it is possible to develop a valuation model. This model considers joint production, activity-level-dependent and -independent payments and specifically includes the indivisibility of the investment. Applying duality theory enables us to examine the determinants of the price ceiling for such an investment. Sensitivity analysis shows that tradable permits have several effects on an investment and do not always encourage environmentally beneficial investments – in particular cases they may even be counterproductive.     

A reduction method for semi-infinite programming by means of a global stochastic approach†

We describe a reduction algorithm for solving semi-infinite programming problems. The proposed algorithm uses the simulated annealing method equipped with a function stretching as a multi-local procedure, and a penalty technique for the finite optimization process. An exponential penalty merit function is reduced along each search direction to ensure convergence from any starting point. Our preliminary numerical results seem to show that the algorithm is very promising in practice.