ISSN:
1547-5816
eISSN:
1553-166X
All Issues
Journal of Industrial & Management Optimization
April 2010 , Volume 6 , Issue 2
Select all articles
Export/Reference:
2010, 6(2): 269-282
doi: 10.3934/jimo.2010.6.269
+[Abstract](2234)
+[PDF](315.0KB)
Abstract:
The single machine semi-online scheduling problem with the objective of minimizing total completion time is investigated with the assumption that the ratio of the longest to the shortest processing time is not greater than a constant $\gamma$. A semi-online algorithm is designed and its competitive ratio is proven to be $1+ \frac{\gamma - 1}{1 + \sqrt {1 + \gamma (\gamma - 1)}}$. The competitive analysis method is as following: it starts from an arbitrary instance and modifies the instance towards the possible structure of the worst-case instance with respect to the given online algorithm. The modification guarantees that the performance ratio does not decrease. Eventually, it comes up with a relatively simple instance with a special structure, whose performance ratio can be directly analyzed and serves as an upper bound on the competitive ratio.
The single machine semi-online scheduling problem with the objective of minimizing total completion time is investigated with the assumption that the ratio of the longest to the shortest processing time is not greater than a constant $\gamma$. A semi-online algorithm is designed and its competitive ratio is proven to be $1+ \frac{\gamma - 1}{1 + \sqrt {1 + \gamma (\gamma - 1)}}$. The competitive analysis method is as following: it starts from an arbitrary instance and modifies the instance towards the possible structure of the worst-case instance with respect to the given online algorithm. The modification guarantees that the performance ratio does not decrease. Eventually, it comes up with a relatively simple instance with a special structure, whose performance ratio can be directly analyzed and serves as an upper bound on the competitive ratio.
2010, 6(2): 283-297
doi: 10.3934/jimo.2010.6.283
+[Abstract](1729)
+[PDF](220.7KB)
Abstract:
This paper is devoted to the study of a one-sector stochastic growth model with the depreciation factor of the output and with bounded and unbounded utility, in which the shocks are allowed to be bounded or unbounded. Under certain assumptions, the existence of a unique optimal policy function for the model is shown to be true and the existence of an invariant distribution for the output process is confirmed.
This paper is devoted to the study of a one-sector stochastic growth model with the depreciation factor of the output and with bounded and unbounded utility, in which the shocks are allowed to be bounded or unbounded. Under certain assumptions, the existence of a unique optimal policy function for the model is shown to be true and the existence of an invariant distribution for the output process is confirmed.
2010, 6(2): 299-313
doi: 10.3934/jimo.2010.6.299
+[Abstract](1664)
+[PDF](212.2KB)
Abstract:
This paper proposes a trial-and-error implementation of marginal-cost pricing on transportation networks in the absence of both demand functions and travel time functions. Assuming that the corresponding link flows for given trial tolls are observable and that the approximations of the exact travel time functions are provided, the new trial is obtained via solving a system of equations. The new trial-and-error implementation is proved to be convergent globally under mild assumptions, and its improvements over existing methods are verified by some numerical experiments.
This paper proposes a trial-and-error implementation of marginal-cost pricing on transportation networks in the absence of both demand functions and travel time functions. Assuming that the corresponding link flows for given trial tolls are observable and that the approximations of the exact travel time functions are provided, the new trial is obtained via solving a system of equations. The new trial-and-error implementation is proved to be convergent globally under mild assumptions, and its improvements over existing methods are verified by some numerical experiments.
2010, 6(2): 315-331
doi: 10.3934/jimo.2010.6.315
+[Abstract](1767)
+[PDF](282.0KB)
Abstract:
This paper presents for the first time how to easily incorporate facts devices in an optimal active power flow model such that an efficient interior-point method may be applied. The optimal active power flow model is based on a network flow approach instead of the traditional nodal formulation that allows the use of an efficiently predictor-corrector interior point method speed up by sparsity exploitation. The mathematical equivalence between the network flow and the nodal models is addressed, as well as the computational advantages of the former considering the solution by interior point methods. The adequacy of the network flow model for representing facts devices is presented and illustrated on a small 5-bus system. The model was implemented using Matlab and its performance was evaluated with the 3,397-bus and 4,075- branch Brazilian power system which show the robustness and efficiency of the formulation proposed. The numerical results also indicate an efficient tool for optimal active power flow that is suitable for incorporating facts devices.
This paper presents for the first time how to easily incorporate facts devices in an optimal active power flow model such that an efficient interior-point method may be applied. The optimal active power flow model is based on a network flow approach instead of the traditional nodal formulation that allows the use of an efficiently predictor-corrector interior point method speed up by sparsity exploitation. The mathematical equivalence between the network flow and the nodal models is addressed, as well as the computational advantages of the former considering the solution by interior point methods. The adequacy of the network flow model for representing facts devices is presented and illustrated on a small 5-bus system. The model was implemented using Matlab and its performance was evaluated with the 3,397-bus and 4,075- branch Brazilian power system which show the robustness and efficiency of the formulation proposed. The numerical results also indicate an efficient tool for optimal active power flow that is suitable for incorporating facts devices.
Convergence and error bound of a D-gap function based Newton-type algorithm for equilibrium
problems
2010, 6(2): 333-346
doi: 10.3934/jimo.2010.6.333
+[Abstract](1931)
+[PDF](188.8KB)
Abstract:
The D-gap function approach has been adopted for solving variational inequality problems. In this paper, we extend the approach for solving equilibrium problems. From the theoretical point, we study the convergence and global error bound of a D-gap function based Newton method.
A general equilibrium problem is first formulated as an equivalent unconstrained minimization problem using a new D-gap function. Then the conditions of "strict monotonicity" and "strong monotonicity" for equilibrium problems are introduced. Under the strict monotonicity condition, it is shown that a stationary point of the unconstrained minimization problem provides a solution to the original equilibrium problem. Without the assumption of Lipschitz continuity, we further prove that strong monotonicity condition guarantees the boundedness of the level sets of the new D-gap function and derive error bounds on the level sets. Combining the strict monotonicity and strong monotonicity conditions, we show the existence and uniqueness of a solution to the equilibrium problem, and establish the global convergence property of the proposed algorithm with a global error bound.
The D-gap function approach has been adopted for solving variational inequality problems. In this paper, we extend the approach for solving equilibrium problems. From the theoretical point, we study the convergence and global error bound of a D-gap function based Newton method.
A general equilibrium problem is first formulated as an equivalent unconstrained minimization problem using a new D-gap function. Then the conditions of "strict monotonicity" and "strong monotonicity" for equilibrium problems are introduced. Under the strict monotonicity condition, it is shown that a stationary point of the unconstrained minimization problem provides a solution to the original equilibrium problem. Without the assumption of Lipschitz continuity, we further prove that strong monotonicity condition guarantees the boundedness of the level sets of the new D-gap function and derive error bounds on the level sets. Combining the strict monotonicity and strong monotonicity conditions, we show the existence and uniqueness of a solution to the equilibrium problem, and establish the global convergence property of the proposed algorithm with a global error bound.
2010, 6(2): 347-361
doi: 10.3934/jimo.2010.6.347
+[Abstract](1956)
+[PDF](193.3KB)
Abstract:
In this paper, we study multi-parametric sensitivity analysis for programming problems with the piecewise linear fractional objective function using the concept of maximum volume in the tolerance region. We construct critical regions (the set of parameters values which the coefficients matrix of the problem (PLFP) may vary while still retaining the same optimal basis B.) for simultaneous and independent perturbations of one row or one column of the constraint matrix in the given problem. Necessary and sufficient conditions are derived to classify perturbation parameters as 'focal' and 'non-focal'. Non-focal parameters can be deleted from the analysis, because of their low sensitivity in practice. Theoretical results are illustrated with the help of a numerical example.
In this paper, we study multi-parametric sensitivity analysis for programming problems with the piecewise linear fractional objective function using the concept of maximum volume in the tolerance region. We construct critical regions (the set of parameters values which the coefficients matrix of the problem (PLFP) may vary while still retaining the same optimal basis B.) for simultaneous and independent perturbations of one row or one column of the constraint matrix in the given problem. Necessary and sufficient conditions are derived to classify perturbation parameters as 'focal' and 'non-focal'. Non-focal parameters can be deleted from the analysis, because of their low sensitivity in practice. Theoretical results are illustrated with the help of a numerical example.
2010, 6(2): 363-380
doi: 10.3934/jimo.2010.6.363
+[Abstract](1751)
+[PDF](245.0KB)
Abstract:
Based on the KK smoothing function, we introduce a regularized one-parametric class of smoothing functions and show that it is coercive under suitable assumptions. By making use of the introduced regularized one-parametric class of smoothing functions, we investigate a smoothing Newton algorithm for solving the generalized complementarity problems over symmetric cones (GSCCP), where a nonmonotone line search scheme is used. We show that the algorithm is globally and locally superlinearly convergent under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool in our analysis.
Based on the KK smoothing function, we introduce a regularized one-parametric class of smoothing functions and show that it is coercive under suitable assumptions. By making use of the introduced regularized one-parametric class of smoothing functions, we investigate a smoothing Newton algorithm for solving the generalized complementarity problems over symmetric cones (GSCCP), where a nonmonotone line search scheme is used. We show that the algorithm is globally and locally superlinearly convergent under suitable assumptions. The theory of Euclidean Jordan algebras is a basic tool in our analysis.
2010, 6(2): 381-392
doi: 10.3934/jimo.2010.6.381
+[Abstract](1959)
+[PDF](162.9KB)
Abstract:
This paper deals with higher-order sensitivity analysis in nonconvex vector optimization. By virtue of higher-order adjacent derivatives introduced in (Aubin and Frankowska, Set-valued Analysis, Birkh$\ddot{a}$user, Boston, 1990), relationships between higher-order derivatives of a set-valued map and its profile map are discussed. Some results concerning higher-order sensitivity analysis are obtained in nonconvex vector optimization.
This paper deals with higher-order sensitivity analysis in nonconvex vector optimization. By virtue of higher-order adjacent derivatives introduced in (Aubin and Frankowska, Set-valued Analysis, Birkh$\ddot{a}$user, Boston, 1990), relationships between higher-order derivatives of a set-valued map and its profile map are discussed. Some results concerning higher-order sensitivity analysis are obtained in nonconvex vector optimization.
2010, 6(2): 393-400
doi: 10.3934/jimo.2010.6.393
+[Abstract](2030)
+[PDF](140.1KB)
Abstract:
The gap constraint used in A. A. Moreb, Spline technique for modeling roadway profile to minimize earthwork cost, J. Ind. Man. & Opt., 5 (2) (2009), 275-283 introduces unnecessary errors, while the slope constraint may be violated for second- and higher-order splines. In this note we amend the gap constraint, while maintaining the linearity of the model. We also present an improved slope constraint for linear and quadratic splines, and show that it becomes nonlinear for cubic and higher order splines. The improvements also apply to A. Moreb, M. Aljohani, Quadratic representation for roadway profile that minimizes earthwork cost, J. Sys. Sci. & Sys. Eng., 13 (2) (2004), 245-252.
The gap constraint used in A. A. Moreb, Spline technique for modeling roadway profile to minimize earthwork cost, J. Ind. Man. & Opt., 5 (2) (2009), 275-283 introduces unnecessary errors, while the slope constraint may be violated for second- and higher-order splines. In this note we amend the gap constraint, while maintaining the linearity of the model. We also present an improved slope constraint for linear and quadratic splines, and show that it becomes nonlinear for cubic and higher order splines. The improvements also apply to A. Moreb, M. Aljohani, Quadratic representation for roadway profile that minimizes earthwork cost, J. Sys. Sci. & Sys. Eng., 13 (2) (2004), 245-252.
2010, 6(2): 401-410
doi: 10.3934/jimo.2010.6.401
+[Abstract](2435)
+[PDF](155.7KB)
Abstract:
We study the first-order behavior of the optimal value function in a parametric discrete optimal control problem with linear constraints and a nonconvex cost function. By establishing a new result on the Fréchet subdifferential of optimal value functions of parametric mathematical programming problems, we obtain some formulae on the Fréchet subdifferential of optimal value functions in parametric discrete optimal control problems which complement results due to Kien et al. [3].
We study the first-order behavior of the optimal value function in a parametric discrete optimal control problem with linear constraints and a nonconvex cost function. By establishing a new result on the Fréchet subdifferential of optimal value functions of parametric mathematical programming problems, we obtain some formulae on the Fréchet subdifferential of optimal value functions in parametric discrete optimal control problems which complement results due to Kien et al. [3].
2010, 6(2): 411-423
doi: 10.3934/jimo.2010.6.411
+[Abstract](2113)
+[PDF](199.0KB)
Abstract:
We consider generalized complementarity problem GCP$(f,g)$ when the underlying functions $f$ and $g$ are $H$-differentiable. We describe $H$-differentials of some GCP functions and their merit functions. We give some conditions on the $H$-differentials of the given functions under which minimizing a merit function corresponding to such functions leads to a solution of the generalized complementarity problem. Further, we give some conditions on the functions $f$ and $g$ to get a solution of GCP$(f,g)$ by introducing the concepts of relative monotonicity and P0-property and their variants. Our results further give a unified/generalization treatment of such results for the nonlinear complementarity problem when the underlying function is $C^1$ , semismooth, and locally Lipschitzian.
We consider generalized complementarity problem GCP$(f,g)$ when the underlying functions $f$ and $g$ are $H$-differentiable. We describe $H$-differentials of some GCP functions and their merit functions. We give some conditions on the $H$-differentials of the given functions under which minimizing a merit function corresponding to such functions leads to a solution of the generalized complementarity problem. Further, we give some conditions on the functions $f$ and $g$ to get a solution of GCP$(f,g)$ by introducing the concepts of relative monotonicity and P0-property and their variants. Our results further give a unified/generalization treatment of such results for the nonlinear complementarity problem when the underlying function is $C^1$ , semismooth, and locally Lipschitzian.
2010, 6(2): 425-433
doi: 10.3934/jimo.2010.6.425
+[Abstract](1763)
+[PDF](153.0KB)
Abstract:
The traditional economic order quantity (EOQ) and/or economic production quantity (EPQ) have been extensively examined and continually modified so as to accommodate specific business needs and market environments. In this paper, the learning effect of setup costs is incorporated into an inventory replenishment system where the demand is assumed to be deterministically constant in a finite planning horizon. The inventory replenishment system with learning considerations of setup costs is formulated as a mixed-integer cost minimization problem in which the number of replenishments and the replenishment time points in the planning horizon are regarded as decision variables. We first show that the time interval between any two successive replenishments should be equal. Then, the conditions of the optimal solution for the proposed problem are derived. Finally, numerical examples are provided to illustrate the features of the proposed problem.
The traditional economic order quantity (EOQ) and/or economic production quantity (EPQ) have been extensively examined and continually modified so as to accommodate specific business needs and market environments. In this paper, the learning effect of setup costs is incorporated into an inventory replenishment system where the demand is assumed to be deterministically constant in a finite planning horizon. The inventory replenishment system with learning considerations of setup costs is formulated as a mixed-integer cost minimization problem in which the number of replenishments and the replenishment time points in the planning horizon are regarded as decision variables. We first show that the time interval between any two successive replenishments should be equal. Then, the conditions of the optimal solution for the proposed problem are derived. Finally, numerical examples are provided to illustrate the features of the proposed problem.
2010, 6(2): 435-451
doi: 10.3934/jimo.2010.6.435
+[Abstract](2112)
+[PDF](353.9KB)
Abstract:
A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows and multiple vehicles is considered in this paper. The first stage uses simulated annealing algorithm to decrease the number of used vehicles, the second stage uses tabu search to decrease the total travel cost. Experimental results show the effectiveness of the algorithm which has produced many new best solutions on problems within 600 customers. In particular, it has improved 45% and 81.7% of the best solutions on the 200 and 600-customer benchmarks, sometimes by as much as 3 vehicles. These results further confirm the benefits of two-stage approaches in vehicle routing problems.
A two-stage hybrid meta-heuristic for pickup and delivery vehicle routing problem with time windows and multiple vehicles is considered in this paper. The first stage uses simulated annealing algorithm to decrease the number of used vehicles, the second stage uses tabu search to decrease the total travel cost. Experimental results show the effectiveness of the algorithm which has produced many new best solutions on problems within 600 customers. In particular, it has improved 45% and 81.7% of the best solutions on the 200 and 600-customer benchmarks, sometimes by as much as 3 vehicles. These results further confirm the benefits of two-stage approaches in vehicle routing problems.
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]