Scalarization Method in Multicriteria Games

Using a two-criteria two-person game as an example, the validity of the scalarization method applied for the parameterization of the set of game values and for estimating the players’ payoffs is investigated. It is shown that the use of linear scalarization by the players gives the results different from those obtained using Germeyer’s scalarization. Various formalizations of the concept of value of MC games are discussed.     

Reduction of indefinite quadratic programs to bilinear programs

Indefinite quadratic programs with quadratic constraints can be reduced to bilinear programs with bilinear constraints by duplication of variables. Such reductions are studied in which: (i) the number of additional variables is minimum or (ii) the number of complicating variables, i.e., variables to be fixed in order to obtain a linear program, in the resulting bilinear program is minimum. These two problems are shown to be equivalent to a maximum bipartite subgraph and a maximum stable set problem respectively in a graph associated with the quadratic program. Non-polynomial but practically efficient algorithms for both reductions are thus obtaine.d Reduction of more general global optimization problems than quadratic programs to bilinear programs is also briefly discussed.     

Subalternation and existence presuppositions in an unconventionally formalized canonical square of opposition

An unconventional formalization of the canonical (Aristotelian-Boethian) square of opposition in the notation of classical symbolic logic secures all but one of the canonical square’s grid of logical interrelations between four A-E-I-O categorical sentence types. The canonical square is first formalized in the functional calculus in Frege’s Begriffsschrift, from which it can be directly transcribed into the syntax of contemporary symbolic logic. Difficulties in received formalizations of the canonical square motivate translating I categoricals, ‘Some S is P’, into symbolic logical notation, not conjunctively as \({\exists x[Sx\wedge Px]}\), but unconventionally instead in an ontically neutral conditional logical symbolization, as \({\exists x[Sx\rightarrow Px]}\). The virtues and drawbacks of the proposal are compared at length on twelve grounds with the explicit existence expansion of A and E categoricals as the default strategy for symbolizing the canonical square preserving all original logical interrelations.     

On statistical sensitivity analysis in stochastic programming

Different approaches to statistical sensitivity analysis for optimal solutions of stochastic programs are discussed and compared. Possibilities of drawing conclusions about asymptotic behavior of estimated optimal solutions by means of stability properties of auxiliary randomly perturbed convex quadratic programs are indicated and illustrated on a numerical example.     

Towards global bilevel dynamic optimization

The global solution of bilevel dynamic optimization problems is discussed. An overview of a deterministic algorithm for bilevel programs with nonconvex functions participating is given, followed by a summary of deterministic algorithms for the global solution of optimization problems with nonlinear ordinary differential equations embedded. Improved formulations for scenario-integrated optimization are proposed as bilevel dynamic optimization problems. Solution procedures for some of the problems are given, while for others open challenges are discussed. Illustrative examples are given.     

A note on reduction of quadratic and bilinear programs with equality constraints

Reduction of some classes of global optimization programs to bilinear programs may be done in various ways, and the choice of method clearly influences the ease of solution of the resulting problem. In this note we show how linear equality constraints may be used together with graph theoretic tools to reduce a bilinear program, i.e., eliminate variables from quadratic terms to minimize the number of complicating variables. The method is illustrated on an example. Computer results are reported on known test problems.     

Distributionally robust mixed integer linear programs: Persistency models with applications

In this paper, we review recent advances in the distributional analysis of mixed integer linear programs with random objective coefficients. Suppose that the probability distribution of the objective coefficients is incompletely specified and characterized through partial moment information. Conic programming methods have been recently used to find distributionally robust bounds for the expected optimal value of mixed integer linear programs over the set of all distributions with the given moment information. These methods also provide additional information on the probability that a binary variable attains a value of 1 in the optimal solution for 0–1 integer linear programs. This probability is defined as the persistency of a binary variable. In this paper, we provide an overview of the complexity results for these models, conic programming formulations that are readily implementable with standard solvers and important applications of persistency models. The main message that we hope to convey through this review is that tools of conic programming provide important insights in the probabilistic analysis of discrete optimization problems. These tools lead to distributionally robust bounds with applications in activity networks, vertex packing, discrete choice models, random walks and sequencing problems, and newsvendor problems.     

Theoretical game analysis of position auctions according to the Vickrey–Clarke–Groves mechanism with two-stage ranking

Different types of position auctions are considered. A position auction is a mechanism for the allocation of advertising space in search engine results to a user-defined query. Advertisers make bids they are willing to pay the search engine for a click to their website. The search engine determines whose advertisements will get to the page and in what position, based on the bids of all the advertisers. Different types of such auctions are discussed using the example of the Yandex search engine based on the Vickrey–Clarke–Grovesmechanism. The main result is a formalization of the concept of an auction with two-stage ranking and its balance test.     

An essential tension in mathematics education

There is a problem that goes through the history of calculus: the tension between the intuitive and the formal. Calculus continues to be taught as if it were natural to introduce the study of change and accumulation by means of the formalized ideas and concepts known as the mathematics of ε and δ. It is frequently considered as a failure that “students still seem to conceptualize limits via the imagination of motion.” These kinds of assertions show the tension, the rift created by traditional education between students’ intuitions and a misdirected formalization. In fact, I believe that the internal connections of the intuition of change and accumulation are not correctly translated into that arithmetical approach of ε and δ. There are other routes to formalization which cohere with these intuitions, and those are the ones discussed in this paper. My departing point is epistemic and once this discussion is put forward, I produce a narrative of classroom work, giving a special place to local conceptual organizations.     

A Hierarchy of Relaxations Leading to the Convex Hull Representation for General Discrete Optimization Problems

We consider linear mixed-integer programs where a subset of the variables are restricted to take on a finite number of general discrete values. For this class of problems, we develop a reformulation-linearization technique (RLT) to generate a hierarchy of linear programming relaxations that spans the spectrum from the continuous relaxation to the convex hull representation. This process involves a reformulation phase in which suitable products using a defined set of Lagrange interpolating polynomials (LIPs) are constructed, accompanied by the application of an identity that generalizes x(1−x) for the special case of a binary variable x. This is followed by a linearization phase that is based on variable substitutions. The constructs and arguments are distinct from those for the mixed 0-1 RLT, yet they encompass these earlier results. We illustrate the approach through some examples, emphasizing the polyhedral structure afforded by the linearized LIPs. We also consider polynomial mixed-integer programs, exploitation of structure, and conditional-logic enhancements, and provide insight into relationships with a special-structure RLT implementation.     

On a class of quadratic programs

This paper considers a class of quadratic programs where the constraints ae linear and the objective is a product of two linear functions. Assuming the two linear factors to be non-negative, maximization and minimization cases are considered. Each case is analyzed with the help of a bicriteria linear program obtained by replacing the quadratic objective with the two linear functions. Global minimum (maximum) is attained at an efficient extreme point (efficient point) of the feasible set in the solution space and corresponds to an efficient extreme point (efficient point) of the feasible set in the bicriteria space. Utilizing this fact and certain other properties, two finite algorithms, including validations are given for solving the respective problems. Each of these, essentially, consists of solving a sequence of linear programs. Finally, a method is provided for relaxing the non-negativity assumption on the two linear factors of the objective function.     

AFRA: Argumentation framework with recursive attacks

The issue of representing attacks to attacks in argumentation is receiving an increasing attention as a useful conceptual modelling tool in several contexts. In this paper we present AFRA, a formalism encompassing unlimited recursive attacks within argumentation frameworks. AFRA satisfies the basic requirements of definition simplicity and rigorous compatibility with Dung’s theory of argumentation. This paper provides a complete development of the AFRA formalism complemented by illustrative examples and a detailed comparison with other recursive attack formalizations.     

Improved program planning with formal models? The case of high risk crop farming in Northeast Germany

In this paper we explore whether the incorporation of systematic time series analyses and mathematical optimization procedures in the practical planning process has the potential to improve production program decisions. The cases of four German cash crop farms are investigated over six planning periods. In order to avoid solutions that simply exceed the farmer’s risk tolerance, the apparently accepted variance of the observed program’s total gross margin is used as an upper bound in the optimization. For each of the 24 planning occasions, the formal model is used to generate optimized alternative programs. The total gross margins that could have been realized if the formally optimized programs had been implemented are then compared to those that were actually realized. We find that the farmers could have increased their total gross margins significantly if—instead of using simple routines and rules of thumb—they had used adequate methods of statistical analysis combined with the formal optimization model. Norbert Hirschauer thanks the German Research Foundation (DFG) for the opportunity to work on this paper during a research leave.     

Global solution of bilevel programs with a nonconvex inner program

A bounding algorithm for the global solution of nonlinear bilevel programs involving nonconvex functions in both the inner and outer programs is presented. The algorithm is rigorous and terminates finitely to a point that satisfies ε-optimality in the inner and outer programs. For the lower bounding problem, a relaxed program, containing the constraints of the inner and outer programs augmented by a parametric upper bound to the parametric optimal solution function of the inner program, is solved to global optimality. The optional upper bounding problem is based on probing the solution obtained by the lower bounding procedure. For the case that the inner program satisfies a constraint qualification, an algorithmic heuristic for tighter lower bounds is presented based on the KKT necessary conditions of the inner program. The algorithm is extended to include branching, which is not required for convergence but has potential advantages. Two branching heuristics are described and analyzed. Convergence proofs are provided and numerical results for original test problems and for literature examples are presented.     

运筹学中若干离散规划问题的相对差分搜索解法

运筹学中有很多离散规划问题。其中的线性规划通常用分枝定界法或割平面法，还有图上作业法求解。不论哪种方法工作量都不小，而且效率低；至于非线性规划大都是用动态规划法求解，也很麻烦、耗时。对于大规模问题，不论线性或非线性离散规划，现有解法都受到问题规模的限制；还有资源分配和背包问题至今没有见到解决方法。本文就是为了解决这些问题，提出了相对差分搜索算法。通过5个算例和其它文献中的一些算例计算验证了本法简单、快速、有效和精确，尤其不受问题规模的限制是其最大的优点。     

Multiprogrammering — en orientering

The need for effective utilization of computer facilities has resulted in a great interest in parallel processing of several independent programs on a computer.The introductory parts of this paper deal with multiprogramming both for batch and real-time computer systems. Also some important hardware features such as automatic program interrupts, memory lock-outs and autonomous facilities are discussed.In the following chapter elementary program-mechanics are introduced and attention is paid to priority assignment to different programs.Some main functions of a Master Control Program are then discussed and finally some aspects are given on multiprogram scheduling of computer runs.Multiprogramming is still in an early stage of its development and therefore this paper makes no claim to completeness—it rather attempts to render some important principles of these new techniques.     

Comparative evaluation of performance of national R&D programs with heterogeneous objectives: A DEA approach

The strategic importance of performance evaluation of national R&D programs is highlighted as the resource allocation draws more attention in R&D policy agenda. Due to the heterogeneity of national R&D programs’ objectives, however, it is intractably difficult to relatively evaluate multiple programs and, consequently, few studies have been conducted on the performance comparison of the R&D programs. This study measures and compares the performance of national R&D programs using data envelopment analysis (DEA). Since DEA allows each DMU to choose the optimal weights of inputs and outputs which maximize its efficiency, it can mirror R&D programs’ unique characteristics by assigning relatively high weights to the variables in which each program has strength. Every project in every R&D program is evaluated together based on the DEA model for comparison of efficiency among different systems. Kruskal–Wallis test with a post hoc Mann–Whitney U test is then run to compare performance of R&D programs. Two alternative approaches to incorporating the importance of variables, the AR model and output integration, are also introduced. The results are expected to provide policy implications for effectively formulating and implementing national R&D programs.     

Decomposition of linear programs using parallel computation

This paper describes DECOMPAR: an implementation of the Dantzig-Wolfe decomposition algorithm for block-angular linear programs using parallel processing of the subproblems. The software is based on a robust experimental code for LP decomposition and runs on the CRYSTAL multicomputer at the University of Wisconsin-Madison. Initial computational experience is reported. Promising directions in future development of this approach are discussed.Research supported in part by the Office of Naval Research under grant N00014-87-K-0163.     

Tightening concise linear reformulations of 0-1 cubic programs

A common strategy for solving 0-1 cubic programs is to reformulate the non-linear problem into an equivalent linear representation, which can then be submitted directly to a standard mixed-integer programming solver. Both the size and the strength of the continuous relaxation of the reformulation determine the success of this method. One of the most compact linear representations of 0-1 cubic programs is based on a repeated application of the linearization technique for 0-1 quadratic programs introduced by Glover. In this paper, we develop a pre-processing step that serves to strengthen the linear programming bound provided by this concise linear form of a 0-1 cubic program. The proposed scheme involves using optimal dual multipliers of a partial level-2 RLT formulation to rewrite the objective function of the cubic program before applying the linearization. We perform extensive computational tests on the 0-1 cubic multidimensional knapsack problem to show the advantage of our approach.     

Simulation Modelling Using an Interactive Simulation Program Generator

The development of an interactive simulation program generator which is available on micro and mainframe computers is outlined. The generator forms part of a simulation environment being researched into and constructed by a group of researchers at the London School of Economics. The generated programs are written in Pascal, using a suite of routines which assume a three-phase structure for simulation programs. Experiences of modelling using such a simulation modelling environment are outlined, as well as details of related research and future research plans.