A strengthened mixed-integer linear formulation for the K clusters problem with fixed cardinality

Lídia Ludovina Lampreia Caeiro Pica Lourenço; Graça Maria Marques da Silva Gonçalves

A strengthened mixed-integer linear formulation for the K clusters problem with fixed cardinality

Lídia Ludovina Lampreia Caeiro Pica Lourenço, Graça Maria Marques da Silva Gonçalves

DM - Departamento de Matemática

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

In this paper we study the K clusters with fixed cardinality problem that consists in finding K clusters, where each cluster has a fixed cardinality. We propose a mixed-integer linear programming formulation and deduce valid inequalities to strengthen the linear relaxation bound. The quality of the model is tested on randomly generated instances, by using standard software, with promising results.

Original language	Unknown
Title of host publication	Mathematics and Computers in Science and Engineering
Editors	C Bulucea, V Mladenov, E Pop, M Leba, N Mastorakis
Place of Publication	AG LOANNOU THEOLOGOU 17-23, 15773 ZOGRAPHOU, ATHENS, GREECE
Publisher	World Scientific and Engineering Acad and Soc
Pages	229-232
ISBN (Print)	978-960-474-138-0
Publication status	Published - 1 Jan 2009
Event	14th WSEAS International Conference on Applied Mathematics (MATH '09) - Puerto De La Cruz (Tenerife, Canary Islands), Spain Duration: 14 Sept 2009 → 16 Sept 2009

Conference

Conference	14th WSEAS International Conference on Applied Mathematics (MATH '09)
Country/Territory	Spain
City	Puerto De La Cruz (Tenerife, Canary Islands)
Period	14/09/09 → 16/09/09

Cite this

Lourenço, Lídia Ludovina Lampreia Caeiro Pica ; Gonçalves, Graça Maria Marques da Silva. / A strengthened mixed-integer linear formulation for the K clusters problem with fixed cardinality. Mathematics and Computers in Science and Engineering. editor / C Bulucea ; V Mladenov ; E Pop ; M Leba ; N Mastorakis. AG LOANNOU THEOLOGOU 17-23, 15773 ZOGRAPHOU, ATHENS, GREECE : World Scientific and Engineering Acad and Soc, 2009. pp. 229-232

@inproceedings{548cf518b6b5433e87fa50b92d81a811,

title = "A strengthened mixed-integer linear formulation for the K clusters problem with fixed cardinality",

abstract = "In this paper we study the K clusters with fixed cardinality problem that consists in finding K clusters, where each cluster has a fixed cardinality. We propose a mixed-integer linear programming formulation and deduce valid inequalities to strengthen the linear relaxation bound. The quality of the model is tested on randomly generated instances, by using standard software, with promising results.",

keywords = "valid inequalities, K clusters problem, mixed-integer linear programming, fixed cardinality",

author = "Louren{\c c}o, {L{\'i}dia Ludovina Lampreia Caeiro Pica} and Gon{\c c}alves, {Gra{\c c}a Maria Marques da Silva}",

note = "14th WSEAS International Conference on Applied Mathematics, Puerto de la Cruz, SPAIN, DEC 14-16, 2009; 14th WSEAS International Conference on Applied Mathematics (MATH '09) ; Conference date: 14-09-2009 Through 16-09-2009",

year = "2009",

month = jan,

day = "1",

language = "Unknown",

isbn = "978-960-474-138-0",

pages = "229--232",

editor = "C Bulucea and V Mladenov and E Pop and M Leba and N Mastorakis",

booktitle = "Mathematics and Computers in Science and Engineering",

publisher = "World Scientific and Engineering Acad and Soc",

}

Lourenço, LLLCP & Gonçalves, GMMDS 2009, A strengthened mixed-integer linear formulation for the K clusters problem with fixed cardinality. in C Bulucea, V Mladenov, E Pop, M Leba & N Mastorakis (eds), Mathematics and Computers in Science and Engineering. World Scientific and Engineering Acad and Soc, AG LOANNOU THEOLOGOU 17-23, 15773 ZOGRAPHOU, ATHENS, GREECE, pp. 229-232, 14th WSEAS International Conference on Applied Mathematics (MATH '09), Puerto De La Cruz (Tenerife, Canary Islands), Spain, 14/09/09.

A strengthened mixed-integer linear formulation for the K clusters problem with fixed cardinality. / Lourenço, Lídia Ludovina Lampreia Caeiro Pica ; Gonçalves, Graça Maria Marques da Silva.
Mathematics and Computers in Science and Engineering. ed. / C Bulucea; V Mladenov; E Pop; M Leba; N Mastorakis. AG LOANNOU THEOLOGOU 17-23, 15773 ZOGRAPHOU, ATHENS, GREECE: World Scientific and Engineering Acad and Soc, 2009. p. 229-232.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A strengthened mixed-integer linear formulation for the K clusters problem with fixed cardinality

AU - Lourenço, Lídia Ludovina Lampreia Caeiro Pica

AU - Gonçalves, Graça Maria Marques da Silva

N1 - 14th WSEAS International Conference on Applied Mathematics, Puerto de la Cruz, SPAIN, DEC 14-16, 2009

PY - 2009/1/1

Y1 - 2009/1/1

N2 - In this paper we study the K clusters with fixed cardinality problem that consists in finding K clusters, where each cluster has a fixed cardinality. We propose a mixed-integer linear programming formulation and deduce valid inequalities to strengthen the linear relaxation bound. The quality of the model is tested on randomly generated instances, by using standard software, with promising results.

AB - In this paper we study the K clusters with fixed cardinality problem that consists in finding K clusters, where each cluster has a fixed cardinality. We propose a mixed-integer linear programming formulation and deduce valid inequalities to strengthen the linear relaxation bound. The quality of the model is tested on randomly generated instances, by using standard software, with promising results.

KW - valid inequalities

KW - K clusters problem

KW - mixed-integer linear programming

KW - fixed cardinality

M3 - Conference contribution

SN - 978-960-474-138-0

SP - 229

EP - 232

BT - Mathematics and Computers in Science and Engineering

A2 - Bulucea, C

A2 - Mladenov, V

A2 - Pop, E

A2 - Leba, M

A2 - Mastorakis, N

PB - World Scientific and Engineering Acad and Soc

CY - AG LOANNOU THEOLOGOU 17-23, 15773 ZOGRAPHOU, ATHENS, GREECE

T2 - 14th WSEAS International Conference on Applied Mathematics (MATH '09)

Y2 - 14 September 2009 through 16 September 2009

ER -

Lourenço LLLCP , Gonçalves GMMDS. A strengthened mixed-integer linear formulation for the K clusters problem with fixed cardinality. In Bulucea C, Mladenov V, Pop E, Leba M, Mastorakis N, editors, Mathematics and Computers in Science and Engineering. AG LOANNOU THEOLOGOU 17-23, 15773 ZOGRAPHOU, ATHENS, GREECE: World Scientific and Engineering Acad and Soc. 2009. p. 229-232