Browsing by Author "Fang, Shu-Cherng"

Now showing 1 - 6 of 6

A Logarithmic Method for Reducing Binary Variables and Inequality Constraints in Solving Task Assignment Problems
(2013-09-01)
Li, Han-Lin
;
Huang, Yao-Huei
;
Fang, Shu-Cherng
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper studies the classical task assignment problem (TAP) in which M unbreakable tasks are assigned to N agents with the objective to minimize the communication and process costs subject to each agent's capacity constraint. Because a large-size TAP involves many binary variables, most, if not all, traditional methods experience the difficulty in solving the problem within a reasonable time period. Recent works present a logarithmic approach to reduce the number of binary variables in problems with mixed-integer variables. This study proposes a new logarithmic method that significantly reduces the numbers of binary variables and inequality constraints in solving task assignment problems. Our numerical experiments demonstrate that the proposed method is superior to other known methods of this kind for solving large-size TAPs.
An enhanced logarithmic method for signomial programming with discrete variables
(2016-12-16)
Li, Han-Lin
;
Fang, Shu-Cherng
;
Huang, Yao-Huei
;
Nie, Tiantian
;
資訊管理與財務金融系註：原資管所+財金所
Signomial programming problems with discrete variables (SPD) appear widely in real-life applications, but they are hard to solve. This paper proposes an enhanced logarithmic method to reformulate the SPD problem as a mixed 0-1 linear program (MILP) with a minimum number of binary variables and inequality constraints. Both of the theoretical analysis and numerical results strongly support its superior performance to other state-of-the-art linearization methods. We also extend the proposed method to linearize some more complicated problems involving product and fractional terms in discrete and continuous variables. (C) 2016 Elsevier B.V. All rights reserved.
An integrated algorithm for solving multi-customer joint replenishment problem with districting consideration
(2020-06-01)
Yao, Ming-Jong
;
Lin, Jen-Yen
;
Lin, Yu-Liang
;
Fang, Shu-Cherng
;
運輸與物流管理系註：原交通所+運管所
This paper studies a multi-customer joint replenishment problem with districting consideration (MJRPDC) which is of particular importance to a company that outsources its transportation and delivery operations to a third-party logistics (3PL) service provider. To solve the problem, we first propose an innovative search algorithm for solving the traditional multi-customer joint replenishment problem in a given zone. Then we design a GA-based framework to handle the corresponding districting problem based on the performance of each district evaluated by using the proposed search algorithm. The proposed methodologies are demonstrated by using an example of solving MJRPDC for a bank.
Enhanced linear reformulation for engineering optimization models with discrete and bounded continuous variables
(2018-06-01)
An, Qi
;
Fang, Shu-Cherng
;
Li, Han -Lin
;
Nie, Tiantian
;
資訊管理與財務金融系註：原資管所+財金所
In this paper, we significantly extend the applicability of state-of-the-art ELDP (equations for linearizing discrete product terms) method by providing a new linearization to handle more complicated non-linear terms involving both of discrete and bounded continuous variables. A general class of "representable programming problems" is formally proposed for a much wider range of engineering applications. Moreover, by exploiting the logarithmic feature embedded in the discrete structure, we present an enhanced linear reformulation model which requires half an order fewer equations than the original ELDP. Computational experiments on various engineering design problems support the superior computational efficiency of the proposed linearization reformulation in solving engineering optimization problems with discrete and bounded continuous variables. (C) 2017 Elsevier Inc. All rights reserved.
Linear Reformulation of Polynomial Discrete Programming for Fast Computation
(2017-12-01)
Li, Han-Lin
;
Huang, Yao-Huei
;
Fang, Shu-Cherng
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
Polynomial discrete programming problems are commonly faced but hard to solve. Treating the nonconvex cross-product terms is the key. State-of-the-art methods usually convert such a problem into a 0-1 mixed-integer linear programming problem and then adopt the branch-and-bound scheme to find an optimal solution. Much effort has been spent on reducing the required numbers of variables and linear constraints as well as on avoiding unbalanced branch-and-bound trees. This study presents a set of equations that linearize the discrete cross-product terms in an extremely effective manner. It is shown that embedding the proposed "equations for linearizing discrete products" into those state-of-the-art methods in the literature not only significantly reduces the required number of linear constraints from O(h(3)n(3)) to O(hn) for a cubic polynomial discrete program with n variables in h possible values but also tighten these methods with much more balanced branch-and-bound trees. Numerical experiments confirm a two-order (10(2)-times) reduction in computational time for some randomly generated cubic polynomial discrete programming problems.
SOLVING ROUTING AND WAVELENGTH ASSIGNMENT PROBLEM WITH MAXIMUM EDGE-DISJOINT PATHS
(2017-04-01)
Hsu, Chia-Chun
;
Cho, Hsun-Jung
;
Fang, Shu-Cherng
;
運輸與物流管理系註：原交通所+運管所
;
Department of Transportation and Logistics Management
The routing and wavelength assignment (RWA) problem in wavelength-division multiplexing optical networks is critically important for increasing the efficiency of wavelength-routed all-optical networks. Given the physical network structure and a set of connection requests, the problem aims to establishing routes for the requests and assigning a wavelength to each of them, subject to the wavelength continuous and wavelength clash constraints. The objective is to minimize he number of required wavelengths to satisfy all requests. The RWA problem was proven to be NP-hard and has been investigated for decades. In this paper, an algorithm based on the maximum edge-disjoint paths is proposed to tackle the RWA problem. Its performance is verified by experiments on some realistic network topologies. Compared with the state-of-the-art bin-packing based methods and the particle swarm optimization al- gorithm, the proposed method can find the best solution among all testing instances in reasonable computing time.