Online stochastic reservation systems

This paper considers online stochastic reservation problems, where requests come online and must be dynamically allocated to limited resources in order to maximize profit. Multi-knapsack problems with or without overbooking are examples of such online stochastic reservations. The paper studies how to adapt the online stochastic framework and the consensus and regret algorithms proposed earlier to online stochastic reservation systems. On the theoretical side, it presents a constant sub-optimality approximation of multi-knapsack problems, leading to a regret algorithm that evaluates each scenario with a single mathematical programming optimization followed by a small number of dynamic programs for one-dimensional knapsacks. It also proposes several integer programming models for handling cancellations and proves their equivalence. On the experimental side, the paper demonstrates the effectiveness of the regret algorithm on multi-knapsack problems (with and without overbooking) based on the benchmarks proposed earlier.     

Approximation of min–max and min–max regret versions of some combinatorial optimization problems

This paper investigates, for the first time in the literature, the approximation of min–max (regret) versions of classical problems like shortest path, minimum spanning tree, and knapsack. For a constant number of scenarios, we establish fully polynomial-time approximation schemes for the min–max versions of these problems, using relationships between multi-objective and min–max optimization. Using dynamic programming and classical trimming techniques, we construct a fully polynomial-time approximation scheme for min–max regret shortest path. We also establish a fully polynomial-time approximation scheme for min–max regret spanning tree and prove that min–max regret knapsack is not at all approximable. For a non-constant number of scenarios, in which case min–max and min–max regret versions of polynomial-time solvable problems usually become strongly NP-hard, non-approximability results are provided for min–max (regret) versions of shortest path and spanning tree.     

A 2-approximation for minmax regret problems via a mid-point scenario optimal solution

In this note, a 2-approximation method for minmax regret optimization problems is developed which extends the work of Kasperski and Zielinski [A. Kasperski, P. Zielinski, An approximation algorithm for interval data minmax regret combinatorial optimization problems, Information Processing Letters 97 (2006) 177-180] from finite to compact constraint sets.     

General approximation schemes for min–max (regret) versions of some (pseudo-)polynomial problems

While the complexity of min–max and min–max regret versions of most classical combinatorial optimization problems has been thoroughly investigated, there are very few studies about their approximation. For a bounded number of scenarios, we establish general approximation schemes which can be used for min–max and min–max regret versions of some polynomial or pseudo-polynomial problems. Applying these schemes to shortest path, minimum spanning tree, minimum weighted perfect matching on planar graphs, and knapsack problems, we obtain fully polynomial-time approximation schemes with better running times than the ones previously presented in the literature.     

On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data

The general problem of minimizing the maximal regret in combinatorial optimization problems with interval costs is considered. Some results are proven that allow to obtain a fully polynomial time approximation scheme (FPTAS) for the problem under the assumption that a pseudopolynomial algorithm is given.     

考虑后悔规避与匹配意愿的直觉模糊双边匹配方法

针对直觉模糊偏好信息的双边匹配问题,提出一种考虑匹配主体后悔规避心理行为和匹配意愿的双边匹配方法。首先,将双边主体的直觉模糊偏好信息转化为效用值;然后,依据后悔理论的思想,通过一方主体将另一方主体进行两两比较计算每个主体的后悔值和欣喜值,进而计算每个主体的总体后悔欣喜值,构建匹配满意度计算规则,建立双边匹配多目标优化模型,通过分析现有匹配意愿系数确定方法的不足,给出一种新的匹配意愿系数确定方法,在此基础上,考虑双边主体的匹配意愿,采用线性加权法将多目标优化模型转化为单目标规划模型进行求解,获得双边匹配结果;最后,通过一个算例验证了提出方法的可行性和有效性。     

An interval uncertain optimization method for vehicle suspensions using Chebyshev metamodels

This paper proposes a new design optimization framework for suspension systems considering the kinematic characteristics, such as the camber angle, caster angle, kingpin inclination angle, and toe angle in the presence of uncertainties. The coordinates of rear inner hardpoints of upper control arm and lower control arm of double wishbone suspension are considered as the design variables, as well as the uncertain parameters. In this way, the actual values of the design variables will vary surrounding their nominal values. The variations result in uncertainties that are described as interval variables with lower and upper bounds. The kinematic model of the suspension is developed in software ADAMS. A high-order response surface model using the zeros of Chebyshev polynomials as sampling points is established, termed as Chebyshev metamodel, to approximate the kinematic model. The Chebyshev meta-model is expected to provide higher approximation accuracy. Interval uncertain optimization problems usually involve a nested computationally expensive double-loop optimization process, in which the inner loop optimization is to calculate the bounds of the interval design functions, while the outer loop is to search the optimum for the deterministic optimization problem. To reduce the computational cost, the interval arithmetic is introduced in the inner loop to improve computational efficiency without compromising numerical accuracy. The numerical results show the effectiveness of the proposed design method.     

Robust Adaptive Fuzzy Identification of Time-Varying Processes with Uncertain Data. Handling Uncertainties in the Physical Fitness Fuzzy Approximation with Real World Medical Data: An Application

This study considers the problem of Robust Fuzzy approximation of a time-varying nonlinear process in the presence of uncertainties in the identification data using a Sugeno Fuzzy System while maintaining the interpretability of the fuzzy model during identification. A recursive procedure for the estimation of fuzzy parameters is proposed based on solving local optimization problem that attempt to minimize the worst-case effect of data uncertainties on approximation performance. To illustrate the approach, several simulation studies on numerical examples are provided. The developed scheme was applied to handle the vagueness, ambiguity and uncertainty inherently present in the general notion of a Medical Expert about Physical Fitness based on a set of various Physiological parameters measurements.     

Computing and minimizing the relative regret in combinatorial optimization with interval data

We consider combinatorial optimization problems with uncertain parameters of the objective function, where for each uncertain parameter an interval estimate is known. It is required to find a solution that minimizes the worst-case relative regret. For minmax relative regret versions of some subset-type problems, where feasible solutions are subsets of a finite ground set and the objective function represents the total weight of elements of a feasible solution, and for the minmax relative regret version of the problem of scheduling n jobs on a single machine to minimize the total completion time, we present a number of structural, algorithmic, and complexity results. Many of the results are based on generalizing and extending ideas and approaches from absolute regret minimization to the relative regret case.     

Global resonance optimization analysis of nonlinear mechanical systems: Application to the uncertainty quantification problems in rotor dynamics

An efficient method to obtain the worst quasi-periodic vibration response of nonlinear dynamical systems with uncertainties is presented. Based on the multi-dimensional harmonic balance method, a constrained, nonlinear optimization problem with the nonlinear equality constraints is derived. The MultiStart optimization algorithm is then used to optimize the vibration response within the specified range of physical parameters. In order to illustrate the efficiency and ability of the proposed method, several numerical examples are illustrated. The proposed method is then applied to a rotor system with multiple frequency excitations (unbalance and support) under several physical parameters uncertainties. Numerical examples show that the proposed approach is valid and effective for analyzing strongly nonlinear vibration problems with different types of nonlinearities in the presence of uncertainties.     

Robust optimization analysis for multiple attribute decision making problems with imprecise information

This paper considers ranking decision alternatives under multiple attributes with imprecise information on both attribute weights and alternative ratings. It is demonstrated that regret results from the decision maker??s inadequate knowledge about the true scenario to occur. Potential optimality analysis is a traditional method to evaluate alternatives with imprecise information. The essence of this approach is to identify any alternative that outperforms the others in its best-case scenario. Our analysis shows that potential optimality analysis is optimistic in nature and may lead to a significant loss if an unfavorable scenario occurs. We suggest a robust optimization analysis approach that ranks alternatives in terms of their worst-case absolute or relative regret. A robust optimal alternative performs reasonably well in all scenarios and is shown to be desirable for a risk-concerned decision maker. Linear programming models are developed to check robust optimality.     

Min–max and min–max (relative) regret approaches to representatives selection problem

The following optimization problem is studied. There are several sets of integer positive numbers whose values are uncertain. The problem is to select one representative of each set such that the sum of the selected numbers is minimum. The uncertainty is modeled by discrete and interval scenarios, and the min?Cmax and min?Cmax (relative) regret approaches are used for making a selection decision. The arising min?Cmax, min?Cmax regret and min?Cmax relative regret optimization problems are shown to be polynomially solvable for interval scenarios. For discrete scenarios, they are proved to be NP-hard in the strong sense if the number of scenarios is part of the input. If it is part of the problem type, then they are NP-hard in the ordinary sense, pseudo-polynomially solvable by a dynamic programming algorithm and possess an FPTAS. This study is motivated by the problem of selecting tools of minimum total cost in the design of a production line.     

Hard uncertainties in multiobjective layout optimization of photovoltaic power plants

This paper describes how to treat hard uncertainties defined by so-called uncertainty maps in multiobjective optimization problems. For the uncertainty map being set-valued, a Taylor formula is shown under appropriate assumptions. The hard uncertainties are modeled using parametric set optimization problems for which a scalarization result is given. The presented new approach for the solution of multiobjective optimization problems with hard uncertainties is then applied to the layout optimization of photovoltaic power plants. Since good weather forecasts are difficult to obtain for future years, weather data are really hard uncertainties arising in the planning process. Numerical results are presented for a real-world problem on the Galapagos island Isabela.     

Computational strategies for non-convex multistage MINLP models with decision-dependent uncertainty and gradual uncertainty resolution

In many planning problems under uncertainty the uncertainties are decision-dependent and resolve gradually depending on the decisions made. In this paper, we address a generic non-convex MINLP model for such planning problems where the uncertain parameters are assumed to follow discrete distributions and the decisions are made on a discrete time horizon. In order to account for the decision-dependent uncertainties and gradual uncertainty resolution, we propose a multistage stochastic programming model in which the non-anticipativity constraints in the model are not prespecified but change as a function of the decisions made. Furthermore, planning problems consist of several scenario subproblems where each subproblem is modeled as a nonconvex mixed-integer nonlinear program. We propose a solution strategy that combines global optimization and outer-approximation in order to optimize the planning decisions. We apply this generic problem structure and the proposed solution algorithm to several planning problems to illustrate the efficiency of the proposed method with respect to the method that uses only global optimization.     

Composite Nonsmooth Optimization Using Approximate Generalized Gradient Vectors

A new approximation method is presented for directly minimizing a composite nonsmooth function that is locally Lipschitzian. This method approximates only the generalized gradient vector, enabling us to use directly well-developed smooth optimization algorithms for solving composite nonsmooth optimization problems. This generalized gradient vector is approximated on each design variable coordinate by using only the active components of the subgradient vectors; then, its usability is validated numerically by the Pareto optimum concept. In order to show the performance of the proposed method, we solve four academic composite nonsmooth optimization problems and two dynamic response optimization problems with multicriteria. Specifically, the optimization results of the two dynamic response optimization problems are compared with those obtained by three typical multicriteria optimization strategies such as the weighting method, distance method, and min–max method, which introduces an artificial design variable in order to replace the max-value cost function with additional inequality constraints. The comparisons show that the proposed approximation method gives more accurate and efficient results than the other methods.     

Ultraspherical Integral Method for Optimal Control Problems Governed by Ordinary Differential Equations

In this paper an ultraspherical integral method is proposed to solve optimal control problems governed by ordinary differential equations. Ultraspherical approximation method reduced the problem to a constrained optimization problem. Penalty leap frog method is presented to solve the resulting constrained optimization problem. Error estimates for the ultraspherical approximations are derived and a technique that gives an optimal approximation of the problems is introduced. Numerical results are included to confirm the efficiency and accuracy of the method.     

A convexification method for a class of global optimization problems with applications to reliability optimization

A convexification method is proposed for solving a class of global optimization problems with certain monotone properties. It is shown that this class of problems can be transformed into equivalent concave minimization problems using the proposed convexification schemes. An outer approximation method can then be used to find the global solution of the transformed problem. Applications to mixed-integer nonlinear programming problems arising in reliability optimization of complex systems are discussed and satisfactory numerical results are presented.     

Approximation algorithms for nonnegative polynomial optimization problems over unit spheres

We consider approximation algorithms for nonnegative polynomial optimization problems over unit spheres. These optimization problems have wide applications e.g., in signal and image processing, high order statistics, and computer vision. Since these problems are NP-hard, we are interested in studying on approximation algorithms. In particular, we propose some polynomial-time approximation algorithms with new approximation bounds. In addition, based on these approximation algorithms, some efficient algorithms are presented and numerical results are reported to show the efficiency of our proposed algorithms.     

Robust optimization approximation for joint chance constrained optimization problem

Chance constraint is widely used for modeling solution reliability in optimization problems with uncertainty. Due to the difficulties in checking the feasibility of the probabilistic constraint and the non-convexity of the feasible region, chance constrained problems are generally solved through approximations. Joint chance constrained problem enforces that several constraints are satisfied simultaneously and it is more complicated than individual chance constrained problem. This work investigates the tractable robust optimization approximation framework for solving the joint chance constrained problem. Various robust counterpart optimization formulations are derived based on different types of uncertainty set. To improve the quality of robust optimization approximation, a two-layer algorithm is proposed. The inner layer optimizes over the size of the uncertainty set, and the outer layer optimizes over the parameter t which is used for the indicator function upper bounding. Numerical studies demonstrate that the proposed method can lead to solutions close to the true solution of a joint chance constrained problem.     

Robust multi-market newsvendor models with interval demand data

We present a robust model for determining the optimal order quantity and market selection for short-life-cycle products in a single period, newsvendor setting. Due to limited information about demand distribution in particular for short-life-cycle products, stochastic modeling approaches may not be suitable. We propose the minimax regret multi-market newsvendor model, where the demands are only known to be bounded within some given interval. In the basic version of the problem, a linear time solution method is developed. For the capacitated case, we establish some structural results to reduce the problem size, and then propose an approximation solution algorithm based on integer programming. Finally, we compare the performance of the proposed minimax regret model against the typical average-case and worst-case models. Our test results demonstrate that the proposed minimax regret model outperformed the average-case and worst-case models in terms of risk-related criteria and mean profit, respectively.