A brief history of balance through time

We present methods for establishing the amount of reciprocity, transitivity and group balance (a generalization of structural balance) in sociometric structures. These methods are applied to the second time series of sociometric data provided by the Newcomb (1961) study. The amount of reciprocity was above chance levels at the outset and showed no systematic variation thereafter. Transitivity has a very different time scale. It climbed steadily through the first nine weeks and remained stable thereafter. While consistent with chance at the beginning of the study period, it grew to above chance levels at week 3. Group imbalance declined throughout the entire period. The reasons for these different time scales are discussed.     

The EvCA project: A brief history

This article presents a brief history of the Evolving Cellular Automata (EvCA) project. In the EvCA project, a genetic algorithm was used to evolve cellular automata to perform certain (nontrivial) computational tasks, in an effort to gain more insight into the question: “How does evolution produce sophisticated emergent computation in systems composed of simple components limited to local interactions?” Next to providing many interesting results and useful insights, the EvCA project seems to have spawned a whole research area of its own. Here, a brief overview is given of how it all started, developed, and inspired further work. © 2013 Wiley Periodicals, Inc. Complexity 18: 15–19, 2013     

On optimizing over lift-and-project closures

The strengthened lift-and-project closure of a mixed integer linear program is the polyhedron obtained by intersecting all strengthened lift-and-project cuts obtained from its initial formulation, or equivalently all mixed integer Gomory cuts read from all tableaux corresponding to feasible and infeasible bases of the LP relaxation. In this paper, we present an algorithm for approximately optimizing over the strengthened lift-and-project closure. The originality of our method is that it relies on a cut generation linear programming problem which is obtained from the original LP relaxation by only modifying the bounds on the variables and constraints. This separation LP can also be seen as dual to the cut generation LP used in disjunctive programming procedures with a particular normalization. We study properties of this separation LP, and discuss how to use it to approximately optimize over the strengthened lift-and-project closure. Finally, we present computational experiments and comparisons with recent related works.     

A brief history of the International Symposia on Mathematical Programming

This article briefly recounts the history of the International Symposia on Mathematical Programming from the 0th in 1949 to the 19th in 2006. Included in the summary are the dates, locations, organizers, sponsors, award winners, and special characteristics of each Symposium.     

An L-shaped method with strengthened lift-and-project cuts

Computational Management Science - Lift-and-project (L &P) cuts are well-known general 0–1 programming cuts which are typically deployed in branch-and-cut methods to solve MILP...     

A lift-and-project cutting plane algorithm for mixed 0–1 programs

We propose a cutting plane algorithm for mixed 0–1 programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through the solution of a linear program that has about twice the size of the usual LP relaxation. A lifting step is used to reduce the size of the LP's needed to generate the cuts. An additional strengthening step suggested by Balas and Jeroslow is then applied. We report our computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cone relaxations of Lovász and Schrijver and the hierarchy of relaxations of Sherali and Adams.The research underlying this report was supported by National Science Foundation Grant #DDM-8901495 and Office of Naval Research Contract N00014-85-K-0198.     

A brief chronological and bibliographic guide to the history of Chinese mathematics

The history of Chinese mathematics remains largely unknown in the West. This situation is the result of several factors: geographic, political, and linguistic. Few Western scholars possess the necessary facility in the Classical Chinese language to seek information about Chinese mathematics from primary sources. Yet despite the deficiency, there does exist a rich, albeit dispersed, literature on the history of Chinese mathematics in Western languages. The purpose of this contribution in to call the reader's attention to this literature and to the history of Chinese mathematics in general.     

A brief history of mathematics education in Turkey: K-12 mathematics curricula

In this study, we survey the history of mathematics education in Turkey starting with its historical roots in the foundation of the republic. The changes in mathematics education in Turkey over the last century are investigated through an analysis of changes in curricular documents for K-12 schools. We consider the factors and reasons affecting curriculum developments, changes in philosophy and structure in terms of standards, objective and instructions. This article utilizes archival research techniques by examining original sources and illustrates the nature of the changes benefiting from a historical perspective. As a result of such analysis of the aforesaid sources, we have seen that the main reasons for changing mathematics curricula are: to build up a modern civilization in Turkey; the reports of John Dewey and the recommendations of Kate Wofford, William C. Varaceus and Watson Dickerman; the desire to become a member of the European Union; international factors and political situations.     

On the commutativity of antiblocker diagrams under lift-and-project operators

The behavior of the disjunctive operator, defined by Balas, Ceria and Cornuéjols, in the context of the “antiblocker duality diagram” associated with the stable set polytope, QSTAB(G), of a graph and its complement, was first studied by Aguilera, Escalante and Nasini. The authors prove the commutativity of this diagram in any number of iterations of the disjunctive operator. One of the main consequences of this result is a generalization of the Perfect Graph Theorem under the disjunctive rank.In the same context, Lipták and Tunçel study the lift-and-project operators N₀, N and N₊ defined by Lovász and Schrijver. They find a graph for which the diagram does not commute in one iteration of the N₀- and N-operator. In connection with N₊, the authors implicitly suggest a similar result proving that if the diagram commutes in k=O(1) iterations, P=NP.In this paper, we give for any number of iterations, explicit proofs of the non commutativity of the N₀-, N- and N₊-diagram.In the particular case of the N₀- and N-operator, we find bounds for the ranks of the complements of line graphs (of complete graphs), which allow us to prove that the diagrams do not commute for these graphs.     

A brief history of partitions of numbers,partition functions and their modern applications

‘Number rules the universe.’

The Pythagoras     

Exact MAX-2SAT solution via lift-and-project closure

We present a new approach for exact solution of MAX-2SAT problems based on a strong reformulation deduced from an optimal continuous solution over the elementary closure of lift-and-project cuts. Computational results show that this formulation leads to a reduced number of nodes in the branch-and-bound tree and short computing times.     

Strong lift-and-project cutting planes for the stable set problem

A great deal of research has been focusing, since the early seventies, on finding strong relaxations for the stable set problem. Polyhedral combinatorics techniques have been at first developed to strengthen the natural linear formulation. Afterward, strong semidefinite programming relaxations have been deeply investigated. Nevertheless, the resulting integer programming (IP) algorithms cannot be regarded as being quite successful in practice, as most of the relaxations give rise to one out of two extreme situations: either provide weak bounds at low computational cost or give good bounds (sometimes excellent) but too demanding to compute. In this paper we present a method to bridge such a gap. In particular, a new lift-and-project relaxation is obtained by a problem-specific variant of the lifting operator M(K, K) by Lovász and Schrijver, combined with Benders decomposition. This yields strong cutting planes, generated by solving a cut generating linear program. An extensive computational experience shows that embedding these cuts in a branch-and-cut framework significantly reduces the size of the enumeration trees as well as the CPU times with respect to state-of-the-art IP algorithms.     

Complex geometry: Its brief history and its future

This paper reviews the brief history of complex geometry and looks into its future.     

Complex geometry: Its brief history and its future

This paper reviews the brief history of complex geometry and looks into its future.     

On the facets of the lift-and-project relaxations of graph subdivisions

We study the behavior of lift-and-project procedures for solving combinatorial optimization problems as described by Lovász and Schrijver (1991), in the context of the stable set problem on graphs. Following the work of Wolsey (1976), we investigate how to generate facets of the relaxations obtained by these procedures from facets of the relaxations of the original graph, after applying fundamental graph operations. We show our findings for the odd subdivision of an edge and its generalization, the stretching of a vertex operation.     

The stable set problem and the lift-and-project ranks of graphs

We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lovász and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures' performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations (as well as their common generalization, the stretching of a vertex operation) cannot decrease the N₀-, N-, or N₊-rank of the graph. We also provide graph classes (which contain the complete graphs) where these operations do not increase the N₀- or the N-rank. Hence we obtain the ranks for these graphs, and we also present some graph-minor like characterizations for them. Despite these properties we give examples showing that in general most of these operations can increase these ranks. Finally, we provide improved bounds for N₊-ranks of graphs in terms of the number of nodes in the graph and prove that the subdivision of an edge or cloning a vertex can increase the N₊-rank of a graph.Research of these authors was supported in part by a PREA from Ontario, Canada and research grants from NSERC.Mathematics Subject Classification (2000): 0C10, 90C22, 90C27, 47D20