MINIZINC, Modeling, CNF -- 3

I need a help with a little project. The instrucctions are in the pdf attached.

Modeling the following problem and then programming in MiniZinc:

1 Description of the Problem

A large number of typical data analysis problems appearing in medicine and in numerous other areas can be formulated in the following way. Consider a dataset consisting of two disjoint sets O+ and O- of t-dimensional boolean vectors. For instance, with t = 8 we may have,

O+ = {(0,0,1,0,1,0,0,0),(1,0,1,1,0,0,0,1),(0,1,0,1,0,0,1,1), (0,1,1,0,1,1,0,1),(0,0,1,0,1,1,1,1)}

and

O- = {(1,1,0,0,1,0,1,1),(0,1,0,0,1,1,0,0),(1,0,0,1,1,0,0,1)}

Typically each vector appearing in the dataset corresponds to a patient or a set of similar patients, the vectors in O+ corresponding to patients having a specific medical condition (e.g. pneumonia), while those in O- (the controls in medical language) do not have that condition. The components of the vectors, called attributes, or features, or sometimes variables, represent the results of certain measurements or tests and indicate the presence or absence of certain symptoms (e.g. fever, high blood pressure,...). For instance, if the second attribute in the previous example denotes fever, we can observe that fever is not a necessary symptom for pneumonia since there are patients with fever both in both O+ and O-.

The dataset is assumed to contain sufficient information to characterize the disease. In practice, the dataset usually contains a number of redundant attributes (i.e, not all of them are really needed to characterize the medical

1

condition). In the following we describe a simple combinatorial optimization problem for eliminating redundant attributes.

Let T = {1,2,...,t} be the set of attributes. A set S ? T is called a support set if the projection on S of O+ is disjoint from the projection on S of O-. Recall that the projection of a t-dimensional vector v over S ? T is a |S|-dimensional vector v' obtained removing from v the components not in S. The projection of a set of t-dimensional vectors over S ? T is the set of |S|-dimensional vectors obtained by projecting all the vectors of the original set over S. For instance, if we project O+ over {1, 3, 4} we obtain,

{(0,1,0),(1,1,1),(0,0,1),(0,1,0),(0,1,0)}

Short support sets are important because they are some sort of short characterizations of the medical condition. One of the interest of support sets is in diagnosis. Let v be the vector of attributes on the support set of a new patient. If v matches with some vector in the projection on S of O+ it is likely that the patient has the condition. If v matches with some vector in the projection on S of O- it is unlikely that the patient has the condition.

Since we may need to measure the S-attributes of new patients, we may require support sets to satisfy specific constraints. For instance, we may not want S to contain too many expensive tests (for economical reasons), or we may not want S to contain too many aggressive tests (for humanitarian rea- sons). In this project, for simplicity, we will restrict ourselves to the At most one constraint. Let A ? T. A support set S satisfies the AtMostOne(A) constraint iff S contains at most one element of A (i.e, |S n A| = 1).

We are now ready to define the problem that we want to consider in the project. Consider two disjuct sets O+ and O- of t-dimensional boolean vectors, a natural number k and a list A1, A2, . . . , Ac ? T of sets of attributes. WewanttofindasetS?T suchthat:

2

1. SisasupportsetofO+ andO-

2. its size is bounded by k (that is, |S| = k).

3. S satisfies the Atmostone constraint with respect to A1, A2, . . . , Ac.

Data Analytics Wprowadzanie danych Przetwarzanie danych Prezentacje kolekcji mody Matematyka

Numer ID Projektu: #18180440

O projekcie