Solving the market split problem using a distributed computation approach

Zhengtian Wu; Chuangyin Dang; Changan Zhu

doi:10.1109/ICInfA.2013.6720486

Solving the market split problem using a distributed computation approach

Zhengtian Wu
, Chuangyin Dang
, Changan Zhu

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

3 Citations (Scopus)

Abstract

A distributed implementation of Dang's Fixed-Point iterative method is proposed to solve the market split problem which has been considered as a benchmark and a challenge to the algorithms solving linear systems with 0/1 variables. There are two steps to solve the market split problem in this paper. The first step is converting the problem to a reformulated polytope judgement problem based on lattice basis reduction. In the next step, the distributed Dang's method is used to judge whether there exits an integer point in the polytope. This is the first distributed implementation to solve the market split problem to our knowledge. Numerical results show that the approach is effective and it is more powerful than CPLEX to solve the market split problem. © 2013 IEEE.

Original language	English
Title of host publication	2013 IEEE International Conference on Information and Automation, ICIA 2013
Pages	1252-1257
DOIs	https://doi.org/10.1109/ICInfA.2013.6720486
Publication status	Published - 2013
Event	2013 IEEE International Conference on Information and Automation, ICIA 2013 - Yinchuan, China Duration: 26 Aug 2013 → 28 Aug 2013

Conference

Conference	2013 IEEE International Conference on Information and Automation, ICIA 2013
Place	China
City	Yinchuan
Period	26/08/13 → 28/08/13

Research Keywords

Basis Reduction
Distributed Implementation
Fixed-Point Iterative Method
Market Split Problem

Access Output

10.1109/ICInfA.2013.6720486

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{9f54ad3ab5ab4206b7ca7b584f924fa7,

title = "Solving the market split problem using a distributed computation approach",

abstract = "A distributed implementation of Dang's Fixed-Point iterative method is proposed to solve the market split problem which has been considered as a benchmark and a challenge to the algorithms solving linear systems with 0/1 variables. There are two steps to solve the market split problem in this paper. The first step is converting the problem to a reformulated polytope judgement problem based on lattice basis reduction. In the next step, the distributed Dang's method is used to judge whether there exits an integer point in the polytope. This is the first distributed implementation to solve the market split problem to our knowledge. Numerical results show that the approach is effective and it is more powerful than CPLEX to solve the market split problem. {\textcopyright} 2013 IEEE.",

keywords = "Basis Reduction, Distributed Implementation, Fixed-Point Iterative Method, Market Split Problem",

author = "Zhengtian Wu and Chuangyin Dang and Changan Zhu",

year = "2013",

doi = "10.1109/ICInfA.2013.6720486",

language = "English",

isbn = "9781479913343",

pages = "1252--1257",

booktitle = "2013 IEEE International Conference on Information and Automation, ICIA 2013",

note = "2013 IEEE International Conference on Information and Automation, ICIA 2013 ; Conference date: 26-08-2013 Through 28-08-2013",

}

Solving the market split problem using a distributed computation approach. / Wu, Zhengtian; Dang, Chuangyin; Zhu, Changan.
2013 IEEE International Conference on Information and Automation, ICIA 2013. 2013. p. 1252-1257 6720486.

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Solving the market split problem using a distributed computation approach

AU - Wu, Zhengtian

AU - Dang, Chuangyin

AU - Zhu, Changan

PY - 2013

Y1 - 2013

N2 - A distributed implementation of Dang's Fixed-Point iterative method is proposed to solve the market split problem which has been considered as a benchmark and a challenge to the algorithms solving linear systems with 0/1 variables. There are two steps to solve the market split problem in this paper. The first step is converting the problem to a reformulated polytope judgement problem based on lattice basis reduction. In the next step, the distributed Dang's method is used to judge whether there exits an integer point in the polytope. This is the first distributed implementation to solve the market split problem to our knowledge. Numerical results show that the approach is effective and it is more powerful than CPLEX to solve the market split problem. © 2013 IEEE.

AB - A distributed implementation of Dang's Fixed-Point iterative method is proposed to solve the market split problem which has been considered as a benchmark and a challenge to the algorithms solving linear systems with 0/1 variables. There are two steps to solve the market split problem in this paper. The first step is converting the problem to a reformulated polytope judgement problem based on lattice basis reduction. In the next step, the distributed Dang's method is used to judge whether there exits an integer point in the polytope. This is the first distributed implementation to solve the market split problem to our knowledge. Numerical results show that the approach is effective and it is more powerful than CPLEX to solve the market split problem. © 2013 IEEE.

KW - Basis Reduction

KW - Distributed Implementation

KW - Fixed-Point Iterative Method

KW - Market Split Problem

UR - https://www.scopus.com/pages/publications/84894216165

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84894216165&origin=recordpage

U2 - 10.1109/ICInfA.2013.6720486

DO - 10.1109/ICInfA.2013.6720486

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9781479913343

SP - 1252

EP - 1257

BT - 2013 IEEE International Conference on Information and Automation, ICIA 2013

T2 - 2013 IEEE International Conference on Information and Automation, ICIA 2013

Y2 - 26 August 2013 through 28 August 2013

ER -

Solving the market split problem using a distributed computation approach

Abstract

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this