Sufficient Optimality Criterion for Linearly Constrained, Separable Concave Minimization Problems

Illés, T.; Nagy, Á B.
June 2005
Journal of Optimization Theory & Applications;Jun2005, Vol. 125 Issue 3, p559
Academic Journal
A sufficient optimality criterion for linearly-constrained concave minimization problems is given in this paper. Our optimally criterion is based on the sensitivity analysis of the relaxed linear programming Problem. The main result is similar to that of Phillips and Rosen (Ref. 1); however, our proofs are simpler and constructive. In the Phillip and Rosen paper (Ref.1), they derived a sufficient optimality criterion for a slightly different linearly-constrained concave minimization problem using exponentially many linear programming problems. We introduce special test points and, using these for several cases, we are able to show optimally of the current basic solution. The sufficient optimality criterion described in this paper can be used as a stopping criterion for branch-and-bound algorithm developed for linearly-constrained concave minimization problems.


Related Articles

  • BRANCH-AND-BOUND METHODS: A SURVEY. Lawler, E. L.; Wood, D. E. // Operations Research;Jul/Aug66, Vol. 14 Issue 4, p699 

    The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed. These include integer linear programming (LAND-DOIG and BALAS methods), nonlinear programming (minimization of nonconvex objective functions), the...

  • AN ALGORITHM FOR LARGE SET PARTITIONING PROBLEMS. Marsten, Roy E. // Management Science;Jan1974, Vol. 20 Issue 5, p774 

    An algorithm is presented for the special integer linear program known as the set partitioning problem. This problem has a binary coefficient matrix, binary variables, and unit resources. Furthermore, all of its constraints are equations: In spite of its very special form, the set partitioning...

  • A Dual-Bounded Algorithm for the p-Median Problem. Galvão, Roberto O. // Operations Research;Sep/Oct80, Vol. 28 Issue 5, p1112 

    The p-median problem consists of locating p facilities on a network, so that the sum of shortest distances from each of the nodes of the network to its nearest facility is minimized. A dual bound, based on the dual of the LP relaxation of the integer programming formulation of the problem, is...

  • AN APPROACH FOR THE OPTIMAL SOLUTION OF MILP PROBLEMS. Ubale, P. V. // Bulletin of Pure & Applied Sciences-Mathematics;Jul-Dec2012, Vol. 31E Issue 2, p169 

    This paper describes an algorithm for finding solutions to optimization problems in which some of the variables must take integer values. The solution of discrete optimization problem to optimality is often an immense job requiring very efficient algorithm. In this paper we describe a Branch and...

  • Augmented Reality Internet Labs versus its Traditional and Virtual Equivalence. Odeh, Salaheddin; Abu Shanab, Shatha; Anabtawi, Mahasen // International Journal of Emerging Technologies in Learning;2015, Vol. 10 Issue 3, p4 

    Engineering is an applied science; it makes science come alive through experiments and labs. Students can only gain practical knowledge that goes beyond mere scientific theory in the educational labs. This can be done using three different types of educational labs: Augmented reality labs,...

  • A simplicial branch-and-bound algorithm conscious of special structures in concave minimization problems. Kuno, Takahito; Nagai, Hidetoshi // Computational Optimization & Applications;Mar2008, Vol. 39 Issue 2, p219 

    In this paper, we develop a simplicial branch-and-bound algorithm for generating globally optimal solutions to concave minimization problems with low rank nonconvex structures. We propose to remove all additional constraints imposed on the usual linear programming relaxed problem. Therefore, in...

  • Global optimization of general nonconvex problems with intermediate polynomial substructures. Zorn, Keith; Sahinidis, Nikolaos // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p673 

    This work considers the global optimization of general nonconvex nonlinear and mixed-integer nonlinear programming problems with underlying polynomial substructures. We incorporate linear cutting planes inspired by reformulation-linearization techniques to produce tight subproblem formulations...

  • Choosing the Job Sequence and Processing Times to Minimize Total Processing Plus Flow Cost on a Single Machine. Vickson, R. G. // Operations Research;Sep/Oct80, Vol. 28 Issue 5, p1155 

    This paper treats the problem of minimizing the total weighted flow cost plus job-processing cost in a single machine sequencing problem for jobs having processing costs which are linear functions of processing times. The optimal job sequence and processing times are obtainable from the solution...

  • Solving Convex MINLP Optimization Problems Using a Sequential Cutting Plane Algorithm. Still, Claus; Westerlund, Tapio // Computational Optimization & Applications;May2006, Vol. 34 Issue 1, p63 

    In this article we look at a new algorithm for solving convex mixed integer nonlinear programming problems. The algorithm uses an integrated approach, where a branch and bound strategy is mixed with solving nonlinear programming problems at each node of the tree. The nonlinear programming...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics