Claudio Vitari
email: cvitari@liuc.it

Aurelio Ravarini
email: aravarini@liuc.it

Bernard Fallery
email: bernard.fallery@univ-montp2.fr

Ravarini Aurelio

THE KMS RECOMMENDING EXPERTS IN THE COMMUNITIES: PROPOSITION OF A THEORY ON THEIR SUCCESS

d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

RESEARCH CONTEXT

In the diversity of the Information Systems research [START_REF] Vessey | Research in Information Systems: An Empirical Study of Diversity in the Discipline and its Journal[END_REF] this study is backed up by the Information Systems and Management as its main reference disciplines. The research topic is Knowledge Management, which is studied at the level of the individuals, as members of Knowledge Communities.

Within the organizations, the management of knowledge is an ever-green issue and it has been using the existing technologies to reach the highest levels of efficiency and competitiveness [START_REF] Guida | Ingegneria della conoscenza : strumenti per innovare e per competere[END_REF]. In our society [START_REF] Nonaka | The knowledge creating company[END_REF][START_REF] Mcdermott | Why Information Technology Inspired But Cannot Deliver Knowledge Management[END_REF][START_REF] Mcdermott | Overcoming cultural barriers to sharing knowledge[END_REF], knowledge is considered by individuals and organizations an economic resource and knowledge upsurges as the only sustainable, in the long run, competitive advantage [START_REF] Nonaka | The knowledge creating company[END_REF][START_REF] Abecker | Organizational Memory: knowledge acquisition, integration and retrivial issues in knowledge-based systems[END_REF][START_REF] Liu | An Empirical Investigation of Expertise Matching within Academia[END_REF] Nowadays, Information and Communication Technologies (ICT) are giving chances to enhance the management of knowledge in the organizations containing its costs [START_REF] Sveiby | The New Organizational Wealth, Managing and Measuring Knowledge-Based Assets[END_REF]). In the attempt to contain costs, organizations are also trying to form their members basing on the existing knowledge as far as creating new knowledge is more expensive than transferring existing knowledge [START_REF] Nonaka | A dynamic theory of organizational knowledge creation[END_REF][START_REF] Smith | Developments in practice IX: the evolution of the KM function[END_REF].

Empirical results demonstrates that the ability to transfer knowledge contributes to the organizational performance of firms in both the manufacturing [START_REF] Galbraith | Transferring Core Manufacturing Technologies in High-Technology Firms[END_REF][START_REF] Epple | An empirical investigation of the micro structure of knowledge acquisition and transfer through learning by doing[END_REF] and service sectors [START_REF] Darr | The acquisition, transfer, and depreciation of knowledge in service organizations : productivity in franchises[END_REF][START_REF] Baum | Survival-enhancing learning in the Manhattan hotel industry, 1898-1980[END_REF]. Although the benefits of knowledge transfer have been documented in many settings, its effectiveness varies considerably among organizations [START_REF] Szulanski | Exploring Internal Stickiness: Impediments to the Transfer of Best Practice Within the Firm[END_REF][START_REF] Argote | Organizational learning: Creating, retaining, and transferring knowledge[END_REF] Knowledge transfer is the only way to form people basing on the existing knowledge and it is accomplishes in multiple ways: from the training courses to a debate during a coffee break [START_REF] Brown | Organizational learning and communities of practice[END_REF][START_REF] Nonaka | A dynamic theory of organizational knowledge creation[END_REF][START_REF] Davenport | Ten principles of knowledge management and four case studies[END_REF][START_REF] Sussman | Informational Influence in Organizations: An Integrated Approach to Knowledge Adoption[END_REF]. Even though knowledge transfer could assume different forms, some limits exist and they depend on the object of transfer. The particularity of knowledge transfer, in comparison with the transfer of other resources, is due to a property of knowledge. Knowledge does not exhaust itself through its use but, on the contrary, its use brings to its rise and development, through a virtual growing circle [START_REF] Guida | Ingegneria della conoscenza : strumenti per innovare e per competere[END_REF].

Knowledge involves cognitive structures and processes and it cannot be embodied as texts or other explicit representations [START_REF] Brown | Organizational learning and communities of practice[END_REF][START_REF] Nonaka | A dynamic theory of organizational knowledge creation[END_REF][START_REF] Davenport | Ten principles of knowledge management and four case studies[END_REF][START_REF] Becerra-Fernandez | The role of artificial intelligence technologies in the implementation of People-Finder knowledge management systems[END_REF][START_REF] Sussman | Informational Influence in Organizations: An Integrated Approach to Knowledge Adoption[END_REF]. Knowledge transfer requires always human action, but ICT can nevertheless play an important role in the knowledge transfer by the very beginning.

The first step to knowledge transfer is the recognition of the heterogeneous distribution of knowledge among individuals (O'Dell and Grayson 1998). ICT already supports these activities even though some significant steps could be done forward much more efficient solutions.

The recognition of the heterogeneous distribution of the knowledge among the individuals could induce the knowledge transfer whether there is knowledge redundancy [START_REF] Nonaka | A dynamic theory of organizational knowledge creation[END_REF]) among the sender and potential recipient of knowledge. Knowledge redundancy refers to the existence of information, more than the specific information required immediately by each individual, which is shared between them.

Nonaka [START_REF] Nonaka | A dynamic theory of organizational knowledge creation[END_REF] affirms that this knowledge redundancy is caused by the overlapping of company information, business activities and management responsibilities. This knowledge redundancy is assured by the participation to the same Knowledge Community, which is preliminary definable as a group of people that share a common practice, work, or interest.

The participation to the same Knowledge Community assures the existence of same common knowledge which will be used as basis for the knowledge transfer.

The Knowledge Community has therefore a crucial role in knowledge transfer. In this situation, individuals can enter each others' area of operation and can provide advice. It allows people to provide new information from new and different perspectives, which Nonaka [START_REF] Nonaka | A dynamic theory of organizational knowledge creation[END_REF]) calls learning by intrusion. Redundant knowledge enables the members of the organization to recognize the specialized knowledge of the colleagues and to facilitate the transfer of knowledge [START_REF] Nonaka | A dynamic theory of organizational knowledge creation[END_REF].

In practice, Knowledge Communities are gaining relevance as an organizational resource enabling knowledge transfer among their members for individual and organizational benefits [START_REF] Wenger | Cultivating Communities of Practice: A Guide to Managing Knowledge[END_REF]. However scholars and practitioners debate on the degree of intervention the organization should apply on their Knowledge Communities.

Various examples of firms that support Knowledge Communities, through the use of IT-based systems managing documents or information, exist and some of them very successful. On the other hand, IT-based systems supporting the transfer of knowledge are less diffused and successful.

Since previous research reports the central role of knowledge for competitive advantage, it is imperative for organizations to explore solutions for levering this knowledge. In our attempt to contribute in solving this lag, and under the hypothesis that Knowledge Communities and IT-based systems can facilitate the transfer of knowledge, this research study is proposed.

In the research area where Knowledge Communities, IT-based systems and Knowledge Management overlap, this study focused on the IT-based systems which counsel individuals, who could be potential sources of specialized knowledge, within a Knowledge Community. We call this type of IT-based systems as "Expert Recommender" as it counsels individuals who could likely help the users to solve problems of business process breakdowns, as we hypothesize that these counseled individuals can be potential sources of knowledge for the users who are facing problems of business process breakdowns.

In this research, we study the Expert Recommender as a service. Instead of focusing on the IT in it-self, we are interested in the service it delivers, the Expert Recommender Service, ERS. Consistently with this service perspective, our research object would include also the cases in which this ERS is delivered without any IT support, thus by a specific department or by the members of the Knowledge Community by them-selves.

RESEARCH OBJECTIVE: THE CONCEPTUAL MODEL

The described research context suggests various research streams.

The literature review and the research relevance motivate academic community to give contributions aiming at the advancement on the Expert Recommender Services. Within the described research context, this contribution will describe the success of the Expert Recommender Services within Knowledge Communities.

The major aim of the ERS is the development of the awareness of the individuals on the knowledge domains of the other members of the Knowledge Community.

Therefore, the description of its success is about the degree of awareness obtained in the Knowledge Community and the degree of improvement of the knowledge transfers.

The conceptual model involves therefore three main elements:

The Expert Recommender Service: the Information System service of counseling to the potential recipient of knowledge those individuals who could likely have the specialized knowledge which the potential recipient requires.

The Knowledge Community: a group of individuals that share a common practice, work, or interest as common knowledge, for the integration and transfer of specialized knowledge among the group's members.

The success of the Expert Recommender Service: the degree to which the stakeholders of the ERS are better off. The stakeholders mainly group the ERS providers, the ERS users, the KC, the organization, which means all the subjects involved in the ERS [START_REF] Delone | Information systems success : the quest for the dependant variable[END_REF].

Characteristics of the Expert Recommending Service

Success of the ERS

Characteristics of the Knowledge Community

RESEARCH METHODOLOGY

The original conceptual model is the output of wide literature review on Expert Recommender Service, Knowledge Community and Information System Success.

Academic publications on: "expert" and "expertise", "community", and "success" has been reviewed1 . This strong theoretical background favored an original, but well grounded, theory building process.

STUDY PROPOSITIONS

This study approaches these research objects with some preliminary propositions, which will lead the development of the research question and of the conceptual model. The author, from his empirical experience and the literature review, proposes that:

The Knowledge Communities differ one to another on the values of their The second relevant aspect, emerging from the literature, is about the aim of the ERS. The major aim of the ERS is the development of the awareness of the individuals on the knowledge domains of the other members. Therefore, the description of its success is about the degree of awareness obtained, which could determine an increase in the knowledge transfers.

RESEARCH MODEL

The combination of the different elements grounded in the previous literature, the final model of ERS success can be delineated. The characteristics of the Expert Recommender Service influence the ERS quality. The ERS quality influences the amount of use of the ERS and the users' satisfaction of the ERS. Use and users' satisfaction have and impact on the individuals and on the organization, in terms of knowledge awareness and knowledge transfer. The characteristics of the Knowledge Communities influence the individual perception of all the above mentioned characteristics: the ERS quality, the ERS use, the users' satisfaction, the individual impact and the organizational impact. The literature review reports that Knowledge Communities could have a positive role in knowledge transfer [START_REF] Thompson | Organizations in action[END_REF][START_REF] Van De Ven | Determinants of coordination modes within organizations[END_REF] [START_REF] Levitt | Organizational learning[END_REF][START_REF] Brown | Organizational learning and communities of practice[END_REF][START_REF] Nonaka | A dynamic theory of organizational knowledge creation[END_REF][START_REF] Grant | Toward a knowledge-based theory of the firm[END_REF]Martinez 2004 page 88).

The ERS aims at reducing a barrier to knowledge transfer, which is the unawareness of the knowledge distribution among the members [START_REF] Libby | Member variation, recognition of expertise, and group performance[END_REF][START_REF] Littlepage | Recognition of expertise in decisionmaking groups: Effects of group size and participation patterns[END_REF][START_REF] Littlepage | Effects of task experience and group experience on group performance, member ability, and recognition of expertise[END_REF][START_REF] Davenport | Successful knowledge management projects[END_REF][START_REF] Cross | Knowing What We Know: Supporting Knowledge Creation and Sharing in Social Networks[END_REF]Ruta and Turati 2002 page 151;[START_REF] Borgatti | A Relational View of Information Seeking and Learning in Social Networks[END_REF][START_REF] Kondratova | Design concepts for virtual research and collaborative environments[END_REF][START_REF] Baumann | The effects of variability and expectations on utilization of member expertise and group performance[END_REF][START_REF] Denrell | Managing knowledge in the dark: an empirical study of the reliability of capability evaluations[END_REF][START_REF] Qureshi | Activating knowledge through electronic collaboration: vanquishing the knowledge paradox[END_REF].

This study concludes with a conceptual model which states that the Knowledge Community and the Expert Recommender Service directly influence the success of the ERS.

The empirical measurement of the success of the ERS, and of the knowledge transfer generated by the ERS, remain however unfold, and a future interesting field of investigation.

Figure 1

 1 Figure 1 The description of the success of the ERS

  properties. The Expert Recommender Services vary for their specific technical characteristics, their integrations in an organizational context and their use by the members of the Knowledge Communities. The characteristics of the Knowledge Community influence the success of the Expert Recommender Service. The Expert Recommender Services influence the knowledge transfers among the members of the Knowledge Communities. These propositions give a preliminary perspective of observation on the research objects and inform the definition of the research question. RESEARCH QUESTION These study propositions are developed from a specific point of view and trying to answer the following specific research question: What are the dimensions of the success of the Expert Recommender Services? The literature review evidences that in the organizations, Expert Recommender Services are realized in different ways, from informally provided by the colleagues to formally computer-based ERS systems. The different forms of the ERS and the different organizations, in which they exist, influence their success.

Figure 2

 2 Figure 2 The final model of the ERS success

  ;

	Characteristics of the Expert	Characteristics of the
	Recommender Service	Knowledge Community
		Success of the ERS
		Use
	Service Quality	(volitional) User	Individual Impact (awareness)	Organizational Impact (knowledge transfer)
		Satisfaction

The list can be sent on request.


Martine Labbé

Luisa I Martínez-Merino

Antonio M Rodríguez-Chía

Mixed Integer Linear Programming for Feature Selection in Support Vector Machine

This work focuses on support vector machine (SVM) with feature selection. A MILP formulation is proposed for the problem. The choice of suitable features to construct the separating hyperplanes has been modelled in this formulation by including a budget constraint that sets in advance a limit on the number of features to be used in the classification process. We propose both an exact and a heuristic procedure to solve this formulation in an efficient way. Finally, the validation of the model is done by checking it with some well-known data sets and comparing it with classical classification methods.

Introduction

In supervised classification, we are given a set of objects Ω partitioned into classes and the goal is to build a procedure for classifying new objects into these classes. This type of problem is faced in many fields, including insurance companies (to determine whether an applicant is a high insurance risk or not), banks (to decide whether an applicant is a credit risk or not), medicine (to determine whether a tumor is benign or malignant), etc. This wide field of application has attracted the attention of a number of researchers from different areas.

Currently, these problems are analyzed from different perspectives: artificial intelligence, machine learning, optimization or statistical pattern recognition among others. In this paper we analyze these problems from the point of view of optimization and more specifically, from the perspective of Mathematical Programming [START_REF] Mangasarian | Linear and nonlinear separation of patterns by linear programming[END_REF][START_REF] Mangasarian | Multi-surface method of pattern separationg[END_REF]).

In the partitioning process, the objects of Ω are considered as points in an n-dimensional feature space. However, the number of features is often much larger than the number of objects in the population. Handling such a high number of features could therefore be a difficult task and in addition, the interpretation of the results could also be impossible. In this sense, feature selection consists of eliminating as many features as possible in a given problem, keeping an acceptable accuracy where spurious random variables are removed. Actually, having a minimal number of features often leads to better generalization and simpler models that can be interpreted more easily.

The support vector machine (SVM) is a type of mathematical programming approach developed by [START_REF] Vapnik | Statistical Learning theory[END_REF], and [START_REF] Cortes | Support-vector networks[END_REF]. It has been widely studied and has become popular in many fields of application in recent years; see the introductory description of SVM by [START_REF] Burges | A tutorial on support vector machines for pattern recognition[END_REF]. The SVM is based on margin maximization, which consists of finding the separating hyperplane that is farthest from the closest object. SVM has proven to be a very powerful tool for supervised classification. Recently, [START_REF] Maldonado | Feature selection for support vector machines via mixed integer linear programming[END_REF] proposed two SVM-based models in which feature selection is taken into account by introducing a budget constraint in the formulation, limiting the number of features used in the model, see also [START_REF] Aytug | Feature selection for support vector machines using generalized benders decomposition[END_REF] and [START_REF] Gaudioso | Lagrangian relaxation for svm feature selection[END_REF].

In this work, we are proposing a MILP formulation, based on [START_REF] Maldonado | Feature selection for support vector machines via mixed integer linear programming[END_REF] idea to choose the best features and to obtain an adequate predictor. To find an efficient way for solving this model, we exploit the tightening of the bounds on the separating hyperplane coefficients, enabling us to get better times. Exact and heuristic solution approaches are also presented using these improvements. Lastly, the model is validated by comparing the proposed formulation with other models and with other feature selection techniques known in the literature, such as Recursive Feature Elimination (RFE) or the Fisher Criterion Score (F); see [START_REF] Guyon | Gene selection for cancer classification using support vector machines[END_REF] and [START_REF] Guyon | Feature Extraction, Foundations and Applications[END_REF] respectively.

The paper is organized into 8 sections. Section 2 is a revision of various formulations for SVM-based models that are analyzed in the literature. Section 3 presents the model under study. In Section 4, several strategies to fix some of the "big M" parameters of the model are considered. Sections 5 and 6 develop heuristic and exact solution approaches, respectively. Section 7 presents some of the computational results that illustrate the improvement analyzed in the paper. Section 8 is devoted to analyzing the validation of the model presented in the paper. Finally some conclusions are addressed.

Support Vector Machine

Consider a training set Ω partitioned into two classes, each object i ∈ Ω is represented with a pair (x i , y i ) ∈ R n × {-1, 1}, where n is the number of features analyzed over each element of Ω, x i contains the features' values and y i provides the labels, 1 or -1, associated with the two classes in Ω. The SVM determines a hyperplane f (x) = w T • x + b that optimally separates the training examples. In the case of linearly separable data, this hyperplane maximizes the margin between the two data classes, i.e., it maximizes the distances between two parallel hyperplanes supporting some elements of the two classes. Even if the training data is non-linearly separable, the constructed hyperplane also minimizes classification errors. Thus, the classical SVM model minimizes an objective function that is a compromise between the structural risk, given by the inverse of the margin, ω , and the empirical risk, given by the deviation of misclassified objects. Several SVM models have been proposed using different measures of margin and deviation. Among them, the standard 2 -SVM [START_REF] Bradley | Feature selection via concave minimization and support vector machines[END_REF]) uses the following formulation:

( 2 -SVM) min

w,b,ξ

1 2 w 2 2 + C m i=1 ξ i s.t. y i (w T x i + b) ≥ 1 -ξ i , ∀i = 1, . . . , m, (1)
ξ i ≥ 0, ∀i = 1, . . . , m. (2)
As can be observed, 2 -SVM considers 2 -norm to measure the margin and it introduces the slack variables ξ i i = 1, . . . , m to measure the deviations of misclassified elements. Additionally, a penalty parameter C that regulates the trade-off between structural and empirical risk is added. Constraints (1) are the main restrictions appearing in classical SVM. In fact, constraints (1) determine whether or not the training data are separable by the classifier hyperplane. [START_REF] Bradley | Feature selection via concave minimization and support vector machines[END_REF] An equivalent linear formulation of this problem is:

( 1 -SVM) min

w,b,ξ n j=1

z j + C m i=1 ξ i s.t. (1)-(2), -z j ≤ w j ≤ z j , ∀j = 1, . . . , n, (3)
z j ≥ 0, ∀j = 1, . . . , n. (4)
Due to constraints (3), the variables z represent the absolute value of the hyperplane coefficients w.

Often, real data are composed of few sample elements (m), but each element has a large number of related features (n). Therefore, it is essential to select a suitable set of features to construct the classifier. From among the different techniques for feature selection, we focus on the embedded methods that perform feature selection at the same time as the classifier is constructed. Specifically, we focus on the SVM models that include feature selection constraints. [START_REF] Maldonado | Feature selection for support vector machines via mixed integer linear programming[END_REF] proposed a model inspired by the 1 -SVM in which the idea of feature selection was introduced through a budget constraint. Unlike 1 -SVM, the objective function of this model does not consider the margin, i.e., this model focuses on minimizing the sum of the deviations. Although structural risk is not explicitly included in the objective function it is, in some way, implicitly under control because the number of non-null w-variables is bounded by a budget constraint. This model is based on the use of a binary variable linked to each feature in order to restrict the number of attributes used in the classifier via a budget constraint. A cost vector c ∈ R n is considered, where c j is the cost of acquiring attribute j, j = 1, . . . , n. The formulation is therefore given by (MILP1) min

l j v j ≤ w j ≤ u j v j , ∀j = 1, . . . , n, (5)
n j=1 c j v j ≤ B, (6)
v j ∈ {0, 1}, ∀j = 1, . . . , n.

Constraints ( 5) link the v-and w-variables and enable the identification of the w-variables which are non-null, i.e. w j will be non-null only if v j takes value 1 for any j = 1, . . . , n.

In fact, these are big M constraints. Values l j and u j correspond to the lower and upper bounds of the value of w j , j = 1, . . . , n, respectively. As previously mentioned, constraint (6)

is the budget constraint that limits the number of non-null w-variables. Thus, an important issue for solving this model is the appropriate choice of these bounds because the efficiency of any enumeration solution approach will greatly depend on the tightness of the model's LP relaxation.

A possible criticism to this model is that in the case in which, for a particular value of B, there are many optimal solutions with objective value 0, this model does not provide a way to choose among those hyperplanes. This situation is very often in datasets with many features and very few objects. (1)-( 7).

The model

In contrast to MILP1, the presented formulation considers the margin in the objective function. Thus, the problem looks for an optimal balance between deviations and the margin using 1 -norm. In what follows and for the sake of clarity, analogously to Maldonado et al.

(2014), we will assume that c j in ( 6) is set to 1 for j = 1, . . . , n. Therefore, the budget B will represent the maximum number of features that can be selected. An equivalent formulation for this model is obtained by decomposing the unrestricted variables w j as two different non-negative variables, w + j and w - j . In this reformulation, w j = w + j -w - j , where w + j , w - j ≥ 0 for j = 1, . . . , n. Thusly, by taking advantage of this definition, we have that z j = |w j | = w + j + w - j in any optimal solution since w - j + w + j for j = 1, . . . , n is part of the objective function to be minimized. This means that, at most, only one of the two variables is non-zero in the optimal solution. Consequently, the following formulation is obtained,

(FS-SVM) min v,w + ,w -,b,ξ,z n j=1 (w + j + w - j ) + C m i=1 ξ i s.t. y i n j=1 (w + j -w - j )x ij + b ≥ 1 -ξ i , ∀i = 1, . . . , m, (8)
n j=1 v j ≤ B, (9)
w + j ≤ u j v j , ∀j = 1, . . . , n, (10)
w - j ≤ -l j v j , ∀j = 1, . . . , n, (11)
w + j ≥ 0, w - j ≥ 0, ∀j = 1. . . . , n, (12)
ξ i ≥ 0, ∀i = 1, . . . , m, (13)
v j ∈ {0, 1}, ∀j = 1, . . . , n. (14)
Note that the FS-SVM formulation presents a feature selection constraint (9) that limits the number of selected features in order to construct the separating hyperplane. Additionally, constraints (10) and ( 11) are two sets of big M constraints.

A preliminary computational study to check how difficult it is to solve the aforementioned mixed integer linear formulation of FS-SVM with very conservative big M values (u j and l j for all j = 1, . . . , n) shows that formulation's performance is not very good (see the columns FS-SVM of Table 7.2 for the different data sets). This encourages us to check whether a strengthening the big M values might improve these computational results. In the following sections, we will analyze the influence of tightening bounds of the w-variables in this formulation, l and u, to solve the model. In this sense, we will develop different methodologies to obtain better w-variable bounds.

In addition, we have also studied an alternative formulation of FS-SVM by substituing constraints ( 10) and ( 11) by conditional constraints and implementing them by CPLEX command IloIfThen, however we have omitted it because we obtained very bad computational times. Moreover, from this preliminar computational analysis we have checked that the solution times for solving MILP1 and FS-SVM are similar. Only in the cases in which the optimal value of MILP1 is 0, this model is much faster, but in those cases, MILP1 is useless because the data are separable for the chosen features and many separating hyperplanes can be equally valid.

4 Strategies for obtaining tightened values of the w j bounds

As mentioned above and in terms of developing good solution approaches to our problem, it would be useful to provide tightened values of the upper/lower bounds of w j for j = 1, . . . , n.

It should be noted that the literature contains various methods related to bound reduction of w variables in SVM. In particular, two methods are developed in [START_REF] Belotti | Lon handling indicator constraints in mixed integer programming[END_REF]. One of them was the origin of a CPLEX parameter and the other is based on an iterative process that solves auxiliary MIPs to strengthen big M values associated with certain variables. In our preliminary computational analysis we checked this parameter and it did not improve our computational results. In addition, the second approach in [START_REF] Belotti | Lon handling indicator constraints in mixed integer programming[END_REF] consists in an iterative process that solves a sequence of MIPs (two for each w j , j = 1, . . . , n). They applied this approach to data with m = 100 and n = 2, for this reason, they solve four MILPs in each iteration. However for the datasets analyzed in this paper with a large number of features, this approach does not make sense.

For FS-SVM, we develop two strategies to compute the bounds of w j for any j = 1, . . . , n.

The first strategy proposed is based on solving the maximization of linear problems that report the lower/upper bounds of the variables and the second one uses the Lagrangian relaxation to tighten the bounds. Note that, in what follows, we will denote the linear relaxation of FS-SVM as LP-FS-SVM.

Strategy I

Given a subset K ⊂ {1, . . . , n}, we will denote the restricted problem below, which is derived from the original FS-SVM, as FS-SVM(K):

(FS-SVM(K)) min v,w + ,w -,b,ξ j∈K (w + j + w - j ) + C m i=1 ξ i s.t. y i j∈K (w + j -w - j )x ij + b ≥ 1 -ξ i , ∀i = 1, . . . , m, w + j ≤ u j v j , ∀j ∈ K, w - j ≤ -l j v j , ∀j ∈ K, j∈K v j ≤ B, v j ∈ {0, 1}, w + j , w - j ≥ 0 ∀j ∈ K, ξ i ≥ 0, ∀i = 1, . . . , m.
Note that in this problem only a subset of variables v, w + and w -are considered. This is equivalent to considering the FS-SVM where v j = w + j = w - j = 0 for j ∈ {1, . . . , n} \ K. Consequently, the solution to this problem is feasible for the original problem and its objective value, called UB, is an upper bound of our model. Solving FS-SVM(K) will be necessary in the application of Strategy I and it will also be used in the heuristic approach, as we will see in Section 5. The process given by Strategy I is described in Algorithm 1. Result: Updated values of upper bounds parameters l j , u j for j = 1, . . . , n.

/* Step 1 */

For j = 1, . . . , n, let w + j and w - j be an optimal solution for LP-FS-SVM and set K 0 := {j : w + j + w - j > 0}. Solve the restricted problem FS-SVM(K 0 ) to obtain UB. /* Step 2 */ for k = 1 to k = n do Solve the following linear programming problems for k = 1, . . . , n.

(LP) max

v,w + ,w -,b,ξ w + k + w - k s.t. (8)-(13), n j=1 (w + j + w - j ) + C m i=1 ξ i ≤ UB, 0 ≤ v j ≤ 1, ∀j = 1, . . . , n.
Let u k be the optimal value of the above problem.

if u k < max{-l k , u k } then u k := min{u k , u k }, -l k := min{-l k , u k }.
Remark 4.1 Note that the bounds obtained by Algorithm 1 can be improved by substituting constraint (9) in the (LP) for any k = 1, . . . , n for j =k v j ≤ B -1. However, the computational analysis addressed in a preliminary study showed that the improvement in quality of the bounds is very small and the running times increased when using this modification. For this reason, we decided to keep constraint (9) and not use this modification.

Strategy II

Unlike the previous strategy in which bounds for w + j + w - j have been computed, this strategy will provide us with bounds for w + j and w - j independently. In this case, the strategy is based on the results below.

Theorem 4.1 Let (v, w + , w -, b, ξ) be an optimal solution of LP-FS-SVM; z LP LB its objective value; α a vector of optimal values for the dual variables associated with the constraints (8); and w + j 0 + w - j 0 = 0 for some j 0 ∈ {1, . . . , n}.

i) If (ṽ, w+ , w-, b, ξ) is an optimal solution of LP-FS-SVM restricting w + j 0 = w+ j 0 where w+ j 0 is a positive constant, z w+ j 0 its objective value and n j=1 v j +

w+ j 0 u j 0 ≤ B, then z LP LB + w+ j 0 (1 - m i=1 α i y i x ij 0 ) ≤ z w+ j 0
.

ii) If (ṽ, w+ , w-, b, ξ) is an optimal solution of LP-FS-SVM restricting w - j 0 = wj 0 with wj 0 a positive constant, z w- j 0 its objective value and n j=1 v j + w-

j 0 -l j 0 ≤ B, then z LP LB + w- j 0 (1 + m i=1 α i y i x ij 0 ) ≤ z w- j 0
.

Proof:

We are only addressing statement i) here because statement ii) would be proved in a similar manner. Since α is a vector of optimal values for the dual variables associated with the family of constraints (8), it holds that

z LP LB = n j=1 (w + j + w - j ) + C m i=1 ξ i + m i=1 α i   1 -ξ i -y i n j=1 (w + j -w - j )x ij -y i b   .
In addition, since w + j 0 + w - j 0 = 0, we have that

z LP LB = n j=1,j =j 0 (w + j + w - j ) + C m i=1 ξ i + m i=1 α i   1 -ξ i -y i n j=1,j =j 0 (w + j -w - j )x ij -y i b   . ( 15
)
On the other hand, consider the LP-FS-SVM with the additional constraints w + j 0 = w+ j 0 ,

v j 0 = w+ j 0 u j 0
and where the family of constraints (8) has been dualized, i.e., min v,w + ,w -,b,ξ n j=1

(w + j + w - j ) + C m i=1 ξ i + m i=1 α i   1 -ξ i -y i n j=1 (w + j -w - j )x ij -y i b   s.t.
(9)-( 13),

w + j 0 -w - j 0 = w+ j 0 , 0 ≤ v j ≤ 1, j = 1, . . . , n,
where α i ≥ 0. Hence, this problem can be rewritten as follows, (Lag-FS-SVM) min

v,w + ,w -,b,ξ n j=1,j =j 0 (w + j + w - j ) + C m i=1 ξ i + m i=1 α i (1 -ξ i - -y i n j=1,j =j 0 (w + j -w - j )x ij - m i=1 y i b) + w+ j 0 (1 - m i=1 α i y i x ij 0 ) s.t. n j=1,j =j 0 v j ≤ B - w+ j 0 u j 0 ,
w + j ≤ u j v j , j = 1, . . . , n, j = j 0 , w - j ≤ -l j v j , j = 1, . . . , n, j = j 0 , w + j , w - j ≥ 0, j = 1, . . . , n, j = j 0 , 0 ≤ v j ≤ 1, j = 1, . . . , n, j = j 0 , ξ i ≥ 0, i = 1, . . . , m.

Note that (v, w + , w -, b, ξ), an optimal solution of LP-FS-SVM, is feasible for the problem above if wj 0 ≤ u j 0 (B -n j=1 vj ). In addition, any feasible solution of the problem Lag-FS-SVM taking w + j 0 = w - j 0 = v j 0 = 0 is feasible for the LP-FS-SVM where family of constraints (8) has been dualized.

Hence, for α = α, using (15), the optimal objective value of the above problem is z LP LB + w+ j 0 (1 -m i=1 α i y i x ij 0 ), which is the lower bound of the optimal value of the LP-FS-SVM with the additional constraint of w + j 0 = w+ j 0 .

Corollary 4.1 Under the hypothesis of Theorem 4.1, if we have an upper bound UB of FS-SVM, then it holds that i) w + j 0 ≤ min

UB-z LP LB 1-m i=1 α i y i x ij 0 , u j 0 (B -n j=1 v j ) . ii) w - j 0 ≤ min UB-z LP LB 1+ m i=1 α i y i x ij 0 , -l j 0 (B -n j=1 v j ) .
A detailed description of this second strategy can be found in Algorithm 2. Result: Tightened bounds of u and l.

/* Step 1 */

Solve the LP-FS-SVM and obtain the dual variables (denoted by α i ) associated with the family of constraints (8). Let z LP LB be its optimal value and (v, w a , w -, b, ξ

) ∈ R n + × R n + × R n + × R × R m + an optimal solution. /* Step 2 */
Let UB be an upper bound of our original model (recall that an upper bound was computed in Strategy I). If

w + j0 + w - j0 = 0, Set u + j0 := min UB-z LP LB 1-m i=1 α i y i x ij 0 , u j0 (B -n j=1 v j ) , if u + j0 < u j0 then u j0 := u + j0 . Set u - j0 := min UB-z LP LB 1+ m i=1 α i y i x ij 0 , -l j0 (B -n j=1 v j ) , if u - j0 < -l j0 then -l j0 := u - j0 .
5 Heuristic Solution Approach: Kernel Search

Among the characteristics of the presented model, we must point out that each data feature (j) has an associated binary variable (v j ) which indicates whether or not feature j is selected to construct the classifier. Therefore, the size of the problem, and consequently the time required for solving it, grows with the number of features. SVM usually works with real data using quite a large number of features. Hence, a heuristic approach that is suited to the model will help us to very quickly find appropriate, good solutions for those cases where exact methods cannot provide solutions within an acceptable time.

Specifically, we adapt the Kernel Search (KS) proposed by [START_REF] Angelelli | Kernel search: A general heuristic for the multi-dimensional knapsack problem[END_REF]. The basic idea of this heuristic approach is to solve a sequence of restricted MILPs derived from the original problem, thus obtaining a progressively better bound on the solution. The KS has been successfully applied to different kinds of problems such as portfolio optimization [START_REF] Angelelli | Kernel search: A new heuristic framework for portfolio selection[END_REF]) and location problems [START_REF] Guastaroba | Kernel search for the capacitated facility location problem[END_REF]). Even though it was originally applied to pure binary formulations, it has been also used in problems with several continuous or integer variables associated with each binary variable.

Regarding our model, we observed that the continuous variables w + j and w - j are related to the binary variables v j by constraints (10) and (11). By applying this heuristic approach to our problem, we will solve a sequence of MILP problems with the same structure as the original one but only considering a subset of variables v and the corresponding subset of continuous variables ω + and ω -which are associated with it. Since restricted MILPs only take into account a subset of v variables, i.e. the remaining v variables are fixed to 0, they will hopefully provide upper bounds in acceptable times.

In the KS, each restricted MILP of the sequence considers the variables that are most likely to take a value different from 0 in the optimal solution of the original problem. These variables are called promising variables and they form the Kernel set of each restricted MILP.

Detailed below is the complete KS procedure for our SVM model, including how to select the promising variables at each step and how to modify the Kernel.

Initial step

First, feature set {1, . . . , n} must be sorted according to how much the corresponding variables are likely to take a value of 1 in the optimal solution. The LP-FS-SVM is solved with this aim in mind, obtaining a solution (v, ω+ , ω-, b, ξ) and the reduced costs of variables ω + j and ω - j for each j = 1, . . . , n. Then, features are sorted in non-decreasing order with respect to vector r, which is defined as:

r j =    -(ω + j + ω- j ), if ω+ j + ω- j > 0, min{r + j , r - j }, otherwise. (16)
Where, r + j and r - j are the reduced costs of variables ω + j and ω - j in the LP-FS-SVM, for j = 1, . . . , n.

To obtain the initial Kernel set (K 0 ), the first k features are chosen, having been sorted into a non-decreasing order with respect to vector r. Specifically, we take

k := j = 1, . . . , n : ω+ j + ω- j > 0 ,
although k is a parameter of the heuristic that can be modified.

Similar to [START_REF] Guastaroba | Kernel search for the capacitated facility location problem[END_REF], the remaining features are divided into N subsets denoted as K i for i = 1, . . . , N . In particular, we take N = n-k k . Each subset K i , i = 1, . . . , N -1 will be composed of k features and K N will contain the remaining features.

In fact, we restrict the KS to analyze only N < N of the subsets, due to the size of the instances considered. Computational experiments have shown results when exploring 10% of the total number of subsets, i.e., N := 0.1 • N .

Given the initial Kernel K 0 , the upper bound (UB) of the problem is initialized by solving FS-SVM(K 0 ). Note that, as observed in Section 4, FS-SVM(K 0 ) is equivalent to solving the original problem setting v j = 0 for j / ∈ K 0 . We should point out that any solution of FS-SVM(K 0 ) is always a feasible solution for FS-SVM, thus solving FS-SVM(K 0 ) we obtain an upper bound.

Main step

In each iteration (it), the heuristic considers the set of features K = K ∪ K it , i.e. the combination of the current Kernel and the features in the set K it . To update the UB, in each iteration FS-SVM(K) is solved plus the following two constraints, as denoted by FS-SVM(K)+( 17)+(18),

j∈K (w + j + w - j ) + C m i=1 ξ i ≤ U B, (17)
j∈K it v j ≥ 1. ( 18
)
Constraint ( 17) restricts the objective function to take a value smaller than or equal to the current upper bound and constraint ( 18) ensures that at least one feature belonging to K it will be chosen. We also impose the restriction that each problem has to be solved within a time limit of 900 seconds. If no feasible solution can be found within this time limit, the algorithm skips to the next iteration. Note that this problem may potentially be infeasible due to the presence of constraints ( 17) and ( 18) together in the formulation. Otherwise, if FS-SVM(K)+( 17)+( 18) is feasible, the objective value, at least, will be equal to the previous UB because of constraint (17).

Update step

If the problem FS-SVM(K)+( 17)+(18) (i.e., FS-SVM(K) where constraints ( 17) and ( 18)

have been added) is feasible, then some features from K it are chosen in the optimal solution of FS-SVM(K)+( 17)+(18). They are added to the current Kernel K for the next iteration since adding these features obtains an identical or better upper bound. Conversely, the set of features of K that has not been chosen in the optimal solution in the previous iterations is removed from the Kernel. The removal of some of the features from the Kernel is decisive in that it does not excessively increase the number of binary variables considered in each FS-SVM(K)+( 17)+(18). In our case, we remove the features that were not selected in the previous two iterations. The set of added features is denoted as K + it and the set of removed features as K - it . The resulting Kernel for the next iteration is

K = K ∪ K + it \ K - it .
Coversely, if the problem is infeasible, the kernel is not modified and the procedure skips to the next iteration. The KS for the FS-SVM model is also described in Algorithm 3. Parameter k is initially fixed as described in Subsection 5.1.

Result: A feasible solution of FS-SVM model.

/* Initial

Step */

Solve LP-FS-SVM. Sort the n features in non-decreasing order with respect to vector r defined in ( 16).

Build the initial kernel K 0 taking the first k ordered features. Set K = K 0 .

Divide the remaining n -k sorted features in a sequence of N subsets (K 1 , . . . , K N ).

Select the number of subsets to analyze, N , ( N < N ).

Solve the FS-SVM(K) obtaining the initial upper bound (UB).

for it = 0 to it = N do /* Main Step */ Build K = K ∪ K it .
Solve FS-SVM(K)+( 17)+( 18).

/* Update Step */ if FS-SVM(K) is feasible (with solution (v, ω+ , ω-, b, ξ
) and optimal value z) and the running time is smaller than 900 s then

U B = z Build K + it := {j ∈ K it : vj = 1}. Build K - it := {j ∈ K : j not selected in the solution of the last two iterations}. Update K := K ∪ K + it \ K - it . Set it := it + 1.

Exact procedure

This section is devoted to the description of a procedure to get an FS-SVM optimal solution by solving a sequence of semi-relaxed problems. In this exact procedure, each semi-relaxed problem is associated with a subset K ⊂ {1, . . . , n} of features in such a way that only the variables v j with j ∈ K will be considered as binary and the remaining ones will be relaxed.

Specifically, the semi-relaxed version of the problem for a set of features K is formulated as follows,

(SR-FS-SVM(K)) min v,wa,w b ,b,ξ n j=1 (w + j + w - j ) + C m i=1 ξ i s.t. (8)-(13), v j ∈ {0, 1}, ∀j ∈ K, ( 19
) 0 ≤ v j ≤ 1, ∀j ∈ {1, . . . , n} \ K. ( 20
)
The optimal value of SR-FS-SVM(K) provides a lower bound of FS-SVM. By adding and removing certain features of K, a sequence of semi-relaxed problems is created, providing lower bounds on the solutions. As we will see in the following subsections, strategies I, II and the Kernel Search are also used in this procedure.

Initial Step

To obtain initial bounds on the objective value, the exact procedure exploits techniques detailed previously. First, strategies I and II are used to tighten parameters u and l. It should be noted that the use of these strategies provide an initial upper bound (UB) and an initial lower bound (LB) for the objective value (by solving the linear relaxation). The Kernel Search is then performed in order to improve the UB given by the strategies.

Main Step

The main step of the exact procedure consists of solving a sequence of semi-relaxed problems to improve the lower bound of the objective value. To start with, we must select a subset of features K ⊂ {1, . . . , n} whose associated v variables will be considered as binary variables in the first semi-relaxed problem. The Kernel Search provides a subset of features that allows us to obtain a good bound on the optimal objective value. Therefore, the exact procedure will consider the set provided by the heuristic as the initial K and it will obtain an initial LB solving SR-FS-SVM(K).

Then, the set K is updated by adding and removing some of the features, improving the bound of the objective value. To this end, two sets (denoted by K + and K -) are built in each iteration. Set K + consists of some of the features in {1, . . . , n} \ K whose associated v variables will be considered as binary in the next iteration, i.e. features of K + will be added to K. Similarly, K -consists of features in K that will not be considered as binary in the next iteration. In addition and if possible, we will update the UB in the main step.

A general outline of the exact procedure is shown in Algorithm 4. Since the set K can be modified using different rules to improve the lower bounds, we have provided three different update variants of this procedure in Algorithms 4.1, 4.2 and 4.3. In Variant I (Algorithm 4.1), the set K is updated by adding the features using vector r, sorted in non-decreasing order as described in the previous section. This ordered sequence of v-variables is based on the idea that the features with the biggest reduced costs of variables w + j and w - j are less likely to be different from 0 in the optimal solution of FS-SVM and those features with a positive value in the LP are the most likely to be different from 0. Let K be the final set obtained using the Kernel Search. Take it := 0.

while U B-LB U B
• 100 ≤ 0.01 do Solve SR-FS-SVM(K). Let (v, w a , w b , b, ξ) be its solution, z LB its objective value.

if running time of FS-SVM(K) > 1800s then break Let ṽj be the optimal values of variables v j with j ∈ K of SR-FS-SVM(K). Solve the FS-SVM fixing v j = 0 ∀j ∈ {1, . . . , n} \ K and v j = ṽj ∀j ∈ K. Let z U B be its objective value.

if z U B < U B then U B := z U B . if z LB > LB then LB := z LB . /* Update Step */
Build K -, composed by the features in K that will be relaxed in the next iteration.

Build K + , composed by the features in {1, . . . , n} \ K that will be added to K in the next iteration.

Update

K := K ∪ K + \ K -. it := it + 1
In contrast, in Variant II (Algorithm 4.2) the set K is increased in each iteration by adding features j ∈ {1, . . . , n} \ K that take a value bigger than 0 in the SR-FS-SVM(K).

Lastly, in Variant III (Algorithm 4.3) the set K is modified based on the reduced costs of the resulting linear programming problem after fixing the binary variables of SR-FS-SVM(K) to their optimal values. We thus obtain the reduced costs of variables w + and w -, and a vector similar to r is created. In this case, we have denoted it as r and it is defined as:

r j :=    -(ω + j + ω- j ) if ω+ j + ω- j > 0, min{r + j , r - j } otherwise. ( 21
)
where ω+ , ω-, r + and r -are the solutions and reduced costs of the problem described above.

r is sorted in non-decreasing order and K is updated by adding the features in this order.

A set of n < n features are added in each iteration. In particular we take n = 20 since it provides good results. Additionally, variables that are null in two consecutive iterations are relaxed.

Using these variants, we explore different forms to improve the lower bounds and to update the initial set of binary variables. The various performances of the described procedures are analyzed in Section 7. Sort the features j ∈ K := {1, . . . , n} \ K according to vector r defined in (16).

Divide K in a sequence of subsets (K 1 , K 2 , . . .) of a certain size S, considering the order given by r.

/* Update Step: Variant I */ Sort K := {1, . . . , n} \ K in non-decreasing according to the values of r vector in (21).

Build K + := K it . Update K := K ∪ K + . Algorithm 4.2: Update Variant II /* Update Step: Variant II */ K + := {j ∈ K|v j > 0}. Update K := K ∪ K + and K := {1, . . . , n} \ K.
Construct the set K + selecting the first n < n features of the ordered set K. In particular, we take n := 20.

Update

K := K ∪ K + \ K -.

Computational Results

In this section, we present the results provided by several computational experiments. In particular: i) how the use of Strategies I and II for fixing the upper and lower bounds of w variables can reduce the computing times for our model; ii) the efficiency of the heuristic approach (Kernel Search) proposed in this paper; and lastly, iii) the study of the results provided by the different variants of the exact solution approaches.

It should be noted that the various computational experiments were performed using CPLEX 12.6.3 on an Intel(R) Core(TM) i7-4790K CPU 32 GB RAM computer. We should also remark that we disabled some CPLEX features for all computational experiments in order to give a clean comparison of the relative performance of the formulations. Specifically, we turned off CutPass, CutsFactor, EachCutLim and FracCuts parameters to avoid cuts generation. Besides, we disabled the internal CPLEX heuristic given by RinsHeur parameter and we turned off presolve during preprocessing using PreInd parameter. Finally, we established an integrality tolerance of 0 using EpInt parameter and a feasibility tolerance of 1e-9 with EpRHS parameter. The computational experiments were carried out on sixteen different datasets. Eight of them can be found in the UCI repository [START_REF] Asuncion | UCI machine learning repository[END_REF]), (see Since the resolution times for the datasets in Table 7.1a and Lepiota dataset are really good when solving the formulation with CPLEX (a few seconds), in this section we focus our attention of developing alternative solution strategies to the instances with the largest number of features (different from Lepiota). In Subsection 7.1, we will analyze the instances with a big number of features and a small sample size (Colon, Leukemia, DLBCL, Carcinoma).

Lastly, we will apply the best obtained techniques to the instances with a big sample size in Subsection 7.2.

Analysis of datasets with small sample size and big number of features

In this subsection we will analyze how the use of strategies I and II can affect Colon, Leukemia, DLBCL and Carcinoma datasets. The heuristic and exact procedures applied to these datasets are also studied in this subsection.

FS-SVM with Strategies I and II

Section 4 described two strategies for obtaining tightened bounds on parameters u and l. Table 7.2 reports the computational results of the proposed formulation, both with and without

Strategies I and II. We used small values of B ∈ {10, 20, 30}, C ∈ {2 -7 , 2 -6 , 2 -5 , 2 -4 , 2 -3 , 2 -1 , 1, 2, 2 2 , 2 4 , 2 5 , 2 6 , 2 7 } and a time limit of two hours (instances exceeding the time limit have been highlighted with their times underlined). However, since the running times are very short for small values of C and the variables w result to be null in most cases, we have only reported the results for C ∈ {1, 2, 2 2 , 2 4 , 2 5 , 2 6 , 2 7 }. In this Table, the column labelled "FS-SVM" shows the gaps and running times of the proposed model. The second group of columns for each dataset, titled "St.+FS-SVM", shows the results associated with the model after strategies I and II have been applied for obtaining tightened lower/upper bounds of w-variables. The termination gap (%) is shown in the "Gap" column, whilst the "t st " column gives the time required for the two strategies, t solv is the running time for solving the formulation once the parameters defining the bounds of w have been fixed and t total is the overall process time.

Lastly, column ∆B = 1 n n j=1 (u j -l j ) shows the average difference between the upper and lower bounds after the use of both strategies. Note that initially u j = -l j takes a large enough amount. Generally, it can be seen that the use of the strategies provides an average difference between both bounds of less than 5.57 units. Therefore, Strategies I and II provide tightened bounds.

For the Colon dataset, FS-SVM cannot be solved for B = 20, C ≥ 2 and B = 10, C ≥ 2 0 within the time limit. However, if Strategies I and II are employed before solving the model, FS-SVM can be solved in less than 30 minutes for all cases when B = 20. For B = 10 and C ≥ 2, the model cannot be solved in less than two hours, even if the strategies are performed, but the gaps at termination are smaller.

The second group of columns of Table 7.2 shows the results for the Leukemia dataset. In this instance, the model with the strategies solves the same cases as the model without the strategies. However, most of the cases that cannot be solved in less than two hours present smaller gaps if the strategies are used. Table 7.2, also details the results for the DLBCL dataset. For B = 20 and C ≥ 2 3 , this instance was not solved within the time limit, but when using the strategies it can be solved in less than approximately 19 minutes. However, the model in which B = 10 and C ≥ 1 cannot be solved, even if u and l are tightened with the strategies, although the gaps are once again better than when the strategies are not utilized.

The last group of columns shows the results of the Carcinoma dataset. In this case, the model cannot be solved in less than two hours for B = 10. However, if we use both strategies, the solution times improve and only two cases (with parameters C = 2 1 , 2 2 ) remained unsolved after the time limit.

Regarding the reported results, we can conclude that the use of Strategies I and II leads to a reduction in running times in most cases. Furthermore, although the model cannot be solved for certain parameters values (even with the use of the strategies), the termination gaps are better if Strategies I and II are employed. gap (%) between the solution provided by the KS and the optimal solution obtained by the FS-SVM formulation (note that for B = 20, 30 the formulation was run until the optimal solution was found and for B = 10 we ran the formulation until a gap of less than 10% was achieved). For cases where the optimal solutions were not found, this column shows, both the gap between the best lower bound and the KS solution, as well as the gap between the best feasible solution and the KS solution. These two gaps are separated by "/". Furthermore, the columns labelled "t KS " represent the running time of the KS. Lastly, in "t Best " columns we can observe the best time for solving the problems. In those instances that were not solved within two hours, we reported the total time of the solution method (FS-SVM, St+FS-SVM or St+FS-SVM * ) that provides the best gap (recall that St+FS-SVM * corresponds to the results of FS-SVM using Strategies I and II, establishing a time limit of two hours and using the Kernel Search solution as the initial solution for the model, see Table 7.4). Shown in superscript is the gap obtained after the time limit was reached.

Heuristic procedure

In general, Table 7.3 demonstrates that the Kernel Search provides, in much less time, the optimal solution for all those instances that we were able to solve exactly in less than two hours. In the remaining cases, we provided better upper bounds than the exact approaches, again in much less time.

Due to these good results in terms of gaps, this heuristic may also be useful in reducing the computational times of the formulation. Table 7.4 shows a comparison of the gaps and times between the model that uses the KS solution as an initial feasible solution of the problem (column St.+FS-SVM * ) and the results reported in Table 7.2. In general, we can observe a reduction of computational times and an improvement of the gaps in the problems that could not be solved within 7200 seconds. In each case, the best times and gaps are shown in bold.

Additionally, figures 7.4 show the best improvements that are achieved using the KS solution.

Exact procedure

Table 7.5 reports the termination gaps and running times of the different procedure variants.

The first two-column block, St+FS-SVM * , is taken from Table 7.4. The following three blocks of two columns show the gaps and times of the exact procedure using Variant I with the different values of parameter S described in Algorithm 4.1. Columns with an asterisk symbol "*" indicate that, for each iteration, we added a constraint to restrict the objective value to greater than or equal to the best lower bound known so far and it also means that the KS solution was used as the initial solution for SR-FS-SVM(K). To finish, the last two columns show the results of Variants II and III as described in Algorithms 4.2 and 4.3, respectively.

The stopping rule for the exact procedure, was for the gap between the upper and lower bounds to be smaller than 0.01% or if the resolution of the semi-relaxed problem took more than 1800 seconds. Moreover, if the bound did not improve in 5 iterations, the procedure was terminated. We used B = 10 and C ∈ {1, 2, 2 2 , 2 3 , 2 4 , 2 5 , 2 6 , 2 7 } since the formulation could not be solved within the time limit using these parameter values.

In the case of the Colon dataset, Table 7.5 shows that Variant I with S = 20 reports the best rates between the upper and lower bounds of the objective values. However, the best running times are provided by Variant III. We can observe that the fastest procedure for the Leukemia dataset is also Variant III. Additionally, Variant II is the one that provides the best gaps for said dataset. In the case of the DLBCL dataset, Table 7.5 shows that Variant I (taking S = 20 and using the Kernel result as the initial solution) together with Variant II results in the best gaps. The best running times for the DLBCL dataset are also the ones obtained using Variant III. Lastly, in the Carcinoma dataset, we can observe that the exact procedure does not provide better results than the ones obtained by the formulation. In spite of that, we observed that when using Variant III, we get gaps smaller than 3% in less than 2300 seconds.

In general, these results show that exact procedures are useful for the cases in which the formulation (together with the two strategies for fixing the bounds of w variables) is not able to find the optimal solution within the time limit. In those cases, the gaps reported by almost all variants are smaller than the ones given by the formulation and they take less time.

Analysis of datasets with big sample sizes and big number of features

In this subsection we will focus on the datasets with big sample size and big number of features (Arrythmia, Madelon and MFeat datasets). Table 7.6 reports four blocks of columns with some of the techniques described in the previous subsection. For each dataset, the blocks of columns FS-SVM and St+FS-SVM* are defined similarly to Table 7.4, the Kernel block reports the results of Kernel Search algorithm. Besides, we include ∆B column like in Table 7.2. Finally, the last block of columns report the results of exact procedure V. I (S=20)* (see Table 7.5).

If we focus our attention on the Arrythmia dataset, we observe that none of the instances can be solved either using the strategies or not. However, the final gaps when using the strategies are smaller than the ones without the strategies. A similar behaviour can be appreciated in Madelon dataset. However, for the MFeat dataset we observe that the instances can be solved in less than two hours if strategies and Kernel are applied. In ∆B column of MFeat dataset, we can observe that the bounds of w variables are very tightened when using the strategies.

Regarding the Kernel Search results, we observe that, in almost all the cases, the solution provided by the heuristic gives the same final gap as the formulation in smaller times. For this reason, we can conclude that the upper bound provided by the Kernel Search is quite good because it cannot be improved.

The last block of columns of Table 7.6 reports the results of exact procedure Variant I (S=20)*. We have chosen this variant because it seems that it provides the best gaps in Table 7.5. For Arrythmia and Madelon datasets, in most of the cases, the gaps provided by this exact procedure are better than the final gaps of the model using the strategies. In the MFeat dataset although the gaps have not improved these are very small. Moreover, some instances provide better running times.

Validation of the model

In this section, the proposed model is analyzed together with other classification approaches.

To this end, a 10-fold-cross validation (10-FCV) was performed for the datasets described above. We compare our model not only with classical SVM such as 1 -SVM [START_REF] Bradley | Feature selection via concave minimization and support vector machines[END_REF]), 2 -SVM [START_REF] Vapnik | Statistical Learning theory[END_REF]) and LP-SVM [START_REF] Zhou | Linear programming support vector machines[END_REF]), but also with recent SVM that include feature selection constraints, such as MILP1 described in Section 2 and MILP2 (an extension of LP-SVM developed by [START_REF] Zhou | Linear programming support vector machines[END_REF] with feature selection through a budget constraint), see [START_REF] Maldonado | Feature selection for support vector machines via mixed integer linear programming[END_REF]. Furthermore, the following classification techniques are also analyzed and compared with our model: FSV [START_REF] Bradley | Feature selection via concave minimization and support vector machines[END_REF]), RFE-SVM [START_REF] Guyon | Gene selection for cancer classification using support vector machines[END_REF]) and Fisher Criterion Score [START_REF] Guyon | Feature Extraction, Foundations and Applications[END_REF]), referred to as Fisher-SVM,

We compute two different predictive performance measures: the accuracy (ACC) and the area under the curve (AUC). The ACC is given by the percentage of good classified elements of the test set. However, the AUC is the mean of the percentage of good classified positive elements and the percentage of good classified negative elements. Hence,

ACC = T P + T N T P + T N + F P + F N , AU C = T P T P +F N + T N T N +F P 2 ,
where TP are true positives, TN are true negatives, FP false positives and FN false negatives.

The different models are compared using these two measures. We should point out that each model has different parameters and we chose the parameters with the best performance in each model. In fact, the penalty parameter C, which is necessary for the MILP2 and FS-SVM models, is varied in the set

{2 -7 , 2 -6 , 2 -5 , 2 -4 , 2 -3 , 2 -2 , 2 -1 , 2 0 , 2 1 , 2 2 , 2 3 , 2 4 , 2 5 , 2 6 , 2 7 }.
Moreover, the upper bounds on the variables related to the MILP1 and MILP2 models are fixed to a sufficiently large amount. The budget parameter (B) is varied, as shall be explained in the following subsections.

To select the best parameters for a model, 10-FCV is performed with each possible combination of parameter values. For each parameter value and each fold of 10-FCV, we obtain an ACC and AUC measure value. After the application of 10-FCV to this parameter combination, we obtain an average of the measures associated with each fold. We repeat this process for the remaining parameter combinations and then compare the average performance measures. Lastly, we indicate the average measures associated with the parameters that provide best results for each instance.

In Subsection 8.1, the eight datasets with the smallest number of features will be analyzed.

Subsection 8.2 will address the Colon, Leukemia, DLBCL and Carcinoma datasets. Finally, Subsection 8.3 will be focused on the remaining datasets that present big sample sizes and big number of features.

In addition, we include a deeper comparison of the proposed model with 1 -SVM in the Appendix. In this case, the analyzed datasets are Ionosphere, Colon, Arrythmia and Madelon.

Instances with a small number of features

This subsection concerns the comparative analysis of different classification techniques and our model for the following datasets: BUPA, PIMA, Cleveland, Housing, Australian Credit, German Credit, WBC and Ionosphere. The number of features in all these datasets is below 50. Therefore, the budget parameter (B) varies with all the possible numbers of features, i.e.

B = 1, . . . , n.

The first column of Tables 8.1-8.8 specifies the classification method used. For each method, we have provided the best average ACC achieved in the 10-FCV (column ACC)

and the parameters used to obtain this ACC (columns B and C). Using these parameters, column AUC reports the average AUC value. The fourth column gives the average number of selected features in the 10-FCV. Note that features are considered if their associated absolute value in the optimal solution is at least = 10 -2 . Lastly, the last column, labelled "Time", details the average time that is required to run a single fold of the 10-FCV. It should be pointed out that the last two rows of each table correspond to our formulation (FS-SVM)

and the Kernel Search (KS FS-SVM). The model with best performance for each dataset is shown in bold.

Furthermore, figures 8.1-8.8 show the ACC performance of different models that include feature selection in terms of parameter B. We should emphasize that parameter B represents the maximum number of features that can be selected in the model. Note that the results

shown in these graphs are the average ACC of 10-FCV corresponding to the C values reported in the corresponding Tables 8.1-8.8.

For the BUPA dataset (Table 8.1), the best performance is achieved using FS-SVM together with 1 -SVM. Figure 8.1 reveals that MILP2 and FS-SVM are the models that provide the best performances for the different B values. In the case of the PIMA dataset (Table 8.2), the best performance in terms of ACC is also obtained using our model together with 1 -SVM, while the best performance in terms of AUC is achieved by RFE-SVM. Figure 8.2 shows that the best ACC performance in general terms is obtained using the proposed FS-SVM model.

In Table 8.3, the best performance for the Cleveland dataset is reported by the RFE-SVM method. Additionally, Figure 8.3 shows that MILP1, MILP2 and FS-SVM present the best average ACC when varying the B parameter. In the case of the Housing dataset (Table 8.4), we can observe that RFE-SVM provides the best average ACC and AUC. FS-SVM also shows similar values but with half the number of features. In Figure 8.4, we can conclude that our approach for B ≤ 7 is among the best ones, together with MILP2.

Table 8.5 shows the results for the Australian Credit dataset. In this case, all the models present a similar ACC and AUC performance. Although the results in bold are those related with the Fisher-SVM technique, Figure 8.5 however, shows that Fisher-SVM performs worse than other models when the budget parameter has a lower value (B = 1, . . . , 4). Therefore, there is no significant difference between the models.

For the German Credit dataset, the best ACC performance is given by MILP1 and the best AUC performance is produced by Fisher-SVM, as shown in Table 8.6. Figure 8.6 shows that the best ACC is achieved with models MILP1, MILP2 and FS-SVM. The best performance for the WBC dataset is obtained with the 2 -SVM model. However, 30 features are required to achieve these results. Our model also provides good results when using only 4 of the 30 features. In Figure 8.7, the overall best results are obtained with the MILP2 and FS-SVM models, using different B values.

The dataset with the biggest number of features among the smallest instances (the Ionosphere dataset) performs best when using FS-SVM, as can be seen in Table 8.8. Figure 8.8 also shows that all the models provide an ACC performance between 82% and 88%. In general, FS-SVM always has the best performance or else is among the best performers.

In terms of these datasets, we can conclude that the proposed model (FS-SVM) produces, in general terms, a good and stable performance, improving, in some cases, the existing approaches in the literature.

Instances with small sample size and big number of features

This subsection is focused on Colon, Leukemia, DLBCL and Carcinoma datasets. Tables 8.9-8.12 do not include the results of MILP2 due to the huge times to solve this model for big instances. Since the KS provides good approximations of the solutions for our model within short time, we will only use the KS to analyze FS-SVM performance for most of the datasets. In addition, the performance of ACC is illustrated in Figures 8.9-8.12 in which B varies betweeen 10 and 100 for the C values shown in Tables 8.9-8.12.

The results for the Colon dataset are indicated in Table 8.9. We observe that the best performance are given by RFE-SVM and FS-SVM. Moreover, Figure 8.9 shows that FS-SVM achieves stable results with all the possible values of B. In fact, RFE-SVM, Fisher-SVM and FS-SVM present similar performances. For the Leukemia dataset, the best performance is achieved in 2 -SVM, but FS-SVM also attains a good performance using only 30 features in contrast with the 5327 used by 2 -SVM.

Besides, Figure 8.10 shows that KS FS-SVM provides the best performance. For the DLBCL dataset, we obtain similar results to the Leukemia case and the results are shown in Table 8.11 and Figure 8.11. The best performances in this case are achieved by the 1 -SVM, the RFE-SVM and KS FS-SVM models.

Lastly, for the Carcinoma dataset, we can see that the best average ACC and AUC are obtained with 2 -SVM, Fisher-SVM and RFE-SVM. In addition, Figure 8.12 shows that KS FS-SVM, Fisher-SVM and RFE-SVM provide good results for all studied B values.

To summarize, the performances of the different models in these four datasets show that our model provides results which are better than MILP1 models and that it attains similar results to RFE-SVM. Regarding these results, we can therefore conclude that our model is a good classifier for big instances where a small number of features must be selected. In the case of the Arrythmia dataset, 1 -SVM needs, in most of the cases, more than 100 features to obtain the reported performance (note that a value of 0.01 is used as tolerance).

Instances with big sample size and big number of features

However, FS-SVM never uses more than 40 features in any of the cases. Similarly, in the Madelon dataset the number of features is greater than 300 for 1 -SVM and smaller than 100

for FS-SVM.

Finally, Table A.1 reports in average the running times of each formulation and the percentage of selected features in FS-SVM that are also chosen in 1 -SVM model. For instance, a 100% means that the selected features of FS-SVM are a subset of the features used by 1 -SVM. In general, we can see a high percentage of overlap between the chosen features of both models.

If we compare the running times associated with each In summary, from a practical or applied perspective, feature selection can be decisive since there can be certain economic restrictions that make difficult the extraction of the data related to all the features. In consequence, the results of the presented model are significant in that it allows us to obtain good ACC and AUC performance using a small and fixed beforehand number of features. In contrast, when using 1 -SVM, it is not possible to set in advance the maximum number of features that can be selected.

  also presented the same model but considering 1 -norm instead of 2 -norm for the margin. The resulting model is the following,

  Based on the idea introduced by[START_REF] Maldonado | Feature selection for support vector machines via mixed integer linear programming[END_REF], we propose the extension of 1 -SVM with a budget constraint, i.e., our model takes into account the structural and empirical risk in the objective function with feature selection through a budget constraint, therefore we avoid the above mentioned criticism of MILP1.[START_REF] Maldonado | Feature selection for support vector machines via mixed integer linear programming[END_REF] were mainly focused on validating their model by contrasting it against well-known classification methods from the literature, but little attention was paid to analyze how to solve their problem efficiently. However, our goal in this paper is to provide a deep analysis of the model, allowing us to produce efficient exact and heuristic solution approaches in addition to validating the model by comparing it with classical classification methods. Hence the model that we propose is

Algorithm 1 :

 1 Strategy I Data: Training sample composed by a set of m elements with n features.

Algorithm 2 :

 2 Strategy II Data: Training data (m elements × n features).

Algorithm 3 :

 3 Kernel Search for FS-SVM Data: Training data composed by a set of m elements with n features.

  Algorithm 4.1: Update Variant I. /* Modified Main Step: Variant I */

  Algorithm 4.3: Update Variant III /* Update Step: Variant III */ Build K -:= {j ∈ K|j has not been selected in the solution of the last two iterations}. Solve the LP program resulting of fixing the binary variables of SR-FS-SVM(K) to its optimal values.

Figure 7 . 1 :

 71 Figure 7.1: Computational times using KS solution as initial solution of the formulation for Colon dataset with B = 20.

Figure 7 . 2 :

 72 Figure 7.2: Computational times using KS solution as initial solution of the formulation for DLBCL dataset with B = 20.

Figure 7 . 3 :

 73 Figure 7.3: Computational times using KS solution as initial solution of the formulation for Carcinoma dataset with B = 20.

Figure 7 . 4 :

 74 Figure 7.4: Computational times using KS solution as initial solution of the formulation for Carcinoma dataset with B = 10.

  Figure A.1: Average ACC, AUC and number of features for each of the described datasets.

  Algorithm 4: Exact Procedure Data: Training data composed by a set of m elements with n features.Run strategies I and II to tighten u and l and to obtain initial LB and UB.Run the Kernel Search to obtain UB new .if UB new <UB then UB:=UB new and run strategies I and II again.

	Result: Optimal objective value or accurate upper and lower bounds.
	/* Initial Step	*/
	/* Main Step	*/

Table 7

 7 The other eight datasets used in the experiments have a larger number of features (see Table7.1b). The Lepiota, Arrythmia, Madelon and MFeat datasets are also in UCI repository. A further description of the remaining datasets in Table7.1b can be found in[START_REF] Alon | Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligo-nucleotide arrays[END_REF],[START_REF] Carrizosa | Binarized support vector machines[END_REF],[START_REF] Guyon | Gene selection for cancer classification using support vector machines[END_REF],[START_REF] Maldonado | Feature selection for support vector machines via mixed integer linear programming[END_REF],[START_REF] Golub | Molecular classification of cancer: Class discovery and class prediction by gene expression monitoring[END_REF],[START_REF] Shipp | Diffuse large b-cell lymphoma outcome prediction by gene-expression profiling and supervised machine learning[END_REF] and[START_REF] Notterman | Transcriptional gene expression profiles of colorectal adenoma, adenocarcinoma, and normal tissue examined by oligonucleotide arrays[END_REF].

	Small number of features
	Name	m	n Class(%)			Big number of features
	BUPA	345	6	42/58	Small sample size	Big sample size
	PIMA	768	8	65/35	Name	m n	Class(%) Name	m	n	Class(%)
	Cleveland	297 13	42/58
					Colon	62 2000 35/65	Lepiota	1824 109 52/48
	Housing	506 13	51/49
					Leukemia	72 5327 47/53	Arrythmia	420 258 57/43
	Australian 690 14	44/56
					DLBCL	77 7129 75/25	Madelon	2000 500 50/50
	GC	1000 24	30/70
					Carcinoma 36 7457 53/47	Mfeat	2000 649 10/90
	WBC	569 30	37/63
	Ionosphere 351 33	64/36			(b)
		(a)

.1a), where m is the number of elements, n is the number of features and the last column shows the percentage of elements in each class. As can be observed, they contain a small number of features.

Table 7

 7

.1: Datasets description.

Table 7 .

 7 3 shows the results of applying the Kernel Search to the proposed model for the four datasets: Colon, Leukemia, DLBCL and Carcinoma. The "Gap" column details the

	Colon m=62 n=2000 Leukemia m=72 n=5327 DLBCL m=77 n=7129 Carcinoma m=36 n=7457	FS-SVM St. + FS-SVM FS-SVM St. + FS-SVM FS-SVM St. + FS-SVM FS-SVM St. + FS-SVM	Gap Time Gap tst t solv t total ∆B Gap Time Gap Tst t solv t total ∆B Gap Time Gap tst t solv t total ∆B Gap Time Gap tst t solv t total ∆B	0.0 1.44 0.0 34.66 2.35 37.00 0.02 0.0 726.84 0.0 447.50 292.67 740.17 0.05 0.0 16.32 0.0 646.61 21.81 668.41 0.02 0.0 0.56 0.0 307.27 4.32 311.60 0.01	0.0 5.30 0.0 32.51 4.42 36.93 0.05 0.0 792.12 0.0 456.01 281.33 737.34 0.05 0.0 13.57 0.0 649.36 21.48 670.84 0.02 0.0 0.59 0.0 305.81 4.31 310.11 0.01	0.0 3.82 0.0 32.32 4.45 36.77 0.05 0.0 814.42 0.0 457.07 598.00 1055.06 0.05 0.0 16.93 0.0 637.28 21.26 658.54 0.02 0.0 0.61 0.0 305.12 4.35 309.47 0.01	0.0 3.87 0.0 32.25 4.71 36.96 0.05 0.0 710.88 0.0 453.51 885.04 1338.55 0.05 0.0 12.31 0.0 644.91 21.22 666.12 0.02 0.0 0.58 0.0 305.73 4.32 310.05 0.01	0.0 4.10 0.0 32.00 5.27 37.27 0.05 0.0 791.81 0.0 455.26 425.10 880.36 0.05 0.0 15.41 0.0 642.77 22.37 665.14 0.02 0.0 0.60 0.0 305.54 4.32 309.86 0.01	0.0 5.26 0.0 32.41 5.10 37.51 0.05 0.0 621.57 0.0 440.89 199.59 640.47 0.05 0.0 16.17 0.0 640.96 24.96 665.92 0.02 0.0 0.59 0.0 308.58 4.34 312.92 0.01	0.0 5.27 0.0 32.12 5.59 37.70 0.05 0.0 569.28 0.0 440.59 173.85 614.44 0.05 0.0 15.70 0.0 644.73 25.91 670.65 0.02 0.0 0.59 0.0 306.58 4.32 310.90 0.01	0.0 5.65 0.0 32.37 5.30 37.67 0.05 0.0 527.17 0.0 440.78 285.78 726.56 0.05 0.0 16.12 0.0 643.00 22.73 665.73 0.02 0.0 0.60 0.0 305.90 4.33 310.23 0.01	0.0 579.94 0.0 31.91 93.35 125.26 0.40 1.1 7201.03 0.5 362.83 7205.94 7567.88 0.25 0.0 7200.40 0.0 536.39 511.59 1047.98 0.25 0.0 1457.92 0.0 310.88 181.54 492.42 0.04	0.3 7200.19 0.0 35.65 1911.11 1946.76 0.79 1.0 7200.90 0.5 388.25 7206.56 7593.99 0.25 0.0 5759.65 0.0 536.98 582.46 1119.44 0.25 0.0 1478.06 0.0 310.94 159.89 470.82 0.04	0.3 7200.10 0.0 35.30 1634.42 1669.72 0.79 2.0 7201.08 0.6 357.72 7206.43 7563.36 0.25 0.0 7168.70 0.0 535.46 515.52 1050.97 0.25 0.0 1551.47 0.0 309.65 204.00 513.65 0.04	0.3 7200.10 0.0 34.34 1652.39 1686.73 0.79 2.0 7200.97 0.6 362.14 7207.29 7568.63 0.25 0.1 7200.38 0.0 534.11 472.57 1006.68 0.25 0.0 1478.82 0.0 309.27 205.08 514.35 0.04	0.3 7200.10 0.0 34.80 1549.91 1584.71 0.79 1.9 7200.99 0.5 385.96 7206.79 7591.77 0.25 0.0 7200.40 0.0 535.53 513.14 1048.67 0.25 0.0 2016.24 0.0 308.58 210.23 518.82 0.04	0.3 7200.10 0.0 34.32 1380.88 1415.20 0.79 1.9 7200.82 0.1 363.40 7205.80 7568.42 0.25 0.1 7200.38 0.0 539.71 366.16 905.88 0.25 0.0 2680.07 0.0 308.94 183.02 491.96 0.04	0.4 7200.10 0.0 34.23 1098.26 1132.48 0.79 1.8 7201.05 0.2 383.67 7206.14 7588.98 0.25 0.3 7200.42 0.0 541.42 335.07 876.49 0.25 0.0 3283.47 0.0 311.44 108.29 419.73 0.04	0.5 7200.11 0.0 34.76 1009.93 1044.69 0.79 1.8 7200.86 0.3 375.56 7205.54 7580.24 0.25 0.3 7200.39 0.0 540.24 373.70 913.94 0.25 0.0 3231.34 0.0 309.85 108.47 418.32 0.04	2.5 7203.00 0.0 40.03 4598.49 4638.52 2.28 15.1 7202.81 15.9 764.48 7204.22 7968.70 1.71 11.8 7203.61 8.1 1013.27 7209.40 8222.67 1.62 2.4 7203.84 0.0 412.96 6789.65 7202.61 0.37	12.4 7204.81 11.2 46.16 7203.86 7250.02 5.19 17.5 7200.71 19.4 767.57 7204.40 7971.97 1.71 11.1 7200.94 7.2 1015.05 7207.12 8222.17 1.63 2.3 7204.3 0.5 413.39 7204.63 7618.01 0.37	10.5 7200.94 13.6 51.20 7206.82 7258.02 5.56 16.9 7200.29 17.5 783.36 7204.02 7987.37 1.71 13.5 7200.40 9.5 1004.74 7209.84 8214.58 1.63 2.3 7203.33 0.5 415.55 7205.41 7620.96 0.37	15.2 7201.77 12.3 46.35 7206.01 7252.36 5.56 16.8 7203.84 14.9 779.71 7204.02 7983.72 1.71 10.8 7202.02 10.6 1008.17 7206.94 8215.11 1.63 2.3 7203.56 0.0 419.50 7078.98 7498.48 0.37	16.9 7203.00 13.5 47.03 7206.16 7253.19 5.56 12.9 7191.54 15.7 781.86 7207.05 7988.91 1.71 13.5 7200.41 9.2 1006.23 7210.54 8216.77 1.63 2.3 7202.94 0.0 420.87 4460.00 4880.87 0.37	17.1 7206.07 13.0 49.17 7206.29 7255.46 5.56 18.8 7200.29 15.2 784.12 7204.11 7988.23 1.71 13.5 7200.40 10.4 1018.63 7210.67 8229.30 1.63 2.9 7206.39 0.0 415.71 2551.15 2966.86 0.37	16.6 7204.87 12.3 46.80 7205.97 7252.77 5.56 18.7 7203.20 17.9 754.17 7206.49 7960.66 1.71 13.5 7200.40 10.1 998.42 7197.19 8195.61 1.63 2.7 7205.12 0.0 418.61 2744.28 3162.89 0.37	17.0 7201.27 10.8 46.39 7206.23 7252.62 5.56 15.2 7203.81 16.5 775.13 7207.06 7982.19 1.71 13.5 7200.38 9.9 1004.78 7210.10 8214.88 1.63 2.6 7206.23 0.0 422.03 2506.86 2928.89 0.37
			B/C	30/2 0	30/2 1	30/2 2	30/2 3	30/2 4	30/2 5	30/2 6	30/2 7	20/2 0	20/2 1	20/2 2	20/2 3	20/2 4	20/2 5	20/2 6	20/2 7	10/2 0	10/2 1	10/2 2	10/2 3	10/2 4	10/2 5	10/2 6	10/2 7

Table 7 .

 7 2: Time performance comparison of FS-SVM with and without strategies in datasets with a big number of features.

Table 7 .

 7 4: Computational times and gaps using KS as initial solution of the formulation for Colon, Leukemia and DLBCL datasets.

	0.0 2680.07 0.0 491.96 0.0 476.89	0.0 3283.47 0.0 419.73 0.0 456.29	0.0 3231.34 0.0 418.32 0.0 469.33	2.4 7203.84 0.0 7202.61 0.0 6931.78	2.3 7204.30 0.5 7618.01 0.0 7331.22	2.3 7203.33 0.5 7620.96 0.0 6994.41	2.3 7203.56 0.0 7498.48 0.0 6625.83	2.3 7202.94 0.0 4880.87 0.0 5016.86	2.9 7206.39 0.0 2966.86 0.0 3569.74	2.7 7205.12 0.0 3162.89 0.0 3457.01	2.6 7206.23 0.0 2928.89 0.0 3327.63
	905.16	801.61	903.79	8392.61	8390.48	8382.97	8404.06	8410.13	8405.00	8406.76	8407.38
	905.88 0.0	876.49 0.0	913.94 0.0	8222.67 6.8	8222.17 6.6	8214.58 6.6	8215.11 6.6	8216.77 6.5	8229.30 6.2	8195.61 6.1	8214.88 6.2
	1580.30 1.9 7200.82 0.1 7568.42 0.2 7653.38 0.1 7200.38 0.0	1132.48 0.0 1087.20 1.8 7201.05 0.2 7588.98 0.2 7621.43 0.3 7200.42 0.0	1044.69 0.0 712.30 1.8 7200.86 0.3 7580.24 0.2 7620.99 0.3 7200.39 0.0	4638.52 0.0 4447.71 15.1 7202.81 15.9 7968.70 11.4 8980.67 11.8 7203.61 8.1	7250.02 8.5 7396.14 17.5 7200.71 19.4 7971.97 11.4 9079.71 11.1 7200.94 7.2	7258.02 9.3 7442.52 16.9 7200.29 17.5 7987.37 11.3 9212.35 13.5 7200.40 9.5	7252.36 9.1 7470.23 16.8 7203.84 14.9 7983.72 11.3 9214.53 10.8 7202.02 10.6	7253.19 9.2 7481.98 12.9 7191.54 15.7 7988.91 11.1 9236.43 13.5 7200.41 9.2	7255.46 9.1 7434.46 18.8 7200.29 15.2 7988.23 10.9 9243.22 13.5 7200.40 10.4	7252.77 9.1 7485.48 18.7 7203.20 17.9 7960.66 11.0 9284.75 13.5 7200.40 10.1	7252.62 9.1 7437.58 15.2 7203.81 16.5 7982.19 10.9 9261.78 13.5 7200.38 9.9
		0.4 7200.10 0.0	0.5 7200.11 0.0	2.5 7203.00 0.0	12.4 7204.81 11.2	10.5 7200.94 13.6	15.2 7201.77 12.3	16.9 7203.00 13.5	17.1 7206.07 13.0	16.6 7204.87 12.3	17.0 7201.27 10.8
		20/2 6	20/2 7	10/2 0	10/2 1	10/2 2	10/2 3	10/2 4	10/2 5	10/2 6	10/2 7

Table 8

 8 Average ACC for BUPA dataset.Figure 8.2: Average ACC for PIMA dataset.

	.2: Best average ACC and AUC for
	PIMA dataset.

Table 8 .

 8 4: Best average ACC and AUC for Housing dataset.

		Australian Credit m=690 n=14					German Credit m=1000 n=24
	Form. Av. ACC Av. AUC Av. F. B	C Time	Form. Av. ACC Av. AUC Av. F. B	C	Time
	1 -SVM	85.51%	86.21%	1	-2 -1	0.01	1 -SVM	76.20%	68.71%	24	-	2 4	0.04
	2 -SVM	85.51%	86.21%	14	-	2	0.13	2 -SVM	76.10%	68.55%	24	-	2 4	0.18
	LP-SVM	85.22%	85.89%	12	-	2 7	0.01	LP-SVM	76.30%	68.79%	24	-2 -3	0.06
	MILP1	85.51%	86.21%	1	1	-	0.06	MILP1	76.90%	68.93%	17 17	-	0.54
	MILP2	85.51%	86.21%	1	1	2 7	0.04	MILP2	76.70%	69.26%	22 22 2 -7	0.18
	FSV	85.51%	86.21%	1	-	-	0.02	FSV	63.70%	68.36%	1	-	-	0.09
	Fisher-SVM	85.65%	86.34%	10 10	2	0.06	Fisher-SVM	75.10%	72.21%	17 17 2 -3	0.07
	RFE-SVM	85.51%	86.21%	1	1 2 -1	0.18	RFE-SVM	74.30%	71.93%	18 18 2 -3	0.06
	FS-SVM	85.51%	86.21%	1	1	1	0.06	FS-SVM	76.40%	68.95%	21 21	2 6	0.32
	KS FS-SVM	85.51%	86.21%	1	1	1	0.11	KS FS-SVM	76.50%	69.12%	21 21		2 5 0.36
	Table 8.5: Best average ACC and AUC for Aus-
	tralian dataset.

Table 8

 8

	.6: Best average ACC and AUC for Ger-
	man credit dataset.

Table 8 .

 8 8: Best average ACC and AUC for Iono-Average ACC for Australian dataset.Figure 8.6: Average ACC for G. Credit dataset.

	sphere dataset.

Table 8 .

 8 10: Best average ACC and AUC for Leukemia dataset.

		DLBCL m=77 n=7129					Carcinoma m=36 n=7457
	Form. Av. ACC Av. AUC Av. F.	B	C	Time	Form.	ACC	AUC Av. F.	B	C	Time
	1-SVM	98.75%	97.50%	32	-	1	3.15	1-SVM	92.50%	87.50%	14.6	-2 -2	0.81
	2-SVM	96.25%	94.17%	7129	-	1	0.15	2-SVM	95.00% 90.00%	7457	-	2 7	0.06
	LP-SVM	97.50%	95.00%	7129	-2 -4	0.50	LP-SVM	92.50%	87.50%	7457	-	2 7	0.17
	MILP1	88.75%	85.83%	10	10	-728.08	MILP1	74.17%	70.00%	90 90	-278.92
	FSV	49.75%	66.67%	23	-	-	15.66	FSV	74.17%	67.50%	2.9	-	-	5.42
	Fisher-SVM	83.50%	88.17%	100 100 2 -5	0.01	Fisher-SVM 95.00% 90.00%	30 30 2 -4	0.01
	RFE-SVM	98.75%	99.17%	40	40	2 7	0.01	RFE-SVM 95.00% 90.00%	20 20	2 7	2.28
	KS FS-SVM	98.75%	97.50%	30	30	2 6	1.41	KS-FS-SVM	92.50%	87.50%	10 10 2 -4	0.17
	Table 8.11: Best average ACC and AUC for
	DLBCL dataset.

Table 8 .

 8 12: Best average ACC and AUC for Average ACC for Colon dataset. Figure 8.10: Average ACC for Leukemia dataset. Average ACC for DLBCL dataset. Figure 8.12: Average ACC for Carcinoma dataset.

	Carcinoma dataset.

Table 8 .

 8 This subsection analyzes Lepiota, Arrythmia, Madelon and MFeat datasets. As in the previous section, Tables 8.13-8.16 do not include the results of MILP2 due to the huge performing times of this model. For the same reason, Tables8.14 and 8.15 do not show the results of MILP1. Besides, we will use the KS to analyze FS-SVM performance. The results of ACC is illustrated in Figures 8.13-8.16 in which B varies betweeen 10 and 100 for the C values shown in Tables 8.13-8.16.The results of the Lepiota dataset are presented in Table8.13. Note that for this dataset almost all models provide the same good results. It is important to point out that KS FS-SVM is the model which attains the best accuracy using the smallest number of features. In Figure8.13 we can see that for each value of parameter B, KS FS-SVM provides the best average accuracy. In the case of the Arrythmia dataset (Table8.14), the model with the best behaviour is 2 -SVM. However, we would highlight the fact that KS FS-SVM obtains a similar result whilst using many less features than 2 -SVM. Figure8.14 shows that KS-FS-SVM provides the best results.Fisher-SVM is the best model for Madelon dataset, but 1 -SVM and KS FS-SVM also provide good accuracy and AUC with a lesser number of features, (see Table8.15). In addition to this, Figure8.15 illustrates that KS FS-SVM provides the best behaviour for different values of B. For MFeat dataset, the best results are achieved by KS FS-SVM, as can be seen in 8.16. Moreover, it can be seen in Figure8.16, the best accuracy is obtained when using KS FS-SVM for different values of B. 13: Best average ACC and AUC for Lepiota dataset.

	Lepiota m=1824 n=109
							Arrythmia m=420 n=258
	Form. Av. ACC Av. AUC Av. F.	B	C	Time
	100.00% 100.00% 100.00% 100.00% LP-SVM 100.00% 100.00% 1-SVM 2-SVM	12.7 110 114.8	--	2 6 2 6 135.98 4.28 2 6 1.38	Form. Av. ACC Av. AUC Av. F. 1-SVM 77.86% 75.93% 69.2 78.81% 77.20% 258 2-SVM LP-SVM 70.48% 69.21% 278	B	C 2-1 2 -3 2 -7	Time 0.76 0.13 0.16
	MILP1 100.00% 100.00%	10	10	-329.58
						FSV	64.76%	62.08%	117.6	0.23
	FSV Fisher-SVM RFE-SVM KS FS-SVM 100.00% 100.00% 71.70% 71.88% 99.90% 99.90% 99.91% 99.91%	2 95 100 2 -7 --90 90 2 -7 10 10 2 6	20.13 7.73 7.33 0.67	Fisher-SVM RFE-SVM KS FS-SVM	72.14% 74.76% 77.14%	68.22% 71.27% 75.47%	100 100 2 -4 80 80 2 -5 40 40 2 0 1851.09 0.32 13.29

Table 8 .

 8 14: Best average ACC and AUC for Arrythmia dataset. Average ACC for Lepiota dataset. Figure 8.14: Average ACC for Arrythmia dataset.

	100%									78%
	100%									76%
	99%									74%
	98% 98% 99%								MILP1 Fisher RFE KS FS-SVM	72% 70% 68%								Fisher RFE KS FS-SVM
	97%									66%
	97%									64%
	10	20	30	40	50	60	70	80	90 100	10	20	30	40	50	60	70	80	90 100
	52% 60% 62% 64% Figure 8.13: 50% 54% 56% 58%						Fisher RFE KS FS-SVM	88% 90% 96% 98% 100% 94% 92%								MILP1 Fisher RFE KS FS-SVM
	10	20	30	40	50	60	70	80	90 100	10	20	30	40	50	60	70	80	90 100

Figure 8.15: Average ACC for Madelon dataset.

Figure 8.16: Average ACC for MFeat dataset.

Table 8 .

 8 16: Best average ACC and AUC for MFeat dataset.We have in this paper provided an MILP model for a classification problem with feature selection based on an SVM approach. We anlyzed different solution methods for this model, using exact and heuristic algorithms. In addition, in order to validate the model, we have compared the results of the model with respect to others existing in the literature. The main conclusion is that the results are good, stable and, in some cases, they provide an improvement over existing models for small instances and instances with small sample size and big number of features. However, future work should focus on the development of enhancements for the cases with big sample size and big number of features.

	9 Concluding remarks

Table A .

 A model, 1 -SVM presents smaller running times since it is a linear model. The largest time difference can be observed in the case of Madelon dataset. 1: Percentage of overlap between features selected by 1 -SVM and FS-SVM and average time of each formulation.

			Times					Times
		C			% Overlap		C			% Overlap
			1 -SVM FS-SVM				1 -SVM FS-SVM
		2 -4	0.01	0.00	100		2 -4	0.20	0.10	52.50
		2 -2	0.01	0.10	99.33		2 -2	0.20	1.17	97.98
	Ionosphere	2 0	0.01	0.38	99.29	Arrythmia	2 0	0.20	104.59	98.01
		2 2	0.01	0.34	100		2 2	0.20	35.67	98.50
		2 4	0.01	4.11	99.38		2 4	0.18	31.30	99.50
		2 6	0.01	5.61	100		2 6	0.18	31.84	99.50
			Times					Times
		C			% Overlap		C			% Overlap
			1 -SVM FS-SVM				1 -SVM FS-SVM
		2 -4	-	-	-		2 -4	10.09	165.50	99.41
		2 -2	0.38	0.18	100		2 -2	14.06	875.32	100
	Colon	2 0	0.41	19.17	89.00	Madelon	2 0	14.15	798.28	100
		2 2	0.36	91.17	94.50		2 2	13.15	1807.79	100
		2 4	0.34	93.04	94.50		2 4	12.50	1846.84	100
		2 6	0.31	99.21	94.50		2 6	12.46	1860.22	100

Acknowledgements

This research was supported in part by Ministerio de Economía y Competitividad via grant numbers MTM2013-46962-C02-02 and MTM2016-74983-C2-2-R. Luisa I. Martínez Merino acknowledges that the research reported here was also supported by Universidad de Cádiz, via PhD grant number UCA/REC02VIT/2014. This work was also partially supported by the Interuniversity Attraction Poles Programme P7/36 COMEX initiated by the Belgian Science Policy Office.

A Appendix

The purpose of this section is to provide an analysis of similarities and differences between the classical 1 -SVM and the proposed FS-SVM. Concretely, we will study four of the previous described datasets: Ionosphere (m=351, n=33), Colon (m=62, n=2000), Arrythmia (m=420, n=258) and Madelon (m=2000, n=649). For these datasets, 10-FCV is performed and the results for C ∈ {2 -4 , 2 -2 , 2 0 , 2 2 , 2 4 , 2 6 } are reported. In the case of FS-SVM model, the values reported correspond to the results of the B value with best accuracy in the 10-FCV and besides, the KS-FS-SVM is used for the large datasets (Colon, Arrythmia and Madelon).

Note that for the Colon dataset, the results are not reported for C = 2 -4 since the solutions are degenerated (w j = 0, ∀j = 1, . . . , n) in both models for this value of C. Regarding the number of features, we observe that FS-SVM uses less features than 1 -SVM in general. The most remarkable instances are the Arrythmia and Madelon datasets.