Search

In this paper, a wide-neighborhood predictor-corrector feasible interior-point algorithm for linear complementarity problems is proposed. The algorithm is based on using the classical affine scaling direction as a part in a corrector step, not in a predictor step. The convergence analysis of the algorithm is shown, and it is proved that the algorithm has the polynomial complexity $$O\left(\sqrt{n}\log \varepsilon ^{-1}\right)$$ which coincides with the best known iteration bound for this class of mathematical problems. The numerical results indicate the efficiency of the algorithm.

In this paper, we propose an arc-search interior-point algorithm for convex quadratic programming with a wide neighborhood of the central path, which searches the optimizers along the ellipses that approximate the entire central path. The favorable polynomial complexity bound of the algorithm is obtained, namely O(nlog((x0)Ts0/e)) which is as good as the linear programming analogue. Finally, the numerical experiments show that the proposed algorithm is efficient.

Nonlinear complementarity and mixed complementarity problems arise in mathematical models describing several applications in Engineering, Economics and different branches of physics. Previously, robust and efficient feasible directions interior point algorithm was presented for nonlinear complementarity problems. In this paper, it is extended to mixed nonlinear complementarity problems. At each iteration, the algorithm finds a feasible direction with respect to the region defined by the inequality conditions, which is also monotonic descent direction for the potential function. Then, an approximate line search along this direction is performed in order to define the next iteration. Global and asymptotic convergence for the algorithm is investigated. The proposed algorithm is tested on several benchmark problems. The results are in good agreement with the asymptotic analysis. Finally, the algorithm is applied to the elastic–plastic torsion problem encountered in the field of Solid Mechanics.

In this paper, we investigate the computational behavior of the exterior point simplex algorithm. Up until now, there has been a major difference observed between the theoretical worst case complexity and practical performance of simplex-type algorithms. Computational tests have been carried out on randomly generated sparse linear problems and on a small set of benchmark problems. Specifically, 6780 linear problems were randomly generated, in order to formulate a respectable amount of experiments. Our study consists of the measurement of the number of iterations that the exterior point simplex algorithm needs for the solution of the above mentioned problems and benchmark dataset. Our purpose is to formulate representative regression models for these measurements, which would play a significant role for the evaluation of an algorithm’s efficiency. For this examination, specific characteristics, such as the number of constraints and variables, the sparsity and bit length, and the condition of matrix A, of each linear problem, were taken into account. What drew our attention was that the formulated model for the randomly generated problems reveal a linear relation among these characteristics.

We consider a class of nonlinear integer optimization problems commonly known as fractional 0---1 programming problems (also, often referred to as hyperbolic 0---1 programming problems), where the objective is to optimize the sum of ratios of affine functions subject to a set of linear constraints. Such problems arise in diverse applications across different fields, and have been the subject of study in a number of papers during the past few decades. In this survey we overview the literature on fractional 0---1 programs including their applications, related computational complexity issues and solution methods including exact, approximation and heuristic algorithms.

In this paper, we propose a new hybrid social spider algorithm with simplex Nelder-Mead method in order to solve integer programming and minimax problems. We call the proposed algorithm a Simplex Social Spider optimization (SSSO) algorithm. In the the proposed SSSO algorithm, we combine the social spider algorithm with its powerful capability of performing exploration, exploitation, and the Nelder-Mead method in order to refine the best obtained solution from the standard social spider algorithm. In order to investigate the general performance of the proposed SSSO algorithm, we test it on 7 integer programming problems and 10 minimax problems and compare against 10 algorithms for solving integer programming problems and 9 algorithms for solving minimax problems. The experiments results show the efficiency of the proposed algorithm and its ability to solve integer and minimax optimization problems in reasonable time.

In this paper, we propose an arc-search infeasible-interior-point method for linear programming. The proposed algorithm is based on a wide neighborhood of the central path and searches the optimizers along the ellipses that approximate the entire the central path. We also establish polynomial complexity of the proposed algorithm. Finally, numerical experiments show that the proposed algorithm is efficient and reliable.

In this paper, a new global algorithm is presented to globally solve the linear multiplicative programming (LMP). The problem (LMP) is firstly converted into an equivalent programming problem (LMP (H)) by introducing p auxiliary variables. Then by exploiting structure of (LMP(H)), a linear relaxation programming (LP (H)) of (LMP (H)) is obtained with a problem (LMP) reduced to a sequence of linear programming problems. The algorithm is used to compute the lower bounds called the branch and bound search by solving linear relaxation programming problems (LP(H)). The proposed algorithm is proven that it is convergent to the global minimum through the solutions of a series of linear programming problems. Some examples are given to illustrate the feasibility of the proposed algorithm.

The bilevel programming problem is strongly NP-hard and non-convex, which implies that the problem is very challenging for most canonical optimization approaches using single-point search techniques to find global optima. In the present paper, a class of nonlinear bilevel programming problems are considered where the follower is a linear fractional program. Based on a novel coding scheme, a genetic algorithm with global convergence was developed. First, potential bases of the follower’s problem were taken as individuals, and a genetic algorithm was used to explore these bases. In addition, in order to evaluate each individual, a fitness function was presented by making use of the optimality conditions of linear fractional programs. Also, the fitness evaluation, as a sub-procedure of optimization, can partly improve the leader’s objective. Finally, some computational examples were solved and the results show that the proposed algorithm is efficient and robust.

In this paper, we use an interior points method of projective type for calculate the initial dual solution of the convex nonlinear programming using the Ye Lustig variant applied to linear programming, as a result we propose a modification in this algorithm to reduce the number of iterations and the computing time of this algorithm. The numerical tests confirm that the modified algorithm is robust.

This article presents a new approximation algorithm for globally solving a class of generalized fractional programming problems (P) whose objective functions are defined as an appropriate composition of ratios of affine functions. To solve this problem, the algorithm solves an equivalent optimization problem (Q) via an exploration of a suitably defined nonuniform grid. The main work of the algorithm involves checking the feasibility of linear programs associated with the interesting grid points. It is proved that the proposed algorithm is a fully polynomial time approximation scheme as the ratio terms are fixed in the objective function to problem (P), based on the computational complexity result. In contrast to existing results in literature, the algorithm does not require the assumptions on quasi-concavity or low-rank of the objective function to problem (P). Numerical results are given to illustrate the feasibility and effectiveness of the proposed algorithm.

This paper presents a linear decomposition approach for a class of nonconvex programming problems by dividing the input space into polynomially many grids. It shows that under certain assumptions the original problem can be transformed and decomposed into a polynomial number of equivalent linear programming subproblems. Based on solving a series of liner programming subproblems corresponding to those grid points we can obtain the near-optimal solution of the original problem. Compared to existing results in the literature, the proposed algorithm does not require the assumptions of quasi-concavity and differentiability of the objective function, and it differs significantly giving an interesting approach to solving the problem with a reduced running time.

We propose a polynomial algorithm for linear feasibility problems. The algorithm represents a linear problem in the form of a system of linear equations and non-negativity constraints. Then it uses a procedure which either finds a solution for the respective homogeneous system or provides the information based on which the algorithm rescales the homogeneous system so that its feasible solutions in the unit cube get closer to the vector of all ones. In a polynomial number of calls to the procedure the algorithm either proves that the original system is infeasible or finds a solution in the relative interior of the feasible set.

To formulate fuzzy linear programming, Gaussian membership functions rather than triangular or trapezoidal ones are usually recognized as more reasonable descriptions for fuzziness. However, the strong nonlinearity of Gaussian membership functions is readily to cause increasing difficulties in achieving optimum solutions accordingly. Motivated by this challenge, we introduce a novel piecewise linear membership function-based decomposition–coordination algorithm, which can initially decompose a fuzzy linear programming problem with Gaussian membership functions into several crisp linear programming models and then coordinate solutions of the sub-models to eventually achieve an overall optimum one. In this paper, detailed algorithmic procedures are presented along with corresponding theoretical analysis. In addition, an application of production planning programming in a workshop of an oil refinery is provided to demonstrate the effectiveness of the proposed methodology.

This paper proposes a new self-adaptive differential evolution algorithm (DE) for continuous optimization problems. The proposed self-adaptive differential evolution algorithm extends the concept of the DE/current-to-best/1 mutation strategy to allow the adaptation of the mutation parameters. The control parameters in the mutation operation are gradually self-adapted according to the feedback from the evolutionary search. Moreover, the proposed differential evolution algorithm also consists of a new local search based on the krill herd algorithm. In this study, the proposed algorithm has been evaluated and compared with the traditional DE algorithm and two other adaptive DE algorithms. The experimental results on 21 benchmark problems show that the proposed algorithm is very effective in solving complex optimization problems.

There recently has been much interest in smoothing-type algorithms for solving the linear second-order cone programming (LSOCP). We extend such method to solve the convex second-order cone programming (CSOCP), which is an extension of the LSOCP. In this paper, we first propose a new smoothing function. Based on this function, we establish a smoothing Newton algorithm for solving the CSOCP and prove that the algorithm is globally and locally quadratically convergent under suitable assumptions. For the established algorithm, we use a generalized Armijo-type search rule to generate the step size. Some numerical results are reported which indicate the effectiveness of our algorithm.

In this paper, a conic reformulation and approximation is proposed for solving a nonconvex quadratic programming problem subject to several convex quadratic constraints. The original problem is transformed into a linear conic programming problem, which can be approximated by a sequence of linear conic programming problems over the dual cone of the cone of nonnegative quadratic functions. Since the dual cone of the cone of nonnegative quadratic functions has a linear matrix inequality representation, each linear conic programming problem in the sequence can be solved efficiently using the semidefinite programming techniques. In order to speed up the convergence of the approximation sequence and relieve the computational effort in solving the linear conic programming problems, an adaptive scheme is adopted in the proposed algorithm. We prove that the lower bounds generated by the linear conic programming problems converge to the optimal value of the original problem. Several numerical examples are used to illustrate how the algorithm works and the computational results demonstrate the efficiency of the proposed algorithm.

By utilizing a dual complementarity property, we propose a new linear programming method for solving the NP-hard absolute value equation (AVE): Ax?|x|=b, where A is an n×n square matrix. The algorithm makes no assumptions on the AVE other than solvability and consists of solving a few linear programs, typically less than four. The algorithm was tested on 500 consecutively generated random solvable instances of the AVE with n=10, 50, 100, 500 and 1000. The algorithm solved 100 % of the test problems to an accuracy of 10?8 by solving an average of 3.3 linear programs per AVE problem.

Multiplicative programming problems are global optimisation problems known to be NP-hard. In this paper we propose an objective space cut and bound algorithm for approximately solving convex multiplicative programming problems. This method is based on an objective space approximation algorithm for convex multi-objective programming problems. We show that this multi-objective optimisation algorithm can be changed into a cut and bound algorithm to solve convex multiplicative programming problems. We use an illustrative example to demonstrate the working of the algorithm. Computational experiments illustrate the superior performance of our algorithm compared to other methods from the literature.

It is shown how the portfolio Omega ratio can be maximized using two linear programming problems. The solution algorithm is to test some condition and solve one of these problems depending on the condition. An example of calculations is given.

In this paper, we present a new trust region algorithm for a nonlinear bilevel programming problem by solving a series of its linear or quadratic approximation subproblems. For the nonlinear bilevel programming problem in which the lower level programming problem is a strongly convex programming problem with linear constraints, we show that each accumulation point of the iterative sequence produced by this algorithm is a stationary point of the bilevel programming problem.

In this paper, ellipsoidal estimations are used to track the central path of linear programming. A higher-order interior-point algorithm is devised to search the optimizers along the ellipse. The algorithm is proved to be polynomial with the best complexity bound for all polynomial algorithms and better than the best known bound for higher-order algorithms.

We present several generalisations of the Games---Chan algorithm. For a fixed monic irreducible polynomial f we consider the sequences s that have as a characteristic polynomial a power of f. We propose an algorithm for computing the linear complexity of s given a full (not necessarily minimal) period of s. We give versions of the algorithm for fields of characteristic 2 and for arbitrary finite characteristic p, the latter generalising an algorithm of Ding et al. We also propose an algorithm which computes the linear complexity given only a finite portion of s (of length greater than or equal to the linear complexity), generalising an algorithm of Meidl. All our algorithms have linear computational complexity. The proposed algorithms can be further generalised to sequences for which it is known a priori that the irreducible factors of the minimal polynomial belong to a given small set of polynomials.

This study proposes a novel technique for solving Linear Programming Problems in a fully fuzzy environment. A modified version of the well-known simplex method is used for solving fuzzy linear programming problems. The use of a ranking function together with the Gaussian elimination process helps in solving linear programming problems in a fully uncertain environment. The proposed algorithm is flexible, easy and reasonable.

In this paper, we propose an interior-point algorithm for monotone linear complementarity problems. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full-Newton steps. Moreover, it is proven that the number of iterations of the algorithm coincides with the well-known best iteration bound for monotone linear complementarity problems.

This article present a branch and bound algorithm for globally solving generalized linear multiplicative programming problems with coefficients. The main computation involve solving a sequence of linear relaxation programming problems, and the algorithm economizes the required computations by conducting the branch and bound search in R p , rather than in R n , where p is the number of rank and n is the dimension of decision variables. The proposed algorithm will be convergent to the global optimal solution by means of the subsequent solutions of the series of linear relaxation programming problems. Numerical results are given to show the feasibility and effectiveness of the proposed algorithm.

A new algorithm is presented to solve constrained nonlinear optimal control problems, with an emphasis on highly nonlinear dynamical systems. The algorithm, called HDDP, is a hybrid variant of differential dynamic programming, a proven second-order technique that relies on Bellman's Principle of Optimality and successive minimization of quadratic approximations. The new hybrid method incorporates nonlinear mathematical programming techniques to increase efficiency: quadratic programming subproblems are solved via trust region and range-space active set methods, an augmented Lagrangian cost function is utilized, and a multiphase structure is implemented. In addition, the algorithm decouples the optimization from the dynamics using first- and second-order state transition matrices. A comprehensive theoretical description of the algorithm is provided in this first part of the two paper series. Practical implementation and numerical evaluation of the algorithm is presented in Part 2.

This paper reviews alternative market equilibrium models for policy analysis. The origin of spatial equilibrium models and their application to wood and wood-processing industries are described. Three mathematical programming models commonly applied to solve spatial problems — namely linear programming, non-linear programming and mixed complementary programming — are reviewed in terms of forms of objective functions and constraint equalities and inequalities. These programming are illustrated with numerical examples. Linear programming is only applied in transportation problems to solve quantities transported between regions when quantities supplied and demanded in each region are already known. It is argued that linear programming can be applied in broader context to transportation problems where supply and demand quantities are unknown and are linear. In this context, linear programming is seen as a more convenient method for modelers because it has a simpler objective function and does not require as strict conditions, for instance the equal numbers of variables and equations required in mixed complementary programming. Finally, some critical insights are provided on the interpretation of optimal solutions generated by solving spatial equilibrium models.

Linear programming with linear complementarity constraints (LPLCC) is an area of active research in Optimization, due to its many applications, algorithms, and theoretical existence results. In this paper, a number of formulations for important nonconvex optimization problems are first reviewed. The most relevant algorithms for computing a complementary feasible solution, a stationary point, and a global minimum for the LPLCC are also surveyed, together with some comments about their efficiency and efficacy in practice.

In this paper, we present a primal-like algorithm to solve an extreme point linear programming problem with fuzzy constraints.

Outcome space methods construct the set of nondominated points in the objective (outcome) space of a multiple objective linear programme. In this paper, we employ results from geometric duality theory for multiple objective linear programmes to derive a dual variant of Benson's "outer approximation algorithm" to solve multiobjective linear programmes in objective space. We also suggest some improvements of the original version of the algorithm and prove that solving the dual provides a weight set decomposition. We compare both algorithms on small illustrative and on practically relevant examples.

This paper proposes a strongly polynomial algorithm which either finds a solution of a linear system Ax = b, 0 ≤ x ≤ 1, or correctly decides that the system has no 0,1-solutions. The algorithm can be used as the basis for the construction of a polynomial algorithm for linear programming.

In this paper, we consider the learning rates of multi-kernel linear programming classifiers. Our analysis shows that the convergence behavior of multi-kernel linear programming classifiers is almost the same as that of multi-kernel quadratic programming. This is implemented by setting a stepping stone between the linear programming and the quadratic programming. An upper bound is presented for general probability distributions and distribution satisfying some Tsybakov noise condition.

The paper is a manifestation of the fundamental importance of the linear program with linear complementarity constraints (LPCC) in disjunctive and hierarchical programming as well as in some novel paradigms of mathematical programming. In addition to providing a unified framework for bilevel and inverse linear optimization, nonconvex piecewise linear programming, indefinite quadratic programs, quantile minimization, and ? 0 minimization, the LPCC provides a gateway to a mathematical program with equilibrium constraints, which itself is an important class of constrained optimization problems that has broad applications. We describe several approaches for the global resolution of the LPCC, including a logical Benders approach that can be applied to problems that may be infeasible or unbounded.

Interior---point algorithms are among the most efficient techniques for solving complementarity problems. In this paper, a procedure for globalizing interior---point algorithms by using the maximum stepsize is introduced. The algorithm combines exact or inexact interior---point and projected---gradient search techniques and employs a line---search procedure for the natural merit function associated with the complementarity problem. For linear problems, the maximum stepsize is shown to be acceptable if the Newton interior---point search direction is employed. Complementarity and optimization problems are discussed, for which the algorithm is able to process by either finding a solution or showing that no solution exists. A modification of the algorithm for dealing with infeasible linear complementarity problems is introduced which, in practice, employs only interior---point search directions. Computational experiments on the solution of complementarity problems and convex programming problems by the new algorithm are included.

Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations (SSLE) algorithm generating feasible iterates is proposed for solving nonlinear optimization problems with inequality constraints. In this paper, we introduce a new technique for constructing the system of linear equations, which recurs to a perturbation for the gradients of the constraint functions. At each iteration of the new algorithm, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination. To ensure the global convergence and avoid the Maratos effect, the algorithm needs to solve two additional reduced systems of linear equations with the same coefficient matrix after finite iterations. The proposed algorithm is proved to be globally and superlinearly convergent under some mild conditions. What distinguishes this algorithm from the previous feasible SSLE algorithms is that an improving direction is obtained easily and the computation cost of generating a new iterate is reduced. Finally, a preliminary implementation has been tested.

A Dinkelbach-type algorithm is proposed in this paper to solve a class of continuous-time linear fractional programming problems. We shall transform this original problem into a continuous-time non-fractional programming problem, which unfortunately happens to be a continuous-time nonlinear programming problem. In order to tackle this nonlinear problem, we propose the auxiliary problem that will be formulated as parametric continuous-time linear programming problem. We also introduce a dual problem of this parametric continuous-time linear programming problem in which the weak duality theorem also holds true. We introduce the discrete approximation method to solve the primal and dual pair of parametric continuous-time linear programming problems by using the recurrence method. Finally, we provide two numerical examples to demonstrate the usefulness of this practical algorithm.

Efficient linear separation algorithms are important for pattern classification applications. In this paper, an algorithm is developed to solve linear separation problems in n-dimensional space. Its convergence feature is proved. The proposed algorithm is proved to converge to a correct solution whenever the two sets are separable. The complexity of the proposed algorithm is analyzed, and experiments on both randomly generated examples and real application problems were carried out. While analysis shows that its time complexity is lower than SVM that needs computations for quadratic programming optimization, experiment results show that the developed algorithm is more efficient than the least-mean-square (LMS), and the Perceptron.

The simplex algorithm for network flow problems has been proposed for linear, piecewise linear, and linear fractional objective functions. Piecewise linear fractional network flow problems can be transformed into equivalent linear or linear fractional programs, but the resulting problems do not possess pure network flow structure and increase the number of variables significantly. We develop a simplex algorithm to solve network flow problems with piecewise linear fractional objective function, unifying and generalizing the network simplex algorithm, network simplex algorithm for piece-wise linear programs, and network simplex algorithm for linear fractional programs. Computational results using the proposed algorithm are also discussed.

In this paper we propose a Fully Polynomial Time Approximation Scheme for a class of optimization problems where the feasible region is a polyhedral one and the objective function is the sum or product of ratios of linear functions. The class includes the well known ones of Linear (Sum-of-Ratios) Fractional Programming and Multiplicative Programming.

We propose a numerical algorithm for finding the normal solution of consistent systems of linear algebraic equations of incomplete rank of rows. Results of a comparison of a numerical realization of the proposed algorithm with some known subroutines are given.

By using the theory of Euclidean Jordan algebras, based on a new class of smoothing functions, the Qi-Sun-Zhou’s smoothing Newton algorithm is extended to solve linear programming over symmetric cones (SCLP). The algorithm is globally convergent under suitable assumptions.

Refining an algorithm due to Koller, Megiddo and von Stengel, we show how to apply Lemke's algorithm for solving linear complementarity programs to compute a quasi-perfect equilibrium in behavior strategies of a given two-player extensive-form game of perfect recall. A quasi-perfect equilibrium is known to be sequential, and our algorithm thus resolves a conjecture of McKelvey and McLennan in the positive. A quasi-perfect equilibrium is also known to be normal-form perfect and our algorithm thus provides an alternative to an algorithm by von Stengel, van den Elzen and Talman. For the case of a zero-sum game, we devise variants of the algorithm that rely on linear programming rather than linear complementarity programming and use the simplex algorithm or other algorithms for linear programming rather than Lemke's algorithm. We argue that these latter algorithms are relevant for recent applications of equilibrium computation to artificial intelligence.

Although linear programming problems can be solved in polynomial time by the ellipsoid method and interior-point algorithms, there still remains a long- standing open problem of devising a strongly polynomial algorithm for linear pro- gramming (or of disproving the existence of such an algorithm). The present work is motivated by an attempt toward solving this problem. Linear programming problems can be formulated in terms of a zonotope, a kind of greedy polyhedron, on which linear optimization is made easily. We propose a method, called the LP-Newton method, for linear programming that is based on the zonotope formulation and the minimum-norm-point algorithm of Philip Wolfe. The LP-Newton method is a finite algorithm even for real-number input data with exact arithmetic computations. We show some preliminary computational results to exam- ine the behavior of the LP-Newton method.

We present an algorithm for solving bilevel linear programs that uses simplex pivots on an expanded tableau. The algorithm uses the relationship between multiple objective linear programs and bilevel linear programs along with results for minimizing a linear objective over the efficient set for a multiple objective problem. Results in multiple objective programming needed are presented. We report computational experience demonstrating that this approach is more effective than a standard branch-and-bound algorithm when the number of leader variables is small.

In this paper we develop a primal–dual simplex algorithm for the bi-objective linear minimum cost network flow problem. This algorithm improves the general primal–dual simplex algorithm for multi-objective linear programs by Ehrgott et al. (J Optim Theory Appl 134:483–497, 2007). We illustrate the algorithm with an example and provide numerical results.

The aim of this paper is to provide new efficient methods for solving general chance-constrained integer linear programs to optimality. Valid linear inequalities are given for these problems. They are proved to characterize properly the set of solutions. They are based on a specific scenario, whose definition impacts strongly on the quality of the linear relaxation built. A branch-and-cut algorithm is described to solve chance-constrained combinatorial problems to optimality. Numerical tests validate the theoretical analysis and illustrate the practical efficiency of the proposed approach.

We consider the separated continuous linear programming problem with linear data. We characterize the form of its optimal solution, and present an algorithm which solves it in a finite number of steps, using an analog of the simplex method, in the space of bounded measurable functions.

Bilevel linear programming, which consists of the objective functions of the upper level and lower level, is a useful tool for modeling decentralized decision problems. Various methods are proposed for solving this problem. Of all the algorithms, the genetic algorithm is an alternative to conventional approaches to find the solution of the bilevel linear programming. In this paper, we describe an adaptive genetic algorithm for solving the bilevel linear programming problem to overcome the difficulty of determining the probabilities of crossover and mutation. In addition, some techniques are adopted not only to deal with the difficulty that most of the chromosomes may be infeasible in solving constrained optimization problem with genetic algorithm but also to improve the efficiency of the algorithm. The performance of this proposed algorithm is illustrated by the examples from references.

Most previous approaches to hardware/software partitioning considered heuristic solutions. In contrast, this paper presents an exact algorithm for the problem based on branch-and-bound. Several techniques are investigated to speed up the algorithm, including bounds based on linear programming, a custom inference engine to make the most out of the inferred information, advanced necessary conditions for partial solutions, and different heuristics to obtain high-quality initial solutions. It is demonstrated with empirical measurements that the resulting algorithm can solve highly complex partitioning problems in reasonable time. Moreover, it is about ten times faster than a previous exact algorithm based on integer linear programming. The presented methods can also be useful in other related optimization problems.