Heuristic Methods for Linear Multiplicative Programming

The linear multiplicative programming is the minimization of the product of affine functions over a polyhedral set. The problem with two affine functions reduces to a parametric linear program and can be solved efficiently. For the objective function with more than two affine functions multiplied, no efficient algorithms that solve the problem to optimality have been proposed, however Benson and Boger have proposed a heuristic algorithm that exploits links of the problem with concave minimization and multicriteria optimization. We will propose a heuristic method for the problem as well as its modification to enhance the accuracy of approximation. Computational experiments demonstrate that the method and its modification solve randomly generated problems within a few percent of relative error.     

Outcome-Space Cutting-Plane Algorithm for Linear Multiplicative Programming

This article presents an outcome-space pure cutting-plane algorithm for globally solving the linear multiplicative programming problem. The framework of the algorithm is taken from a pure cutting-plane decision set-based method developed by Horst and Tuy for solving concave minimization problems. By adapting this method to an outcome-space reformulation of the linear multiplicative programming problem, rather than applying directly the method to the original decision-set formulation, it is expected that considerable computational savings can be obtained. Also, we show how additional computational benefits might be obtained by implementing the new algorithm appropriately. To illustrate the new algorithm, we apply it to the solution of a sample problem.     

Convergence and Application of a Decomposition Method Using Duality Bounds for Nonconvex Global Optimization

The subject of this article is a class of global optimization problems, in which the variables can be divided into two groups such that, in each group, the functions involved have the same structure (e.g. linear, convex or concave, etc.). Based on the decomposition idea of Benders (Ref. 1), a corresponding master problem is defined on the space of one of the two groups of variables. The objective function of this master problem is in fact the optimal value function of a nonlinear parametric optimization problem. To solve the resulting master problem, a branch-and-bound scheme is proposed, in which the estimation of the lower bounds is performed by applying the well-known weak duality theorem in Lagrange duality. The results of this article concentrate on two subjects: investigating the convergence of the general algorithm and solving dual problems of some special classes of nonconvex optimization problems. Based on results in sensitivity and stability theory and in parametric optimization, conditions for the convergence are established by investigating the so-called dual properness property and the upper semicontinuity of the objective function of the master problem. The general algorithm is then discussed in detail for some nonconvex problems including concave minimization problems with a special structure, general quadratic problems, optimization problems on the efficient set, and linear multiplicative programming problems.     

A branch-and-reduce approach to global optimization

This paper presents valid inequalities and range contraction techniques that can be used to reduce the size of the search space of global optimization problems. To demonstrate the algorithmic usefulness of these techniques, we incorporate them within the branch-and-bound framework. This results in a branch-and-reduce global optimization algorithm. A detailed discussion of the algorithm components and theoretical properties are provided. Specialized algorithms for polynomial and multiplicative programs are developed. Extensive computational results are presented for engineering design problems, standard global optimization test problems, univariate polynomial programs, linear multiplicative programs, mixed-integer nonlinear programs and concave quadratic programs. For the problems solved, the computer implementation of the proposed algorithm provides very accurate solutions in modest computational time.     

Global minimization of a generalized linear multiplicative programming

This article presents a simplicial branch and bound algorithm for globally solving generalized linear multiplicative programming problem (GLMP). Since this problem does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving such problem. In this algorithm, a well known simplicial subdivision is used in the branching procedure and the bound estimation is performed by solving certain linear programs. Convergence of this algorithm is established, and some experiments are reported to show the feasibility of the proposed algorithm.     

Global minimization of a generalized convex multiplicative function

This paper discusses an algorithm for generalized convex multiplicative programming problems, a special class of nonconvex minimization problems in which the objective function is expressed as a sum ofp products of two convex functions. It is shown that this problem can be reduced to a concave minimization problem with only 2p variables. An outer approximation algorithm is proposed for solving the resulting problem.     

Nonanticipative duality,relaxations, and formulations for chance-constrained stochastic programs

We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation bounds can be calculated by solving a set of single scenario subproblems and then solving a single knapsack problem. We also derive two new primal MIP formulations and demonstrate that for chance-constrained linear programs, the continuous relaxations of these formulations yield bounds equal to the proposed dual bounds. We propose a new heuristic method and two new exact algorithms based on these duals and formulations. The first exact algorithm applies to chance-constrained binary programs, and uses either of the proposed dual bounds in concert with cuts that eliminate solutions found by the subproblems. The second exact method is a branch-and-cut algorithm for solving either of the primal formulations. Our computational results indicate that the proposed dual bounds and heuristic solutions can be obtained efficiently, and the gaps between the best dual bounds and the heuristic solutions are small.     

Global Optimization of Multiplicative Programs

This paper develops global optimization algorithms for linear multiplicative and generalized linear multiplicative programs based upon the lower bounding procedure of Ryoo and Sahinidis [30] and new greedy branching schemes that are applicable in the context of any rectangular branch-and-bound algorithm. Extensive computational results are presented on a wide range of problems from the literature, including quadratic and bilinear programs, and randomly generated large-scale multiplicative programs. It is shown that our algorithms make possible for the first time the solution of large and complex multiplicative programs to global optimality.     

Integrated pricing and lot-sizing decisions in a serial supply chain

In this article, we consider a serial supply chain controlled by a decision-maker who is responsible for deciding the amount of raw material to order from the selected suppliers, the amount of product to transfer between consecutive stages in order to avoid any inventory shortages, and the final product's selling price so that the profit per time unit is maximized. Coordinating all these decisions simultaneously is a topic that has been neglected in literature. This integrated process is modeled as a mixed-integer nonlinear programming model. In addition, the model requires the order quantity received from each selected supplier to be an integer multiple of the order quantity delivered to the following stage, which means that a different multiplicative factor can be assigned to each supplier. This coordination mechanism shows an improvement in the objective function compared to existing models that assign the same multiplicative factor to each selected supplier. Moreover, we develop a heuristic algorithm that generates near optimal solutions in a timely manner. Two numerical examples are presented to illustrate the proposed model and the heuristic algorithm.     

A continuous approach for the concave cost supply problem via DC programming and DCA

The paper addresses an important but difficult class of concave cost supply management problems which consist in minimizing a separable increasing concave objective function subject to linear and disjunctive constraints. We first recast these problems into mixed zero-one nondifferentiable concave minimization over linear constraints problems and then apply exact penalty techniques to state equivalent nondifferentiable polyhedral DC (Difference of Convex functions) programs. A new deterministic approach based on DC programming and DCA (DC Algorithms) is investigated to solve the latter ones. Finally numerical simulations are reported which show the efficiency, the robustness and the globality of our approach.     

Parametric simplex algorithms for solving a special class of nonconvex minimization problems

It is shown that parametric linear programming algorithms work efficiently for a class of nonconvex quadratic programming problems called generalized linear multiplicative programming problems, whose objective function is the sum of a linear function and a product of two linear functions. Also, it is shown that the global minimum of the sum of the two linear fractional functions over a polytope can be obtained by a similar algorithm. Our numerical experiments reveal that these problems can be solved in much the same computational time as that of solving associated linear programs. Furthermore, we will show that the same approach can be extended to a more general class of nonconvex quadratic programming problems.     

An unconstrained dual approach to solving Karmarkar-type linear programs using conventional barrier functions

This paper proposes an unconstrained dual approach and an efficient algorithm for solving Karmarkar-type linear programming problems. Conventional barrier functions are incorporated as a perturbation term in the derivation of the associated duality theory. An optimal solution of the original linear program can be obtained by solving a sequence of unconstrained concave programs, or be approximated by solving one such dual program with a sufficiently small perturbation parameter. A globally convergent curved-search algorithm with a quadratic rate of convergence is designed for this purpose. Based on our testing results, we find that the computational procedure is very efficient and can be a viable approach for solving linear programming problems.     

An objective space cut and bound algorithm for convex multiplicative programmes

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.     

An adaptive tabu-simulated annealing for concave cost transportation problems

The transportation problem (TP) is one of the most popular network problems because of its theoretical and practical importance. If the transportation cost linearly depends on the transported amount of the product, then TP is solvable in polynomial time with linear programming methods. However, in the real world, the transportation costs are generally nonlinear, frequently concave where the unit cost for transporting products decreases as the amount of products increases. Since concave cost transportation problems (ccTPs) are NP-hard, solving large-scale problems is time consuming. In this study, we propose a hybrid algorithm based on the concepts borrowed from tabu search (TS) and simulated annealing (SA) to solve the ccTP. This algorithm, called ATSA (adaptive tabu-simulated annealing), is an SA approach supplemented with a tabu list and adaptive cooling strategy. The effectiveness of ATSA has been investigated in two stages using a set of TPs with different sizes. The first stage includes performance analysis of ATSA using SA, ASA (adaptive simulated anealing) and TS, which are basic forms of ATSA. In the second stage, ATSA has been compared with the heuristic approaches given in the literature for ccTP. Statistical analysis shows that ATSA exhibits better performance than its basic forms and heuristic approaches.     

Global optimization of mixed-integer nonlinear programs: A theoretical and computational study

This work addresses the development of an efficient solution strategy for obtaining global optima of continuous, integer, and mixed-integer nonlinear programs. Towards this end, we develop novel relaxation schemes, range reduction tests, and branching strategies which we incorporate into the prototypical branch-and-bound algorithm. In the theoretical/algorithmic part of the paper, we begin by developing novel strategies for constructing linear relaxations of mixed-integer nonlinear programs and prove that these relaxations enjoy quadratic convergence properties. We then use Lagrangian/linear programming duality to develop a unifying theory of domain reduction strategies as a consequence of which we derive many range reduction strategies currently used in nonlinear programming and integer linear programming. This theory leads to new range reduction schemes, including a learning heuristic that improves initial branching decisions by relaying data across siblings in a branch-and-bound tree. Finally, we incorporate these relaxation and reduction strategies in a branch-and-bound algorithm that incorporates branching strategies that guarantee finiteness for certain classes of continuous global optimization problems. In the computational part of the paper, we describe our implementation discussing, wherever appropriate, the use of suitable data structures and associated algorithms. We present computational experience with benchmark separable concave quadratic programs, fractional 0–1 programs, and mixed-integer nonlinear programs from applications in synthesis of chemical processes, engineering design, just-in-time manufacturing, and molecular design.The research was supported in part by ExxonMobil Upstream Research Company, National Science Foundation awards DMII 95-02722, BES 98-73586, ECS 00-98770, and CTS 01-24751, and the Computational Science and Engineering Program of the University of Illinois.     

Using a Hybrid Genetic-Algorithm/Branch and Bound Approach to Solve Feasibility and Optimization Integer Programming Problems

The satisfiability problem in forms such as maximum satisfiability (MAX-SAT) remains a hard problem. The most successful approaches for solving such problems use a form of systematic tree search. This paper describes the use of a hybrid algorithm, combining genetic algorithms and integer programming branch and bound approaches, to solve MAX-SAT problems. Such problems are formulated as integer programs and solved by a hybrid algorithm implemented within standard mathematical programming software. Computational testing of the algorithm, which mixes heuristic and exact approaches, is described.     

Concave Programming in Control Theory

We show in the present paper that many open and challenging problems in control theory belong the the class of concave minimization programs. More precisely, these problems can be recast as the minimization of a concave objective function over convex LMI (Linear Matrix Inequality) constraints. As concave programming is the best studied class of problems in global optimization, several concave programs such as simplicial and conical partitioning algorithms can be used for the resolution. Moreover, these global techniques can be combined with a local Frank and Wolfe feasible direction algorithm and improved by the use of specialized stopping criteria, hence reducing the overall computational overhead. In this respect, the proposed hybrid optimization scheme can be considered as a new line of attack for solving hard control problems.Computational experiments indicate the viability of our algorithms, and that in the worst case they require the solution of a few LMI programs. Power and efficiency of the algorithms are demonstrated for a realistic inverted-pendulum control problem.Overall, this dedication reflects the key role that concavity and LMIs play in difficult control problems.     

Computational experience using an edge search algorithm for linear reverse convex programs

This paper presents computational experience with a rather straight forward implementation of an edge search algorithm for obtaining the globally optimal solution for linear programs with an additional reverse convex constraint. The paper's purpose is to provide a collection of problems, with known optimal solutions, and performance information for an edge search implementation so that researchers may have some benchmarks with which to compare new methods for reverse convex programs or concave minimization problems. There appears to be nothing in the literature that provides computational experience with a basic edge search procedure. The edge search implementation uses a depth first strategy. As such, this paper's implementation of the edge search algorithm is a modification of Hillestad's algorithm [11]. A variety of test problems is generated by using a modification of the method of Sung and Rosen [20], as well as a new method that is presented in this paper. Test problems presented may be obtained at ftp://newton.ee.ucla.edu/nonconvex/pub/.     

Solving Sum of Ratios Fractional Programs via Concave Minimization

This article presents an algorithm for globally solving a sum of ratios fractional programming problem. To solve this problem, the algorithm globally solves an equivalent concave minimization problem via a branch-and-bound search. The main work of the algorithm involves solving a sequence of convex programming problems that differ only in their objective function coefficients. Therefore, to solve efficiently these convex programming problems, an optimal solution to one problem can potentially be used to good advantage as a starting solution to the next problem.     

A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes

In this paper, we develop a version of the bundle method to solve unconstrained difference of convex (DC) programming problems. It is assumed that a DC representation of the objective function is available. Our main idea is to utilize subgradients of both the first and second components in the DC representation. This subgradient information is gathered from some neighborhood of the current iteration point and it is used to build separately an approximation for each component in the DC representation. By combining these approximations we obtain a new nonconvex cutting plane model of the original objective function, which takes into account explicitly both the convex and the concave behavior of the objective function. We design the proximal bundle method for DC programming based on this new approach and prove the convergence of the method to an \(\varepsilon \)-critical point. The algorithm is tested using some academic test problems and the preliminary numerical results have shown the good performance of the new bundle method. An interesting fact is that the new algorithm finds nearly always the global solution in our test problems.