Roof duality,complementation and persistency in quadratic 0–1 optimization

The paper is concerned with the ‘primal’ problem of maximizing a given quadratic pseudo-boolean function. Four equivalent problems are discussed—the primal, the ‘complementation’, the ‘discrete Rhys LP’ and the ‘weighted stability problem of a SAM graph’. Each of them has a relaxation—the ‘roof dual’, the ‘quadratic complementation,’ the ‘continuous Rhys LP’ and the ‘fractional weighted stability problem of a SAM graph’. The main result is that the four gaps associated with the four relaxations are equal. Furthermore, a solution to any of these problems leads at once to solutions of the other three equivalent ones. The four relaxations can be solved in polynomial time by transforming them to a bipartite maximum flow problem. The optimal solutions of the ‘roof-dual’ define ‘best’ linear majorantsp(x) off, having the following persistency property: if theith coefficient inp is positive (negative) thenx _i=1 (0) in every optimum of the primal problem. Several characterizations are given for the case where these persistency results cannot be used to fix any variable of the primal. On the other hand, a class of gap-free functions (properly including the supermodular ones) is exhibited.     

A duality theorem for semi-infinite convex programs and their finite subprograms

In this paper, we first establish a general recession condition under which a semi-infinite convex program and its formal lagrangian dual have the same value. We go on to show that, under this condition, the following hold. First, every finite subprogram, with ‘enough’ of the given constraints, has the same value as its Lagrangian dual. Second, the weak value of the primal program is equal to the optimal value of the primal. The first draft of this work, entitled ‘Asymptotic Convex Programming’ was completed while the author was a member of the Department of Mathematical Sciences at the University of Delaware, Newark, DE 19711.     

Constructing greedy linear extensions by interchanging chains

A natural way to prove that a particular linear extension of an ordered set is ‘optimal’ with respect to the ‘jump number’ is to transform this linear extension ‘canonically’ into one that is ‘optimal’. We treat a ‘greedy chain interchange’ transformation which has applications to ordered sets for which each ‘greedy’ linear extension is ‘optimal’.     

Primal cutting plane algorithms revisited

Dual fractional cutting plane algorithms, in which cutting planes are used to iteratively tighten a linear relaxation of an integer program, are well-known and form the basis of the highly successful branch-and-cut method. It is rather less well-known that various primal cutting plane algorithms were developed in the 1960s, for example by Young. In a primal algorithm, the main role of the cutting planes is to enable a feasible solution to the original problem to be improved. Research on these algorithms has been almost non-existent.  In this paper we argue for a re-examination of these primal methods. We describe a new primal algorithm for pure 0-1 problems based on strong valid inequalities and give some encouraging computational results. Possible extensions to the case of general mixed-integer programs are also discussed.     

An algorithm for automatically selecting a suitable verification method for linear systems

Several methods have been proposed to calculate a rigorous error bound of an approximate solution of a linear system by floating-point arithmetic. These methods are called ‘verification methods’. Applicable range of these methods are different. It depends mainly on the condition number and the dimension of the coefficient matrix whether such methods succeed to work or not. In general, however, the condition number is not known in advance. If the dimension or the condition number is large to some extent, then Oishi–Rump’s method, which is known as the fastest verification method for this purpose, may fail. There are more robust verification methods whose computational cost is larger than the Oishi–Rump’s one. It is not so efficient to apply such robust methods to well-conditioned problems. The aim of this paper is to choose a suitable verification method whose computational cost is minimum to succeed. First in this paper, four fast verification methods for linear systems are briefly reviewed. Next, a compromise method between Oishi–Rump’s and Ogita–Oishi’s one is developed. Then, an algorithm which automatically and efficiently chooses an appropriate verification method from five verification methods is proposed. The proposed algorithm does as much work as necessary to calculate error bounds of approximate solutions of linear systems. Finally, numerical results are presented.     

Interacting with local and remote data repositories using the stashR package

The stashR package (a Set of Tools for Administering Shared Repositories) for R implements a basic versioned key-value style database where character string keys are associated with data values. Using the S4 classes ‘localDB’ and ‘remoteDB’, and associated methods, versioned key-value databases can be either created locally on the user’s computer or accessed remotely via the Internet. The stashR package can enhance reproducible research by providing a ‘localDB’ database format for the caching of computations which can subsequently be stored on the Internet. To reproduce a particular computation, a reader can access the ‘remoteDB’ database and obtain the associated R objects. This work was supported in part by the Johns Hopkins Training Program in the Epidemiology and Biostatistics of Aging (NIA T32 AG00247) and the Faculty Innovation Fund, Johns Hopkins Bloomberg School of Public Health.     

Experiments with an interactive paired comparison simplex method for molp problems

In this paper, an interactive paired comparison simplex based method formultiple objective linear programming (MOLP) problems is developed and compared to other interactive MOLP methods. The decision maker (DM)’s utility function is assumed to be unknown, but is an additive function of his known linearized objective functions. A test for ‘utility efficiency’ for MOLP problems is developed to reduce the number of efficient extreme points generated and the number of questions posed to the DM. The notion of ‘strength of preference ’ is developed for the assessment of the DM’s unknown utility function where he can express his preference for a pair of extreme points as ‘strong ’, ‘weak ’, or ‘almost indifferent ’. The problem of ‘inconsistency of the DM’ is formalized and its resolution is discussed. An example of the method and detailed computational results comparing it with other interactive MOLP methods are presented. Several performance measures for comparative evaluations of interactive multiple objective programming methods are also discussed. All rights reserved. This study, or parts thereof, may not be reproduced in any form without written permission of the authors.     

Effect of regulation on efficiency: evidence from Indian cement industry

The main objective of the paper is to analyze the impact of environmental regulation on technical efficiencies of Indian cement producing firms. It derives the technical efficiency (TE) scores of firms in the presence and absence of regulation and brings out the differences in their magnitudes in two scenarios: one in which the firms take initiatives to comply with the set standards by investing additional resources for pollution abatement and the other in which the firms do not take the necessary initiatives. The paper uses establishment level data from Annual Survey of Industries on cement for two years, the most recent data published for 2003–2004 and a previous year for 1999–2000 when the environmental regulations in India were in the initial phases of implementation. A non-parametric deterministic method of data envelopment analysis (DEA) is used to derive the TE scores of firms. The traditional DEA framework is modified by introducing weak disposability of bad outputs to characterize ‘effective environmental regulation’, which ensures that reducing pollution is not costless. For both years it has been found that the TE scores of firms under ‘effective regulation’ scenario are either higher than or equal to those derived under ‘ineffective regulation’ scenario resulting in a higher average TE at the industry level in the ‘effective regulation’ scenario.     

A changing trajectory of proof learning in the geometry inquiry classroom

The purpose of this study is to explore how students changes through learning to construct mathematical proofs in an inquiry-based middle school geometry class in Korea. Although proof has long been considered as one of the most important aspects of mathematics education, it is well-known that it is one of the most difficult areas of school mathematics for students. The geometry inquiry classroom (GIC) is an experimental class designed to teach geometry, especially focusing on teaching proof, based on students’ own inquiry. Based on a 2-year participant observation in the GIC, this study was conducted to address the following research question: how has students’ practice of mathematical proof been changed through their participation in the GIC? The in-depth analysis of the classroom discourse identified three stages through which the students’ practice of mathematical proof was transformed in the GIC: ‘emergent understanding of proof’, ‘proof learning as a goal-oriented activity’, ‘experiencing proof as the practice of mathematics’. The study found that as learning evolved through these stages, so the mathematics teacher’s role shifted from being an instructor to a mediator of communication. Most importantly, this research showed that the GIC has created a learning environment where students develop their competence in constructing meaningful mathematical proof and grow to be ‘a human who proves’, ultimately ‘a person who playfully engages with mathematics’.     

Analysis and design of selection committees: a game theoretic secretary problem

Firms often delegate important decisions to committees which are set up specifically for that purpose; for example selection committees. We analyze the equilibrium behavior of a game in which committee members (the players) interview candidates sequentially, either hiring or going on to the next one. The players have differing evaluations of candidates (e.g. one cares about typing skills; the other about IT skills), which become their utilities if the candidate is hired. We then consider the optimal design (rules of the game) of such a committee, from the point of view of the firm. That is, which rules hire candidates which maximize the firm’s utility. Our committee game has a first round in which the members sequentially, by order of player number, say ‘yea’ or ‘nea’ to the candidate. If there are sufficient ‘yeas’ then she is tentatively hired; otherwise she is rejected. In the former case, members who said nea can veto the candidate in the second round. Thus the candidate is either hired, rejected, or vetoed. In the last case, the member casting a veto has one less to use on later candidates. We analyze equilibria where a player may say ‘yea’ to a candidate he would prefer not to hire, in order to force the other player to use up a valuable veto. We show that for the uniform candidate distribution there is a unique equilibrium and better candidates for the firm are hired when there are more vetoes. However we exhibit a candidate distribution where increasing the numbers of vetoes results in hiring worse candidates.