China
Africa
Explore chapters and articles related to this topic
Linear Programming and Mixed Integer Programming
Published in Erchin Serpedin, Thomas Chen, Dinesh Rajan, Mathematical Foundations for SIGNAL PROCESSING, COMMUNICATIONS, AND NETWORKING, 2012
Linear fractional programming (LFP) is an example of non-convex (quasi-convex, actually) optimization problem that can be transformed into an LP one. An LFP problem has the form () μ0=maxbTx+deTx+fs.t.Aex=beAix≤bi
A two-level vertex-searching global algorithm framework for bilevel linear fractional programming problems
Published in Systems Science & Control Engineering, 2020
In this paper, we focus on the continuous bilevel linear fractional programming problem (BLFP) over a polyhedron, in which both the upper and the lower objectives are linear fractional. To the best of the author's knowledge, there are two methods in literature that can reach the global optimum to (BLFP). One is the Kth-best algorithm proposed in Calvete and Galé (2004b) which is an extension version from that of solving the bilevel linear problem. The Kth-best algorithm can be regarded as the only one two-level primal vertex-searching algorithm, in which only primal information, including the primal models and the primal polyhedron as the search space, was used in the solving procedure. At each iteration, this algorithm searches the best vertex by enumerating all neighbour vertices for a given vertex followed a path with monotonic upper objective function value until this best vertex is in IR. The other existing algorithm for (BLFP) to reach the global optimum is the algorithm in Wang et al. (2012) which used the duality-based approach transforming the original bilevel problem into an equivalent single-level one by replacing the lower level program with its dual problem and forcing the dual gap to be zero. This approach also requires some enumerative scheme to do the vertex-searching task. More precisely, it searches vertices of the polyhedron on the dual problem of the lower level problem. Moreover, this algorithm needs to generate all vertices of it's search space by the Back-track algorithm proposed in Fukuda et al. (1997). Hence, the single-level duality-based reformulation method can be regarded as a single-level primal–dual vertex-searching algorithm.
Real-time procurement policy with yield and price uncertainty
Published in International Journal of Production Research, 2020
Wenqiang Dai, Zhuolin Yang, Yi Feng, Meng Zheng
Let , , then the above problem is Applying a well-known result (see e.g. Boyd and Vandenberghe 2004), the above linear-fractional programming problem becomes equivalent to a linear programming problem as follows: The dual of the above LP is given below (see e.g. Luenberger and Ye 2016): The optimal value is . This lemma follows.
Replenishment policy for a purchase-to-order seller: a tradeoff between ordering cost and delay cost
Published in International Journal of Production Research, 2020
Wagner (2011) studies two online lot-sizing problems by utilising linear-fractional programming and duality theory. The first problem considers perishable products with lost sales and the second one considers durable products with backlogged demand. For the special case of the second problem, Wagner (2011) analyzes an MTO strategy that never maintains positive inventory. This special MTO strategy is similar to the work of Buchbinder et al. (2013) and ours in that the product cannot be inventoried for future demand but all the demand unfulfilled in previous periods can be backlogged.