Activator Protein-1 (AP-1) is an oncogenic transcription factor that is dysregulated in numerous human cancers, making it an attractive therapeutic target. AP-1 forms via interaction of cJun and cFos proteins, which intertwine to generate a ‘coiled coil’ (CC) structure. Thus, the cJun/cFos α-helical CC domains responsible for dimerisation are appealing targets for inhibiting AP-1 formation and activity. Helical peptide antagonists that sequester cJun can be derived from the cFos CC domain by selection of more optimal amino acids for increased binding affinity. Peptides can then be downsized and modified to improve therapeutic potential. Two approaches aimed to identify novel short peptides against cJun. The first was to covalently cyclise amino acid side chains in existing cFos-derived peptide “FosW”, with the aim of constraining FosW into a stable helix to allow downsizing without significant loss of binding structure and affinity. Using circular dichroism spectroscopy and isothermal titration calorimetry, a series of helix constrained peptides were characterised, from which a peptide was identified that retained 88 % of FosW binding affinity whilst being 22 % shorter, and which entered breast cancer cells in vitro, with preliminary data suggesting potential ability to inhibit AP-1 in cellulo. The second approach was to combine two existing high-throughput peptide selection systems, with the aim of benefitting from overlap in their strengths and weaknesses. Combination of in vitro CIS display and in cellulo Protein-fragment Complementation Assay successfully isolated a high affinity peptide from a hugely diverse library, and future refinements to further exploit this approach, particularly for short peptide selection, were formulated. Thus, molecules and techniques derived here may expedite the future development of therapies for cancers featuring AP-1 dysregulation.

The quickest change-point detection problems with sampling right constraints are considered. Specially, an observer sequentially takes observations from a random sequence, whose distribution will change at an unknown time. Based on the observation sequence, the observer wants to identify the change-point as quickly as possible. Unlike the classic quickest detection problem in which the observer can take an observation at each time slot, we impose a causal sampling right constraint to the observer. In particular, sampling rights are consumed when the observer takes an observation and are replenished randomly by a stochastic process. The observer cannot take observations if there is no sampling right left. The causal sampling right constraint is motivated by several practical applications. For example, in the application of sensor network for monitoring the abrupt change of its ambient environment, the sensor can only take observations if it has energy left in its battery. With this additional constraint, we design and analyze the optimal detection and sampling right allocation strategies to minimize the detection delay under various problem setups. As one of our main contributions, a greedy sampling right allocation strategy, by which the observer spends sampling rights in taking observations as long as there are sampling rights left, is proposed. This strategy possesses a low complexity structure, and leads to simple but (asymptotically) optimal detection algorithms for the problems under consideration. Specially, our main results include: 1) Non-Bayesian quickest change-point detection: we consider non-Bayesian quickest detection problem with stochastic sampling right constraint. Two criteria, namely the algorithm level average run length (ARL) and the system level ARL, are proposed to control the false alarm rate. We show that the greedy sampling right allocation strategy combined with the cumulative sum (CUSUM) algorithm is optimal for Lorden's setup with the algorithm level ARL constraint and is asymptotically optimal for both Lorden's and Pollak's setups with the system level ARL constraint. 2) Bayesian quickest change-point detection: both limited sampling right constraint and stochastic sampling right constraint are considered in the Bayesian quickest detection problem. The limited sampling right constraint can be viewed as a special case of the stochastic sampling right constraint with a zero sampling right replenishing rate. The optimal solutions are derived for both sampling right constraints. However, the structure of the optimal solutions are rather complex. For the problem with the limited sampling right constraint, we provide asymptotic upper and lower bounds for the detection delay. For the problem with the stochastic sampling right constraint, we show that the greedy sampling right allocation strategy combined with Shiryaev's detection rule is asymptotically optimal. 3) Quickest change-point detection with unknown post-change parameters: we extend previous results to the quickest detection problem with unknown post-change parameters. Both non-Bayesian and Bayesian setups with stochastic sampling right constraints are considered. For the non-Bayesian problem, we show that the greedy sampling right allocation strategy combined with the M-CUSUM algorithm is asymptotically optimal. For the Bayesian setups, we show that the greedy sampling right allocation strategy combined with the proposed M-Shiryaev algorithm is asymptotically optimal.

在約束滿足問題中，破壞指數量級數量的所有對稱通常過於昂貴。在實踐中，我們通常只有效地破壞對稱的一個子集。我們稱之為目標對稱。在靜態對稱破壞中，我們的目標是發佈一套約束去破壞這些目標對稱，以達到減少解集以及搜索空間的效果。一個問題中的所有對稱之間是互相交織的。一個旨在特定對稱的破壞對稱約束几乎總會產生副作用，而不僅僅破壞了預期的對稱。破壞相同目標對稱的不同約束可以有不同的副作用。傳統智慧告訴我們應該選擇一個破壞更多對稱從而有更多副作用的破壞對稱約束。雖然這樣的說法在許多方面上都是有效的，我們應該更加注意副作用發生的地方。 / 給與一個約束滿足問題，一個對稱被一個約束保留當且僅當該對稱仍然是新的約束滿足問題的對稱。這個新的約束滿足問題是有原問題加上該約束組成的。我們給出定律和例子，以表明發佈儘量保留目標對稱以及限制它的副作用發生在非目標對稱上的破壞約束是有利的。這些好處來自于被破壞的對稱數目以及一個對稱被破壞（或消除）的程度，并導致一個較小的解集和搜索空間。但是，對稱不一定會被保留。我們顯示，旨在一個已經被消除的目標對稱的破壞對稱約束仍然可以被發佈。我們建議根據問題的約束以及其他破壞對稱約束來選擇破壞對稱約束，以繼續消除更多的對稱。我們進行了廣泛的實驗來確認我們的建議的可行性與效率。 / Breaking the exponential number of all symmetries of a constraint satisfaction problem is often too costly. In practice, we often aim at breaking a subset of the symmetries efficiently, which we call target symmetries. In static sym-metry breaking, the goal is to post a set of constraints to break these target symmetries in order to reduce the solution set and thus also the search space. Symmetries of a problem are all intertwined. A symmetry breaking constraint intended for a particular symmetry almost always breaks more than just the intended symmetry as a side-effect. Different constraints for breaking the same target symmetry can have different side-effects. Conventional wisdom suggests that we should select a symmetry breaking constraint that has more side-effects by breaking more symmetries. While this wisdom is valid in many ways, we should be careful where the side-effects take place. / A symmetry σ of a CSP P =(V, D, C) is preserved by a set of symmetry breaking constraints C{U+02E2}{U+1D47} i σ is a symmetry of P¹ =(V, D, CU C{U+02E2}{U+1D47}). We give theorems and examples to demonstrate that it is beneficial to post symmetry breaking constraints that preserve the target symmetries and restrict the side-effects to only non-target symmetries as much as possible. The benefits are in terms of the number of symmetries broken and the extent to which a symmetry is broken (or eliminated), resulting in a smaller solution set and search space. However, symmetry preservation may not always hold. We illustrate that symmetry breaking constraints, which aim at a target symmetry that is already eliminated, can still be posted. To continue eliminating more symmetries, we suggest to select symmetry breaking constraints based on problem constraints and other symmetry breaking constraints. Extensive experiments are also conducted to confirm the feasibility and efficiency of our proposal empirically. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Li, Jingying. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 101-112). / Abstracts also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.1 / Chapter 1.2 --- Motivation and Goals --- p.3 / Chapter 1.3 --- Outline of Thesis --- p.5 / Chapter 2 --- Background --- p.8 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.8 / Chapter 2.1.1 --- Backtracking Search --- p.9 / Chapter 2.1.2 --- Consistency Techniques --- p.12 / Chapter 2.1.3 --- Local Consistencies with Backtracking Search --- p.15 / Chapter 2.2 --- Symmetry Breaking in CSPs --- p.16 / Chapter 2.2.1 --- Symmetry Classes --- p.18 / Chapter 2.2.2 --- Breaking Symmetries --- p.22 / Chapter 2.2.3 --- Variable and Value Symmetries --- p.23 / Chapter 2.2.4 --- Symmetry Breaking Constraints --- p.26 / Chapter 3 --- Effects of Symmetry Breaking Constraints --- p.29 / Chapter 3.1 --- Removing Symmetric Search Space --- p.29 / Chapter 3.1.1 --- Properties --- p.30 / Chapter 3.1.2 --- Canonical Variable Orderings --- p.31 / Chapter 3.1.3 --- Regenerating All Solutions --- p.33 / Chapter 3.1.4 --- Remaining Solution Set Sizes --- p.36 / Chapter 3.2 --- Constraint Interactions in Propagation --- p.43 / Chapter 4 --- Choices of Symmetry Breaking Constraints --- p.45 / Chapter 4.1 --- Side-Effects --- p.45 / Chapter 4.2 --- Symmetry Preservation --- p.50 / Chapter 4.2.1 --- De nition and Properties --- p.50 / Chapter 4.2.2 --- Solution Reduction --- p.54 / Chapter 4.2.3 --- Preservation Examples --- p.55 / Chapter 4.2.4 --- Preserving Order --- p.64 / Chapter 4.3 --- Eliminating Eliminated Symmetries --- p.65 / Chapter 4.3.1 --- Further Elimination --- p.65 / Chapter 4.3.2 --- Aggressive Elimination --- p.71 / Chapter 4.4 --- Interactions with Problem Constraints --- p.72 / Chapter 4.4.1 --- Further Simplification --- p.72 / Chapter 4.4.2 --- Increasing Constraint Propagation --- p.73 / Chapter 5 --- Experiments --- p.75 / Chapter 5.1 --- Symmetry Preservation --- p.75 / Chapter 5.1.1 --- Diagonal Latin Square Problem --- p.76 / Chapter 5.1.2 --- NN-Queen Problem --- p.77 / Chapter 5.1.3 --- Error Correcting Code - Lee Distance (ECCLD) --- p.78 / Chapter 5.2 --- Eliminating Eliminated Symmetries --- p.80 / Chapter 5.2.1 --- Equidistance Frequency Permutation Array Problem --- p.80 / Chapter 5.2.2 --- Cover Array Problem --- p.82 / Chapter 5.2.3 --- Sports League Scheduling Problem --- p.83 / Chapter 6 --- Related Work --- p.86 / Chapter 6.1 --- Symmetry Breaking Approaches --- p.86 / Chapter 6.2 --- Reducing Overhead and Increasing Propagation --- p.90 / Chapter 6.3 --- Selecting and Generating Choices --- p.91 / Chapter 6.3.1 --- Reducing Conflict with Search Heuristic --- p.92 / Chapter 6.3.2 --- Choosing the Subset of Symmetries --- p.93 / Chapter 6.4 --- Detecting Symmetries --- p.93 / Chapter 7 --- Conclusion and Remarks --- p.95 / Chapter 7.1 --- Conclusion --- p.95 / Chapter 7.2 --- Discussions --- p.97 / Chapter 7.3 --- Future Work --- p.99 / Bibliography --- p.101

by Won, Hon Wing Stephen. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1997. / Includes bibliographical references (leaves 95-101). / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problem --- p.1 / Chapter 1.2 --- CSP Solving Techniques --- p.2 / Chapter 1.3 --- Motivation of the Dissertation --- p.4 / Chapter 1.4 --- Overview of the Dissertation --- p.6 / Chapter 2 --- Related Work --- p.8 / Chapter 2.1 --- Heuristic Repair Method --- p.8 / Chapter 2.2 --- GSAT --- p.8 / Chapter 2.3 --- GENET --- p.9 / Chapter 2.4 --- Simulated Annealing --- p.9 / Chapter 2.5 --- Genetic Algorithms --- p.10 / Chapter 3 --- Overview of GENET --- p.11 / Chapter 3.1 --- Network Architecture --- p.11 / Chapter 3.2 --- Convergence Procedure --- p.12 / Chapter 3.3 --- The illegal and atmost Constraints --- p.13 / Chapter 3.3.1 --- The illegal Constraint --- p.14 / Chapter 3.3.2 --- The atmost Constraint --- p.14 / Chapter 3.4 --- General Non-Binary Constraints --- p.15 / Chapter 3.4.1 --- Constraint Transformation --- p.15 / Chapter 3.4.2 --- Using the illegal Constraints --- p.17 / Chapter 3.4.3 --- Problem Transformation --- p.17 / Chapter 4 --- An Extended GENET --- p.20 / Chapter 4.1 --- Network Architecture --- p.20 / Chapter 4.2 --- Convergence Procedure --- p.22 / Chapter 4.3 --- E-GENET as a Generalization of GENET --- p.24 / Chapter 4.3.1 --- Constraints --- p.30 / Chapter 4.3.2 --- Network Architecture --- p.31 / Chapter 4.4 --- Properties of E-GENET --- p.32 / Chapter 4.4.1 --- Incompleteness of E-GENET --- p.33 / Chapter 4.4.2 --- Making E-GENET Complete --- p.36 / Chapter 4.5 --- Storage Scheme --- p.38 / Chapter 4.5.1 --- The illegal and atmost Constraint --- p.39 / Chapter 4.5.2 --- The Disequality Constraint --- p.39 / Chapter 4.5.3 --- General Constraints --- p.40 / Chapter 4.6 --- Benchmarking Results --- p.40 / Chapter 4.6.1 --- The Graph-Coloring Problem --- p.41 / Chapter 4.6.2 --- The N-queens Problem --- p.42 / Chapter 4.6.3 --- The Car-Sequencing Problem --- p.43 / Chapter 4.6.4 --- The Cryptarithmetic Problem --- p.44 / Chapter 4.6.5 --- The Hamiltonian Path Problem --- p.45 / Chapter 5 --- Optimizations to E-GENET --- p.47 / Chapter 5.1 --- Inadequacies of E-GENET --- p.47 / Chapter 5.1.1 --- Cumbrous Constraint Node --- p.48 / Chapter 5.1.2 --- Inefficiency of the min-conflicts heuristic --- p.48 / Chapter 5.2 --- Optimizations --- p.50 / Chapter 5.2.1 --- Intermediate Node --- p.50 / Chapter 5.2.2 --- New Assignment Scheme of Initial Penalty Values --- p.55 / Chapter 5.2.3 --- Concept of Contribution --- p.57 / Chapter 5.2.4 --- Learning Heuristic --- p.62 / Chapter 6 --- A Comprehensive Constraint Library --- p.63 / Chapter 6.1 --- Elementary Constraints --- p.64 / Chapter 6.1.1 --- Linear Arithmetic Constraints --- p.64 / Chapter 6.1.2 --- The atmost Constraint --- p.66 / Chapter 6.1.3 --- Disjunctive Constraints --- p.69 / Chapter 6.2 --- Global Constraints --- p.71 / Chapter 6.2.1 --- The cumulative Constraint --- p.72 / Chapter 6.2.2 --- The among Constraint --- p.77 / Chapter 6.2.3 --- The diffn Constraint --- p.82 / Chapter 6.2.4 --- The cycle Constraint --- p.85 / Chapter 7 --- Conclusion --- p.89 / Chapter 7.1 --- Contributions --- p.89 / Chapter 7.2 --- Discussions --- p.90 / Chapter 7.3 --- Future Work --- p.94 / Bibliography --- p.95

Mak, Wai Keung Terrence. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2011. / Includes bibliographical references (p. 100-104). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Constraint Satisfaction Problems --- p.1 / Chapter 1.2 --- Weighted Constraint Satisfaction Problems --- p.2 / Chapter 1.3 --- Quantified Constraint Satisfaction Problems --- p.3 / Chapter 1.4 --- Motivation and Goal --- p.4 / Chapter 1.5 --- Outline of the Thesis --- p.6 / Chapter 2 --- Background --- p.7 / Chapter 2.1 --- Constraint Satisfaction Problems --- p.7 / Chapter 2.1.1 --- Backtracking Tree Search --- p.9 / Chapter 2.1.2 --- Local Consistencies for solving CSPs --- p.11 / Node Consistency (NC) --- p.13 / Arc Consistency (AC) --- p.14 / Searching by Maintaining Arc Consistency --- p.16 / Chapter 2.1.3 --- Constraint Optimization Problems --- p.17 / Chapter 2.2 --- Weighted Constraint Satisfaction Problems --- p.19 / Chapter 2.2.1 --- Branch and Bound Search (B&B) --- p.23 / Chapter 2.2.2 --- Local Consistencies for WCSPs --- p.25 / Node Consistency --- p.26 / Arc Consistency --- p.28 / Chapter 2.3 --- Quantified Constraint Satisfaction Problems --- p.32 / Chapter 2.3.1 --- Backtracking Free search --- p.37 / Chapter 2.3.2 --- Consistencies for QCSPs --- p.38 / Chapter 2.3.3 --- Look Ahead for QCSPs --- p.45 / Chapter 3 --- Quantified Weighted CSPs --- p.48 / Chapter 4 --- Branch & Bound with Consistency Techniques --- p.54 / Chapter 4.1 --- Alpha-Beta Pruning --- p.54 / Chapter 4.2 --- Consistency Techniques --- p.57 / Chapter 4.2.1 --- Node Consistency --- p.62 / Overview --- p.62 / Lower Bound of A-Cost --- p.62 / Upper Bound of A-Cost --- p.66 / Projecting Unary Costs to Cθ --- p.67 / Chapter 4.2.2 --- Enforcing Algorithm for NC --- p.68 / Projection Phase --- p.69 / Pruning Phase --- p.69 / Time Complexity --- p.71 / Chapter 4.2.3 --- Arc Consistency --- p.73 / Overview --- p.73 / Lower Bound of A-Cost --- p.73 / Upper Bound of A-Cost --- p.75 / Projecting Binary Costs to Unary Constraint --- p.75 / Chapter 4.2.4 --- Enforcing Algorithm for AC --- p.76 / Projection Phase --- p.77 / Pruning Phase --- p.77 / Time complexity --- p.79 / Chapter 5 --- Performance Evaluation --- p.83 / Chapter 5.1 --- Definitions of QCOP/QCOP+ --- p.83 / Chapter 5.2 --- Transforming QWCSPs into QCOPs --- p.90 / Chapter 5.3 --- Empirical Evaluation --- p.91 / Chapter 5.3.1 --- Random Generated Problems --- p.92 / Chapter 5.3.2 --- Graph Coloring Game --- p.92 / Chapter 5.3.3 --- Min-Max Resource Allocation Problem --- p.93 / Chapter 5.3.4 --- Value Ordering Heuristics --- p.94 / Chapter 6 --- Concluding Remarks --- p.96 / Chapter 6.1 --- Contributions --- p.96 / Chapter 6.2 --- Limitations and Related Works --- p.97 / Chapter 6.3 --- Future Works --- p.99 / Bibliography --- p.100

We develop a framework for finding robust solutions of constraint programs. Our approach is based on the notion of fault tolerance. We formalise this concept within constraint programming, extend it in several dimensions and introduce some algorithms to find robust solutions efficiently. When applying constraint programming to real world problems we often face uncertainty. Whilst reactive methods merely deal with the consequences of an unexpected change, taking a more proactive approach may guarantee a certain level of robustness. We propose to apply the fault tolerance framework, introduced in [Ginsberg 98], to constraint programming: A robust solution is one such that a small perturbation only requires a small response. We identify, define and classify a number of abstract problems related to stability within constraint satisfaction or optimisation. We propose some efficient and effective algorithms for solving these problems. We then extend this framework by allowing the repairs and perturbations themselves to be constrained. Finally, we assess the practicality of this framework on constraint satisfaction and scheduling problems.

<p>The world’s population is ageing. Due to societal improvements in healthcare, living standards, and socio-economic status, more and more people are living to old age. The proportion of the world's population aged 65 or over is expected to increase from 11% in 1998 to 16% in 2025. This causes a major public health issue, because with increased age there is an increased risk of developing a number of age-related diseases. However, there is increasing scientific evidence that many of the biological changes and risks for chronic disease, which have traditionally been attributed to ageing, are in fact caused by malnutrition (sub-optimal diets and nutrient intakes).</p><p>This report presents a constraint satisfaction approach to planning meals while taking into account amongst other things nutritional and economic factors. Two models for generating meal plans are presented and their respective strengths and weaknesses discussed. System design, implementation and the main algorithms used are described in more detail. These algorithms include Depth First Branch and Bound and its various improvements for meal plan generation as well as Item-based Collaborative Filtering for user preferences. Our test runs show that the system works well for smaller applications but runs into problems when the number of available recipes grows or a larger number of meals are planned. The tests also show that the two modelling approaches both have useful applications. Based on the test results some suggestions for further improvement of the system conclude the report.</p>

This work considers initial value problems (IVPs) for ordinary differential equations (ODEs) where some of the data is uncertain and given by intervals as is the case in many areas of science and engineering. Interval methods provide a way to approach these problems but they raise fundamental challenges in obtaining high accuracy and low computation costs. This work introduces a constraint satisfaction approach to these problems which enhances traditional interval methods with a pruning step based on a global relaxation of the ODE. The relaxation uses Hermite interpolation polynomials and enclosures of their error terms to approximate the ODE. Our work also shows how to find an evaluation time for the relaxation that minimizes its local error. Theoretical and experimental results show that the approach produces significant improvements in accuracy over the best interval methods for the same computation costs. The results also indicate that the new algorithm should be significantly faster when the ODE contains many operations.

A mechanical design "compiler" has been developed which, given an appropriate schematic, specifications, and utility function for a mechanical design, returns catalog numbers for an optimal implementation. The compiler has been successfully tested on a variety of mechanical and hydraulic power transmission designs and a few temperature sensing designs. Times required have been at worst proportional to the logarithm of the number of possible combinations of catalog numbers.

This work considers initial value problems (IVPs) for ordinary differential equations (ODEs) where some of the data is uncertain and given by intervals as is the case in many areas of science and engineering. Interval methods provide a way to approach these problems but they raise fundamental challenges in obtaining high accuracy and low computation costs. This work introduces a constraint satisfaction approach to these problems which enhances traditional interval methods with a pruning step based on a global relaxation of the ODE. The relaxation uses Hermite interpolation polynomials and enclosures of their error terms to approximate the ODE. Our work also shows how to find an evaluation time for the relaxation that minimizes its local error. Theoretical and experimental results show that the approach produces significant improvements in accuracy over the best interval methods for the same computation costs. The results also indicate that the new algorithm should be significantly faster when the ODE contains many operations.