ISSN:
1547-5816
eISSN:
1553-166X
All Issues
Journal of Industrial & Management Optimization
January 2012 , Volume 8 , Issue 1
Select all articles
Export/Reference:
2012, 8(1): 1-17
doi: 10.3934/jimo.2012.8.1
+[Abstract](2865)
+[PDF](544.1KB)
Abstract:
This paper focuses on an M/M/$s$ queue with multiple working vacations such that the server works with different service rates rather than no service during the vacation period. We show that this is a generalization of an M/M/1 queue with working vacations in the literature. Service times during vacation period, or during service period and vacation times are all exponentially distributed. We obtain the useful formula for the rate matrix $\textbf{R}$ through matrix-geometric method. A cost function is formulated to determine the optimal number of servers subject to the stability conditions. We apply the direct search algorithm and Newton-Quasi algorithm to heuristically find an approximate solution to the constrained optimization problem. Numerical results are provided to illustrate the effectiveness of the computational algorithm.
This paper focuses on an M/M/$s$ queue with multiple working vacations such that the server works with different service rates rather than no service during the vacation period. We show that this is a generalization of an M/M/1 queue with working vacations in the literature. Service times during vacation period, or during service period and vacation times are all exponentially distributed. We obtain the useful formula for the rate matrix $\textbf{R}$ through matrix-geometric method. A cost function is formulated to determine the optimal number of servers subject to the stability conditions. We apply the direct search algorithm and Newton-Quasi algorithm to heuristically find an approximate solution to the constrained optimization problem. Numerical results are provided to illustrate the effectiveness of the computational algorithm.
2012, 8(1): 19-40
doi: 10.3934/jimo.2012.8.19
+[Abstract](2240)
+[PDF](461.2KB)
Abstract:
We study an optimal inventory control problem for a seller to sell a replenishment product via sequential Internet auctions. At the beginning of each auction, the seller may purchase his good from an outside supplier with a fixed ordering cost. There is a holding cost for inventory and backordering is not allowed. We address the total expected discounted criteria in both finite and infinite horizons and the average criterion in an infinite horizon. We show that the classic $(j, J)$ policy is optimal for each criterion. Moreover, we obtain integer programming with bounded decision variables $j$ and $J$ for computing the optimal $(j, J)$ policies for both the discounted and average criteria in an infinite horizon. Finally, numerical results show that it is meaningful for the seller to reduce randomness in the number of buyers with certainly remaining the average number of arriving buyers, but to enhance randomness in the buyers' valuation.
We study an optimal inventory control problem for a seller to sell a replenishment product via sequential Internet auctions. At the beginning of each auction, the seller may purchase his good from an outside supplier with a fixed ordering cost. There is a holding cost for inventory and backordering is not allowed. We address the total expected discounted criteria in both finite and infinite horizons and the average criterion in an infinite horizon. We show that the classic $(j, J)$ policy is optimal for each criterion. Moreover, we obtain integer programming with bounded decision variables $j$ and $J$ for computing the optimal $(j, J)$ policies for both the discounted and average criteria in an infinite horizon. Finally, numerical results show that it is meaningful for the seller to reduce randomness in the number of buyers with certainly remaining the average number of arriving buyers, but to enhance randomness in the buyers' valuation.
2012, 8(1): 41-49
doi: 10.3934/jimo.2012.8.41
+[Abstract](1841)
+[PDF](322.1KB)
Abstract:
The nestedness property has become an increasingly important means for devising efficient algorithms for network location problems. In this paper we prove that the nestedness property holds for the tactical continuous, and strategic discrete and continuous subtree location problems in a tree network with the ordered median objective, where the $\lambda$-weights take at most two different values. These results extend some existing results in the literature. With these nestedness results, we solve the problems in polynomial time. Finally we pose an open problem on identifying the nestedness property for the $(k_1,k_2)$-trimmed problem.
The nestedness property has become an increasingly important means for devising efficient algorithms for network location problems. In this paper we prove that the nestedness property holds for the tactical continuous, and strategic discrete and continuous subtree location problems in a tree network with the ordered median objective, where the $\lambda$-weights take at most two different values. These results extend some existing results in the literature. With these nestedness results, we solve the problems in polynomial time. Finally we pose an open problem on identifying the nestedness property for the $(k_1,k_2)$-trimmed problem.
2012, 8(1): 51-65
doi: 10.3934/jimo.2012.8.51
+[Abstract](2492)
+[PDF](402.8KB)
Abstract:
This paper considers a penalty algorithm for solving the generalized Nash equilibrium problem (GNEP). Under the GNEP-MFCQ at a limiting point of the sequence generated by the algorithm, we demonstrate that the limit point is a solution to the GNEP and the parameter becomes a constant after a finite iterations. We formulate the Karush-Kuhn-Tucker conditions for a penalized problem into a system of nonsmooth equations and demonstrate the nonsingularity of its Clarke’s generalized Jacobian at the KKT point under the so-called GNEP-Second Order Sufficient Condition. The nonsingularity facilitates the application of the smoothing Newton method for the global convergence and local quadratic rate. Finally, the numerical results are reported to show the effectiveness of the penalty method in solving generalized Nash equilibrium problem.
This paper considers a penalty algorithm for solving the generalized Nash equilibrium problem (GNEP). Under the GNEP-MFCQ at a limiting point of the sequence generated by the algorithm, we demonstrate that the limit point is a solution to the GNEP and the parameter becomes a constant after a finite iterations. We formulate the Karush-Kuhn-Tucker conditions for a penalized problem into a system of nonsmooth equations and demonstrate the nonsingularity of its Clarke’s generalized Jacobian at the KKT point under the so-called GNEP-Second Order Sufficient Condition. The nonsingularity facilitates the application of the smoothing Newton method for the global convergence and local quadratic rate. Finally, the numerical results are reported to show the effectiveness of the penalty method in solving generalized Nash equilibrium problem.
2012, 8(1): 67-86
doi: 10.3934/jimo.2012.8.67
+[Abstract](1868)
+[PDF](178.3KB)
Abstract:
In this paper, we consider the linear complementarity problem over Euclidean Jordan algebras with a Cartesian $P_*(\kappa)$-transformation, which is denoted by the Cartesian $P_*(\kappa)$-SCLCP. A smoothing algorithm is extended to solve the Cartesian $P_*(\kappa)$-SCLCP. We show that the algorithm is globally convergent if the problem concerned has a solution. In particular, we show that the algorithm is globally linearly convergent under a weak assumption.
In this paper, we consider the linear complementarity problem over Euclidean Jordan algebras with a Cartesian $P_*(\kappa)$-transformation, which is denoted by the Cartesian $P_*(\kappa)$-SCLCP. A smoothing algorithm is extended to solve the Cartesian $P_*(\kappa)$-SCLCP. We show that the algorithm is globally convergent if the problem concerned has a solution. In particular, we show that the algorithm is globally linearly convergent under a weak assumption.
2012, 8(1): 87-102
doi: 10.3934/jimo.2012.8.87
+[Abstract](2562)
+[PDF](471.2KB)
Abstract:
The Partitioning-Hub Location-Routing Problem (PHLRP) is a hub location problem involving graph partitioning and routing features. PHLRP consists of partitioning a given network into sub-networks, locating at least one hub in each sub-network and routing the traffic within the network at minimum cost. There are various important applications of PHLRP, such as in the deployment of network routing protocol problems and in the planning of freight distribution problems. We first present the formulation of this problem as an Binary Integer Linear Programming (BILP) and then investigate a new method based on DC (Difference of Convex functions) programming and DCA (DC Algorithms). Preliminary numerical results are compared with CPLEX, the best solver for BILP. These results show that the proposed algorithm is efficient.
The Partitioning-Hub Location-Routing Problem (PHLRP) is a hub location problem involving graph partitioning and routing features. PHLRP consists of partitioning a given network into sub-networks, locating at least one hub in each sub-network and routing the traffic within the network at minimum cost. There are various important applications of PHLRP, such as in the deployment of network routing protocol problems and in the planning of freight distribution problems. We first present the formulation of this problem as an Binary Integer Linear Programming (BILP) and then investigate a new method based on DC (Difference of Convex functions) programming and DCA (DC Algorithms). Preliminary numerical results are compared with CPLEX, the best solver for BILP. These results show that the proposed algorithm is efficient.
2012, 8(1): 103-115
doi: 10.3934/jimo.2012.8.103
+[Abstract](2235)
+[PDF](436.7KB)
Abstract:
This paper proposes a new heuristic, Tropical Cyclone-based Method (TCM), for solving global optimization problems with box constraints. TCM mimics the formation process of tropical cyclones in the atmosphere to move a set of sample points towards optimality. The formation of a tropical cyclone in nature is still not completely understood by people. Nevertheless, inspired by the known formation factors of a tropical cyclone, TCM is designed to seek optimal solutions by considering airflow, disturbance, and convection in order to traverse the solution space. Experimental results on some well-known nonlinear test functions are included. Compared with the well-known Electromagnetism-like Mechanism (EM), TCM is both effective and efficient for solving the reported test functions.
This paper proposes a new heuristic, Tropical Cyclone-based Method (TCM), for solving global optimization problems with box constraints. TCM mimics the formation process of tropical cyclones in the atmosphere to move a set of sample points towards optimality. The formation of a tropical cyclone in nature is still not completely understood by people. Nevertheless, inspired by the known formation factors of a tropical cyclone, TCM is designed to seek optimal solutions by considering airflow, disturbance, and convection in order to traverse the solution space. Experimental results on some well-known nonlinear test functions are included. Compared with the well-known Electromagnetism-like Mechanism (EM), TCM is both effective and efficient for solving the reported test functions.
2012, 8(1): 117-126
doi: 10.3934/jimo.2012.8.117
+[Abstract](2147)
+[PDF](386.4KB)
Abstract:
In this paper, we consider the $2$-catalog segmentation problem. For the disjoint version, we propose an approximation algorithm based on the non-uniform rotation technique using a semidefinite programming ($SDP$) relaxation. We give the performance curve depending on the ratio between the value of optimal SDP solution and the total weight. In this curve, the lowest point implies the approximation ratio is $0.7317$ which is the best ratio for the disjoint version until now. We also consider the performance curve of the joint version.
In this paper, we consider the $2$-catalog segmentation problem. For the disjoint version, we propose an approximation algorithm based on the non-uniform rotation technique using a semidefinite programming ($SDP$) relaxation. We give the performance curve depending on the ratio between the value of optimal SDP solution and the total weight. In this curve, the lowest point implies the approximation ratio is $0.7317$ which is the best ratio for the disjoint version until now. We also consider the performance curve of the joint version.
2012, 8(1): 127-139
doi: 10.3934/jimo.2012.8.127
+[Abstract](1917)
+[PDF](434.5KB)
Abstract:
This paper develops a general equilibrium model with two firms in cooperative R&D projects to investigate the optimal assignment of principalship and residual distribution strategies. We make a distinction between cooperative R&D effort and monitoring effort. When it is costly to sign contracts on R&D efforts under complete information, it may be optimal to let one firm purchase the rights to monitor and to direct, and claim full residual. Principalship is the purchase of these rights. These rights are limited residual rights of control over R&D actions. In the benchmark case of incomplete information, we have also explored how the optimal assignment of principalship distribution in cooperative R&D and partnership depends on the interaction between each member’s importance in cooperative R&D, the effectiveness of monitoring and the degree of R&D teamwork.
This paper develops a general equilibrium model with two firms in cooperative R&D projects to investigate the optimal assignment of principalship and residual distribution strategies. We make a distinction between cooperative R&D effort and monitoring effort. When it is costly to sign contracts on R&D efforts under complete information, it may be optimal to let one firm purchase the rights to monitor and to direct, and claim full residual. Principalship is the purchase of these rights. These rights are limited residual rights of control over R&D actions. In the benchmark case of incomplete information, we have also explored how the optimal assignment of principalship distribution in cooperative R&D and partnership depends on the interaction between each member’s importance in cooperative R&D, the effectiveness of monitoring and the degree of R&D teamwork.
2012, 8(1): 141-162
doi: 10.3934/jimo.2012.8.141
+[Abstract](2417)
+[PDF](583.4KB)
Abstract:
In this study, we consider an imperfect production system in which the manager not only faces the Economic Lot Scheduling Problem, but also needs to conduct multiple inspections during a production lot of any product. Inspection plays an important role in an imperfect production system since it saves the cost from producing and restoring defective items though it also incurs extra inspection cost at the same time. In this study, we employ the common cycle approach in which all the products share the same replenishment cycle, and adopt a consensus inspection policy. The focus of this study is to determine the optimal cycle time and an optimal production and inspection schedule that minimize the total cost per unit time. We formulate a mathematical model in which we take into accounts both the production capacity and inspection capacity constraints. Also, we conduct full theoretical analysis and propose an effective search algorithm for solving an optimal solution. Our numerical experiments demonstrate the effectiveness of the proposed search algorithm.
In this study, we consider an imperfect production system in which the manager not only faces the Economic Lot Scheduling Problem, but also needs to conduct multiple inspections during a production lot of any product. Inspection plays an important role in an imperfect production system since it saves the cost from producing and restoring defective items though it also incurs extra inspection cost at the same time. In this study, we employ the common cycle approach in which all the products share the same replenishment cycle, and adopt a consensus inspection policy. The focus of this study is to determine the optimal cycle time and an optimal production and inspection schedule that minimize the total cost per unit time. We formulate a mathematical model in which we take into accounts both the production capacity and inspection capacity constraints. Also, we conduct full theoretical analysis and propose an effective search algorithm for solving an optimal solution. Our numerical experiments demonstrate the effectiveness of the proposed search algorithm.
2012, 8(1): 163-178
doi: 10.3934/jimo.2012.8.163
+[Abstract](2161)
+[PDF](368.9KB)
Abstract:
In this paper we apply a recently proposed Lagrange Dual Method (LDM) to design a new Sparse Representation-based Classification (LDM-SRC) algorithm for robust face recognition problem. The proposed approach improves the efficiency of the SRC algorithm significantly. The proposed algorithm has the following advantages: (1) it employs the LDM $\ell_1$-solver to find solution of the $\ell_1$-norm minimization problem, which is much faster than other state-of-the-art $\ell_1$-solvers, e.g. $\ell_1$-magic and $\ell_1-\ell_2$. (2) The LDM $\ell_1$-solver utilizes a new Lagrange-dual reformulation of the original $\ell_1$-norm minimization problem, not only reducing the problem size when the dimension of training image data is much less than the number of training samples, but also making the dual problem become smooth and convex. Therefore it converts the non-smooth $\ell_1$-norm minimization problem into a sequence of smooth optimization problems. (3) The LDM-SRC algorithm can maintain good recognition accuracy whilst reducing the computational time dramatically. Experimental results are presented on some benchmark face databases.
In this paper we apply a recently proposed Lagrange Dual Method (LDM) to design a new Sparse Representation-based Classification (LDM-SRC) algorithm for robust face recognition problem. The proposed approach improves the efficiency of the SRC algorithm significantly. The proposed algorithm has the following advantages: (1) it employs the LDM $\ell_1$-solver to find solution of the $\ell_1$-norm minimization problem, which is much faster than other state-of-the-art $\ell_1$-solvers, e.g. $\ell_1$-magic and $\ell_1-\ell_2$. (2) The LDM $\ell_1$-solver utilizes a new Lagrange-dual reformulation of the original $\ell_1$-norm minimization problem, not only reducing the problem size when the dimension of training image data is much less than the number of training samples, but also making the dual problem become smooth and convex. Therefore it converts the non-smooth $\ell_1$-norm minimization problem into a sequence of smooth optimization problems. (3) The LDM-SRC algorithm can maintain good recognition accuracy whilst reducing the computational time dramatically. Experimental results are presented on some benchmark face databases.
2012, 8(1): 179-187
doi: 10.3934/jimo.2012.8.179
+[Abstract](2336)
+[PDF](317.9KB)
Abstract:
By constructing a corresponding Nash map, we prove that every infinite game with compact metrizable sets of strategies and continuous payoffs has such a topological essential component that contains a minimal payoff-wise essential set containing a stable set, and deduce that every topological essential equilibrium is payoff-wise essential and so is perfect.
By constructing a corresponding Nash map, we prove that every infinite game with compact metrizable sets of strategies and continuous payoffs has such a topological essential component that contains a minimal payoff-wise essential set containing a stable set, and deduce that every topological essential equilibrium is payoff-wise essential and so is perfect.
2012, 8(1): 189-227
doi: 10.3934/jimo.2012.8.189
+[Abstract](2649)
+[PDF](849.2KB)
Abstract:
This paper aims to study convex analysis on some “generalized domains,” in particular, the domain of the product of closed subsets of reals. We introduce the basic concepts and derive analytic properties regarding convex subsets of mixed domains and convex functions defined on convex sets in mixed domains. The results obtained may open an avenue for modeling and solving a new type of optimization problems that involve both discrete and continuous variables at the same time.
This paper aims to study convex analysis on some “generalized domains,” in particular, the domain of the product of closed subsets of reals. We introduce the basic concepts and derive analytic properties regarding convex subsets of mixed domains and convex functions defined on convex sets in mixed domains. The results obtained may open an avenue for modeling and solving a new type of optimization problems that involve both discrete and continuous variables at the same time.
2012, 8(1): 229-242
doi: 10.3934/jimo.2012.8.229
+[Abstract](1941)
+[PDF](227.8KB)
Abstract:
This paper presents a detailed proof of the triality theorem for a class of fourth-order polynomial optimization problems. The method is based on linear algebra but it solves an open problem on the double-min duality. Results show that the triality theory holds strongly in the tri-duality form for our problem if the primal problem and its canonical dual have the same dimension; otherwise, both the canonical min-max duality and the double-max duality still hold strongly, but the double-min duality holds weakly in a symmetrical form. Some numerical examples are presented to illustrate that this theory can be used to identify not only the global minimum, but also the local minimum and local maximum.
This paper presents a detailed proof of the triality theorem for a class of fourth-order polynomial optimization problems. The method is based on linear algebra but it solves an open problem on the double-min duality. Results show that the triality theory holds strongly in the tri-duality form for our problem if the primal problem and its canonical dual have the same dimension; otherwise, both the canonical min-max duality and the double-max duality still hold strongly, but the double-min duality holds weakly in a symmetrical form. Some numerical examples are presented to illustrate that this theory can be used to identify not only the global minimum, but also the local minimum and local maximum.
2012, 8(1): 243-261
doi: 10.3934/jimo.2012.8.243
+[Abstract](2674)
+[PDF](384.2KB)
Abstract:
Firms often face the problem of deciding how to share scarce resources between a set of candidate projects and simultaneously schedule them; that is, how to choose a project portfolio. Usually, this decision-making process is carried out in groups, and all the individuals’ preferences have to be considered simultaneously to determine an acceptable solution. We propose a two-step approach to assist groups in making this crucial decision. In the first step, a multiobjective model is solved that takes into account the characteristics of the organization (private or public) as well as the many key factors required by the decision group, such as available resources, synergies between projects, and other constraints to suitably select and schedule efficient project portfolios. Usually, the decision-making group has to choose from among a large number of efficient solutions. In the second step, the decision-making group refines the potential solutions. This second step is characterised by a flexible selection of weights, which helps to rank the set of efficient solutions and maximise consensus between the group members.
Firms often face the problem of deciding how to share scarce resources between a set of candidate projects and simultaneously schedule them; that is, how to choose a project portfolio. Usually, this decision-making process is carried out in groups, and all the individuals’ preferences have to be considered simultaneously to determine an acceptable solution. We propose a two-step approach to assist groups in making this crucial decision. In the first step, a multiobjective model is solved that takes into account the characteristics of the organization (private or public) as well as the many key factors required by the decision group, such as available resources, synergies between projects, and other constraints to suitably select and schedule efficient project portfolios. Usually, the decision-making group has to choose from among a large number of efficient solutions. In the second step, the decision-making group refines the potential solutions. This second step is characterised by a flexible selection of weights, which helps to rank the set of efficient solutions and maximise consensus between the group members.
2012, 8(1): 263-269
doi: 10.3934/jimo.2012.8.263
+[Abstract](2061)
+[PDF](301.2KB)
Abstract:
Li et al. [Journal of Industrial and Management Optimization 5 (2009) 867-880] develop a model to determine an optimal replenishment policy with defective items and shortage backlogging under conditions of permissible delay in payments. They used the optimization technique based on differential calculus to determine an optimal replenishment policy. The main purpose of this paper is to solve the inventory problem in Li et al. (2009) by the algebraic method to simplify the solution procedures.
Li et al. [Journal of Industrial and Management Optimization 5 (2009) 867-880] develop a model to determine an optimal replenishment policy with defective items and shortage backlogging under conditions of permissible delay in payments. They used the optimization technique based on differential calculus to determine an optimal replenishment policy. The main purpose of this paper is to solve the inventory problem in Li et al. (2009) by the algebraic method to simplify the solution procedures.
2019 Impact Factor: 1.366
Authors
Editors
Referees
Librarians
Email Alert
Add your name and e-mail address to receive news of forthcoming issues of this journal:
[Back to Top]