WINNER DETERMINATION IN COMBINATORIAL REVERSE AUCTION USING GENETIC ALGORITHM AND DANTZIG-WOLFE DECOMPOSITION

Q: How can I download an article?

To download an article from SID, first log in to the site, search for the article title, and click on the 'Download Article' option.

Q: How can I download an ISI article?

To download an ISI article on SID, enter the keyword or article title in the search bar, view the relevant results, click on the desired article, and select the 'Download Article' option.

Q: How can I access the SID database?

To access the SID database, visit SID.ir, create an account, and log in to access scientific resources.

Q: Is downloading articles from SID free?

Some articles on SID are available for free, while others require payment. Details are specified on the article's page.

Alaei R.; SETAK M.

مرکز اطلاعات علمی Scientific Information Database (SID) - Trusted Source for Research and Academic Resources

Journal Paper

Paper Information

Journal: INDUSTRIAL ENGINEERING & MANAGEMENT SHARIF (SHARIF: ENGINEERING) Year:2019 | Volume:35-1 | Issue:1/1 Page(s): 47-56

Download Full-Text

Persian Verion

View:

434

Download:

Cites:

Information Journal Paper

Title

WINNER DETERMINATION IN COMBINATORIAL REVERSE AUCTION USING GENETIC ALGORITHM AND DANTZIG-WOLFE DECOMPOSITION

Author(s)

Alaei R. | SETAK M. | Issue Writer Certificate

Keywords

Supplier selectionQ1

combinatorial reverse auctionQ1

winner determination problemQ1

genetic algorithmQ2

dantzig-wolfe decompositionQ1

Abstract

In this paper, the problem of winner determination in a combinatorial reverse auction mechanism is considered for solving. Because of NP-completeness of finding a feasible solution for the formulated winner determination problem as well as its solving, the popular exact methods are failed in solving its large-scale instances. So, an exact problem-specific two-stage method is proposed to reduce the time required for its solving. The proposed method involves a well-known population-based meta-heuristic called genetic algorithm and an advanced exact method called dantzig-wolfe decomposition in first and second stages, respectively. The genetic algorithm is used for finding a near-optimal feasible solution for the formulated winner determination problem as an initial solution for the second stage. The proposed genetic algorithm generates feasible solutions in initial population and repairs infeasible child solutions after reproduction using problem-specific operators. Also, dantzig-wolfe decomposition is used for decomposing the formulated winner determination problem with block-diagonal structure in its constraints matrix to a master problem and multiple sub-problems for finding its optimal solution within a reasonable time starting from the nearoptimal feasible solution found by genetic algorithm in first stage. We conducted a computational experiment using randomly generated instances of winner determination problem with different sizes to evaluate the performance of our proposed two-stage method in solving the formulated winner determination problem. Computational results demonstrate that the genetic algorithm performs well in finding near-optimal solutions of the formulated problem. Also, the computational results show that the dantzig-wolfe decomposition based method in second stage can improve the near-optimal solution found by genetic algorithm in first stage and find the optimal solution of formulated winner determination problem as well as confirming the optimality or non-optimality of solution found by genetic algorithm. The other result is that the proposed two-stage method spends less time compared with LINGO software in finding optimal solution of formulated winner determination problem.

Cites

No record.

References

No record.

Cite

APA: Copy

Alaei, R., & SETAK, M.. (2019). WINNER DETERMINATION IN COMBINATORIAL REVERSE AUCTION USING GENETIC ALGORITHM AND DANTZIG-WOLFE DECOMPOSITION. INDUSTRIAL ENGINEERING & MANAGEMENT SHARIF (SHARIF: ENGINEERING), 35-1(1/1 ), 47-56. SID. https://sid.ir/paper/107559/en

Vancouver: Copy

Alaei R., SETAK M.. WINNER DETERMINATION IN COMBINATORIAL REVERSE AUCTION USING GENETIC ALGORITHM AND DANTZIG-WOLFE DECOMPOSITION. INDUSTRIAL ENGINEERING & MANAGEMENT SHARIF (SHARIF: ENGINEERING)[Internet]. 2019;35-1(1/1 ):47-56. Available from: https://sid.ir/paper/107559/en

IEEE: Copy

R. Alaei, and M. SETAK, “WINNER DETERMINATION IN COMBINATORIAL REVERSE AUCTION USING GENETIC ALGORITHM AND DANTZIG-WOLFE DECOMPOSITION,” INDUSTRIAL ENGINEERING & MANAGEMENT SHARIF (SHARIF: ENGINEERING), vol. 35-1, no. 1/1 , pp. 47–56, 2019, [Online]. Available: https://sid.ir/paper/107559/en

Related Journal Papers