<p>Many problems in business, industry, and academia can be modelled as constraint programs consisting of matrices of decision variables. Such “matrix models” often have symmetry. In particular, they often have row and column symmetry as the rows and columns can freely be permuted without affecting the satisfiability of assignments. Existing methods have difficulty in dealing with the super-exponential number of symmetries in a problem with row and column symmetry. We therefore propose some ordering constraints which can effectively break such symmetries. To use these constraints in practice, we develop some efficient linear time propagators. We demonstrate the effectiveness of these symmetry breaking ordering constraints on a wide range of problems. We also show how such ordering constraints can be used to deal with partial symmetries, as well as value symmetries.</p>

<p>Essay 1: Hurst and Lusardi (2004) use higher-order polynomials in wealth in estimating the relationship with entrepreneurship. They find evidence conflicting with the existence of extensive liquidity constraints in the United States. In this paper, their approach is replicated on Swedish data. A positive relationship between wealth and entrepreneurship is found, which supports the liquidity constraints hypothesis. Alternative methods attempting to handle the endogeneity problem and distinguish between absolute decreasing risk aversion and liquidity constraints give further support to the hypothesis. The paper suggests that there exist liquidity constraints in Sweden, which are possibly more extensive than in the United States.</p><p>Essay 2: Displacement is expected to decrease the reservation wage of self-employment by decreasing earnings in paid employment and increasing the probability of unemployment. This paper examines whether displacement increases the probability of self-employment using propensity score matching on Swedish register-based data. The data include all individuals displaced due to plant closures in 1987 and 1988, and a random sample of 200,000 employed individuals. The results suggest that displacement almost doubles the probability of entering self-employment the year after displacement. A sub-sample analysis indicates that individuals with a potentially worse position on the labor market react more strongly to displacement in terms of entering self-employment.</p><p>Essay 3: A large literature has studied the effect of displacement on labor market outcomes in general, but no one has evaluated how the displaced succeed as self-employed. This paper studies how the survival of the business is affected by displacement in connection to entry, using a discrete-time proportional hazard model on a matched sample of displaced and non-displaced individuals. The main result of the paper is that, as a consequence of previous displacement, the probability of switching from self-employment to paid employment decreases and the probability of switching to unemployment is unaffected.</p>

Bayesian Optimization (BO) methods are often used to optimize an unknown function f(���) that is costly to evaluate. They typically work in an iterative manner. In each iteration, given a set of observation points, BO algorithms select k ��� 1 points to be evaluated. The results of those points are then added to the set of observations and the procedure is repeated until a stopping criterion is met. The goal is to optimize the function f(���) with a small number of experiment evaluations. While this problem has been extensively studied, most existing approaches ignored some real world constraints frequently encountered in practical applications. In this thesis, we extend the BO framework in a number of important directions to incorporate some of these constraints. First, we introduce a constrained BO framework where instead of selecting a precise point at each iteration, we request a constrained experiment that is characterized by a hyper-rectangle in the input space. We introduce efficient sequential and non-sequential algorithms to select a set of constrained experiments that best optimize f(���) within a given budget. Second, we introduce one of the first attempts in batch BO where instead of selecting one experiment at each iteration, a set of k > 1 experiments is selected. This can significantly speedup the overall running time of BO. Third, we introduce scheduling algorithms for the BO framework when: 1) it is possible to run concurrent experiments; 2) the durations of experiments are stochastic, but with a known distribution; and 3) there is a limited number of experiments to run in a fixed amount of time. We propose both online and offline scheduling algorithms that effectively handle these constraints. Finally, we introduce a hybrid BO approach which switches between the sequential and batch mode. The proposed hybrid approach provides us with a substantial speedup against sequential policies without significant performance loss. / Graduation date: 2013

Mathematical program with equilibrium constraints (MPEC)has extensive applications in practical areas such as traffic control, engineering design, and economic modeling. Some generalized stationary points of MPEC are studied to better describe the limiting points produced by interior point methods for MPEC.A primal-dual interior point method is then proposed, which solves a sequence of relaxed barrier problems derived from MPEC. Global convergence results are deduced without assuming strict complementarity or linear independence constraint qualification. Under very general assumptions, the algorithm can always find some point with strong or weak stationarity. In particular, it is shown that every limiting point of the generated sequence is a piece-wise stationary point of MPEC if the penalty parameter of the merit function is bounded. Otherwise, a certain point with weak stationarity can be obtained. Preliminary numerical results are satisfactory, which include a case analyzed by Leyffer for which the penalty interior point algorithm failed to find a stationary solution. / Singapore-MIT Alliance (SMA)

The Diameter-Constrained Minimum Spanning Tree Problem seeks a least cost spanning tree subject to a (diameter) bound imposed on the number of edges in the tree between any node pair. A traditional multicommodity flow model with a commodity for every pair of nodes was unable to solve a 20-node and 100-edge problem after one week of computation. We formulate the problem as a directed tree from a selected central node or a selected central edge. Our model simultaneously finds a central node or a central edge and uses it as the source for the commodities in a directed multicommodity flow model with hop constraints. The new model has been able to solve the 20-node, 100-edge instance to optimality after less than four seconds. We also present model enhancements when the diameter bound is odd (these situations are more difficult). We show that the linear programming relaxation of the best formulations discussed in this paper always give an optimal integer solution for two special, polynomially-solvable cases of the problem. We also examine the Diameter Constrained Minimum Steiner Tree problem. We present computational experience in solving problem instances with up to 100 nodes and 1000 edges. The largest model contains more than 250,000 integer variables and more than 125,000 constraints.

This report describes the UNITRAN (UNIversal TRANslator) system, an implementation of a principle-based approach to natural language translation. The system is "interlingual", i.e., the model is based on universal principles that hold across all languages; the distinctions among languages are handled by settings of parameters associated with the universal principles. Interaction effects of linguistic principles are handled by the syste so that the programmer does not need to specifically spell out the details of rule applications. Only a small set of principles covers all languages; thus, the unmanageable grammar size of alternative approaches is no longer a problem.

The first essay constitutes a theory which lends truth to the Kuznets hypothesis. The attention is centered on the role of financial markets in defining the process of knowledge accumulation, and ultimately the distribution of income earning capabilities in a population of ex ante heterogeneous individuals. The provision of credit is hindered by one-sided lack of commitment embedded in the area of educational investment. Adaptation in the legislative system to accommodate a punishment scheme conditional on default is the critical requirement for the economy to be carried on a dynamic growth path, albeit one of higher and worsening inequality. Owing to the accumulation of human capital and the associated externality on future generations’ knowledge productivity, the economy ultimately makes its transition to a state of lower income differentials. The second essay is an enquiry on the role of monetary policy in determining the growth dynamics of a small open economy. We postulate that the possibility of intermediated credit does not exist, the intention of the assumption being to uncover the role of inflation as tax on private spending. The analysis brings a valid argument of the superneutrality of money. Inflation when operating as consumption tax has no impact on the growth rate of output. This is established irrespective of the labor supply be held fixed, or incorporated as endogenous decision. When imitating the role of capital taxation, inflationary policy has a negative effect on capital accumulation in a framework of fixed labor supply. However, the validity of the superneutrality result is once again reestablished in an environment accommodating the endogeneity of labor supply. The third essay is a theoretical investigation of the long-run effects of tax and expenditure policies in an open economy framework. The aim is to establish an analytic basis for the factual evidence associated with the non-monotonic response of the current account to fiscal shocks. To this endeavor we sought two sources of time non-separability in the preference structure, habit-forming consumption in consumer durable goods. Optimal private choices induce non-monotonic dynamics on consumption behavior that are exactly consistent with the evidence on the current account.

Compared to conventional Steiner tree signal net routing, non-tree topology is often superior in many aspects including timing performance, tolerance to open faults and variations. In nano-scale VLSI designs, interconnect delay is a performance bottleneck and variation effects are increasingly problematic. Therefore the advantages of non-tree topology are particularly appealing for timing critical net routings in nano-scale VLSI designs. We propose Steiner network construction heuristics which can generate either tree or non-tree of signal net with different slack wirelength tradeoffs, and handle both long path and short path constraints. Extensive experiments in different scenarios show that our heuristics usually improve timing slack by hundreds of pico seconds compared to traditional tree approaches while increasing only slightly in wirelength. These results show that our algorithm is a very promising approach for timing critical net routings.

Conformal field theories (CFT) constitute an interesting class of twodimensionalquantum field theories, with applications in string theoryas well as condensed matter physics. The symmetries of a CFT can beencoded in the mathematical structure of a conformal vertex algebra.The rational CFT’s are distinguished by the property that the categoryof representations of the vertex algebra is a modular tensor category.The solution of a rational CFT can be split off into two separate tasks, apurely complex analytic and a purely algebraic part. The TFT-construction gives a solution to the second part of the problem.This construction gets its name from one of the crucial ingredients,a three-dimensional topological field theory (TFT). The correlators obtainedby the TFT-construction satisfy all consistency conditions of thetheory. Among them are the factorization constraints, whose implicationsfor boundary conditions are the main topic of this thesis. The main result reviewed in this thesis is that the factorization constraintsgive rise to a semisimple commutative associative complex algebrawhose irreducible representations are the so-called reflection coefficients.The reflection coefficients capture essential information aboutboundary conditions, such as ground-state degeneracies and Ramond-Ramond charges of string compactifications. We also show that the annuluspartition function can be derived fromthis classifying algebra andits representation theory.

This thesis consists of an introduction and sevenindependent, but closely related, papers which all deal withproblems in structural optimization. In particular, we considermodels and methods for global optimization of problems intopology design of discrete and continuum structures. In the first four papers of the thesis the nonconvex problemof minimizing the weight of a truss structure subject to stressconstraints is considered. First itis shown that a certainsubclass of these problems can equivalently be cast as linearprograms and thus efficiently solved to global optimality.Thereafter, the behavior of a certain well-known perturbationtechnique is studied. It is concluded that, in practice, thistechnique can not guarantee that a global minimizer is found.Finally, a convergent continuous branch-and-bound method forglobal optimization of minimum weight problems with stress,displacement, and local buckling constraints is developed.Using this method, several problems taken from the literatureare solved with a proof of global optimality for the firsttime. The last three papers of the thesis deal with topologyoptimization of discretized continuum structures. Theseproblems are usually modeled as mixed or pure nonlinear 0-1programs. First, the behavior of certain often usedpenalization methods for minimum compliance problems isstudied. It is concluded that these methods may fail to producea zero-one solution to the considered problem. To remedy this,a material interpolation scheme based on a rational functionsuch that compli- ance becomes a concave function is proposed.Finally, it is shown that a broad range of nonlinear 0-1topology optimization problems, including stress- anddisplacement-constrained minimum weight problems, canequivalently be modeled as linear mixed 0-1 programs. Thisresult implies that any of the standard methods available forgeneral linear integer programming can now be used on topologyoptimization problems. <b>Keywords:</b>topology optimization, global optimization,stress constraints, linear programming, mixed integerprogramming, branch-and-bound.