A relaxed cutting plane algorithm for solving fuzzy inequality systems

This paper studies a system of infinitely many fuzzy inequalities with concavemembership functions. By using the tolerance approach, we show that solving such system can be reduced to a semi-infinite programming problem. A relaxed cutting plane algorithm is proposed. In each iteration, we solve a finite convex optimization problem and add one or two more constraints. The proposed algorithm chooses a point at which the infinite constraints are violated to a degree rather than at which the violation is maximized. The iterative process ends when an optimal solution is identified. A convergence proof, under some mild conditions, is given. An efficient implementation based on the "method of centres" with "entropic regularization" techniques is also included. Some computational results confirm the efficiency of the proposed method and show its potential for solving large scale problems.     

A cutting plane algorithm for solving bilinear programs

This paper addresses itself to a special class of nonconvex quadratic program referred to as a bilinear program in the literature. We will propose here a cutting plane algorithm to solve this class of problems. The algorithm is along the lines of H. Tui and K. Ritter, but it differs in its exploitation of the special structure of the problem. Though the algorithm is not guaranteed at this stage of the research to converge to a global optimum, the preliminary results of numerical experiments are encouraging.This research was partially supported by the Office of Naval Research under Contract N-00014-67-A-0112-0011; and U.S. Atomic Energy Commission Contract AT(04-3)-326-PA # 18.     

A cutting plane algorithm for graph coloring

We present an approach based on integer programming formulations of the graph coloring problem. Our goal is to develop models that remove some symmetrical solutions obtained by color permutations. We study the problem from a polyhedral point of view and determine some families of facets of the 0/1-polytope associated with one of these integer programming formulations. The theoretical results described here are used to design an efficient Cutting Plane algorithm.     

A sequential cutting plane algorithm for solving convex NLP problems

In this paper we look at a new algorithm for solving convex nonlinear programming optimization problems. The algorithm is a cutting plane-based method, where the sizes of the subproblems remain fixed, thus avoiding the issue with constantly growing subproblems we have for the classical Kelley’s cutting plane algorithm. Initial numerical experiments indicate that the algorithm is considerably faster than Kelley’s cutting plane algorithm and also competitive with existing nonlinear programming algorithms.     

A lift-and-project cutting plane algorithm for mixed 0–1 programs

We propose a cutting plane algorithm for mixed 0–1 programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through the solution of a linear program that has about twice the size of the usual LP relaxation. A lifting step is used to reduce the size of the LP's needed to generate the cuts. An additional strengthening step suggested by Balas and Jeroslow is then applied. We report our computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cone relaxations of Lovász and Schrijver and the hierarchy of relaxations of Sherali and Adams.The research underlying this report was supported by National Science Foundation Grant #DDM-8901495 and Office of Naval Research Contract N00014-85-K-0198.     

A relaxed cutting plane method for semi-infinite semi-definite programming

In this paper, we develop two discretization algorithms with a cutting plane scheme for solving combined semi-infinite and semi-definite programming problems, i.e., a general algorithm when the parameter set is a compact set and a typical algorithm when the parameter set is a box set in the m-dimensional space. We prove that the accumulation point of the sequence points generated by the two algorithms is an optimal solution of the combined semi-infinite and semi-definite programming problem under suitable assumption conditions. Two examples are given to illustrate the effectiveness of the typical algorithm.     

A cutting plane method for solving harvest scheduling models with area restrictions

We describe a cutting plane algorithm for an integer programming problem that arises in forest harvest scheduling. Spatial harvest scheduling models optimize the binary decisions of cutting or not cutting forest management units in different time period subject to logistical, economic and environmental restrictions. One of the most common constraints requires that the contiguous size of harvest openings (i.e., clear-cuts) cannot exceed an area threshold in any given time period or over a set of periods called green-up. These so-called adjacency or green-up constraints make the harvest scheduling problem combinatorial in nature and very hard to solve. Our proposed cutting plane algorithm starts with a model without area restrictions and adds constraints only if a violation occurs during optimization. Since violations are less likely if the threshold area is large, the number of constraints is kept to a minimum. The utility of the approach is illustrated by an application, where the landowner needs to assess the cost of forest certification that involves clear-cut size restrictions stricter than what is required by law. We run empirical tests and find that the new method performs best when existing models fail: when the number of units is high or the allowable clear-cut size is large relative to average unit size. Since this scenario is the norm rather than the exception in forestry, we suggest that timber industries would greatly benefit from the method. In conclusion, we describe a series of potential applications beyond forestry.     

A cutting plane algorithm for convex programming that uses analytic centers

Anoracle for a convex setS ⁿ accepts as input any pointz in ⁿ , and ifz S, then it returns yes, while ifz S, then it returns no along with a separating hyperplane. We give a new algorithm that finds a feasible point inS in cases where an oracle is available. Our algorithm uses the analytic center of a polytope as test point, and successively modifies the polytope with the separating hyperplanes returned by the oracle. The key to establishing convergence is that hyperplanes judged to be unimportant are pruned from the polytope. If a ball of radius 2^–L is contained inS, andS is contained in a cube of side 2 ^L+1, then we can show our algorithm converges after O(nL ²) iterations and performs a total of O(n ⁴ L ³+TnL ²) arithmetic operations, whereT is the number of arithmetic operations required for a call to the oracle. The bound is independent of the number of hyperplanes generated in the algorithm. An important application in which an oracle is available is minimizing a convex function overS. Supported by the National Science Foundation under Grant CCR-9057481PYI.Supported by the National Science Foundation under Grants CCR-9057481 and CCR-9007195.     

A multivariate adaptive regression splines cutting plane approach for solving a two-stage stochastic programming fleet assignment model

The fleet assignment model assigns a fleet of aircraft types to the scheduled flight legs in an airline timetable published six to twelve weeks prior to the departure of the aircraft. The objective is to maximize profit. While costs associated with assigning a particular fleet type to a leg are easy to estimate, the revenues are based upon demand, which is realized close to departure. The uncertainty in demand makes it challenging to assign the right type of aircraft to each flight leg based on forecasts taken six to twelve weeks prior to departure. Therefore, in this paper, a two-stage stochastic programming framework has been developed to model the uncertainty in demand, along with the Boeing concept of demand driven dispatch to reallocate aircraft closer to the departure of the aircraft. Traditionally, two-stage stochastic programming problems are solved using the L-shaped method. Due to the slow convergence of the L-shaped method, a novel multivariate adaptive regression splines cutting plane method has been developed. The results obtained from our approach are compared to that of the L-shaped method, and the value of demand-driven dispatch is estimated.     

A cutting plane algorithm for MV portfolio selection model

This paper deals with a portfolio selection problem with fuzzy return rates. A possibilistic mean variance (FMVC) portfolio selection model was proposed. The possibilistic programming problem can be transformed into a linear optimal problem with an additional quadratic constraint by possibilistic theory. For such problems there are no special standard algorithms. We propose a cutting plane algorithm to solve (FMVC). The nonlinear programming problem can be solved by sequence linear programming problem. A numerical example is given to illustrate the behavior of the proposed model and algorithm.     

A one-phase algorithm for semi-infinite linear programming

We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding an-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.     

Uncertain fractional differential equations and an interest rate model

The concept of uncertain fractional differential equation is introduced, and solutions of several uncertain fractional differential equations are presented. This kind of equation is a counterpart of stochastic fractional differential equation. By the proposed concept, an interest rate model is considered, and the price of a zero‐coupon bond is obtained. Copyright © 2014 John Wiley & Sons, Ltd.     

A cutting plane method for solving minimax problems in the complex plane

It is shown how the combined discretization and cutting plane method for general convex semi-infinite programming problems recently presented in [40] can be effectively implemented for the solution of minimax problems in the complex plane. In contrast to other approaches, the minimax problem does not have to be linearized. The performance of the algorithm is demonstrated by a number of highly accurate numerical examples.     

A nonsmooth Levenberg–Marquardt method for solving semi-infinite programming problems

In this paper, we first transform the semi-infinite programming problem into the KKT system by the techniques in [D.H. Li, L. Qi, J. Tam, S.Y. Wu, A smoothing Newton method for semi-infinite programming, J. Global. Optim. 30 (2004) 169–194; L. Qi, S.Y. Wu, G.L. Zhou, Semismooth Newton methods for solving semi-infinite programming problems, J. Global. Optim. 27 (2003) 215–232]. Then a nonsmooth and inexact Levenberg–Marquardt method is proposed for solving this KKT system based on [H. Dan, N. Yamashita, M. Fukushima, Convergence properties of the inexact Levenberg–Marquardt method under local error bound conditions, Optimim. Methods Softw., 11 (2002) 605–626]. This method is globally and superlinearly (even quadratically) convergent. Finally, some numerical results are given.     

A comparison between a primal and a dual cutting plane algorithm for posynomial geometric programming problems

In this paper, primal and dual cutting plane algorithms for the solution of posynomial geometric programming problems are presented. It is shown that these cuts are deepest, in the sense that they cut off as much of the infeasible set as possible. Problems of nondifferentiability in the dual cutting plane are circumvented by the use of a subgradient. Although the resulting dual problem seems easier to solve, the computational experience seems to show that the primal cutting plane outperforms the dual.     

An efficient algorithm for solving semi-infinite inequality problems with box constraints

Many design objectives may be formulated as semi-infinite constraints. Examples in control design, for example, include hard constraints on time and frequency responses and robustness constraints. A useful algorithm for solving such inequalities is the outer approximations algorithm. One version of an outer approximations algorithm for solving an infinite set of inequalities(x, y) 0 for allyY proceeds by solving, at iterationi of the master algorithm, a finite set of inequalities ((x, y) 0 for allyY _i) to yieldx _i and then updatingY _i toY _i+1=Y _i {y_i } wherey _i arg max {(x _i,y)¦y Y}. Since global optimization is computationally extremely expensive, it is desirable to reduce the number of such optimizations. We present, in this paper, a modified version of the outer approximations algorithm which achieves this objective.The research reported herein was sponsored by the National Science Foundation Grants ECS-9024944, ECS-8816168, the Air Force Office of Scientific Research Contract AFOSR-90-0068, and the NSERC of Canada under Grant OGPO-138352.     

A BRANCH-AND-PRICE ALGORITHM FOR SOLVING THE CUTTING STRIPS PROBLEM

After giving a suitable model for the cutting strips problem, we present a branch-and-price algorithm for it by combining the column generation technique and the branch-and-hound method with LP relaxations. Some theoretical issues and implementation details about the algorithm are discussed, including the solution of the pricing subproblem, the quality of LP relaxations, the branching scheme as well as the column management. Finally, preliminary computarional experience is reported.     

A finitely converging cutting plane technique

We consider a new finitely convergent cutting plane algorithm for mixed integer linear programs in which the optimal objective value is assumed to be integral. The primary 'theoretical' contribution is the simplicity of the proof of convergence.     

A relaxed primal-dual path-following algorithm for linear programming

In this paper, we provide an easily satisfied relaxation condition for the primaldual interior path-following algorithm to solve linear programming problems. It is shown that the relaxed algorithm preserves the property of polynomial-time convergence. The computational results obtained by implementing two versions of the relaxed algorithm with slight modifications clearly demonstrate the potential in reducing computational efforts.Partially supported by the North Carolina Supercomputing Center, the 1993 Cray Research Award, and a National Science Council Research Grant of the Republic of China.     

A cutting plane algorithm for the General Routing Problem

The General Routing Problem (GRP) is the problem of finding a minimum cost route for a single vehicle, subject to the condition that the vehicle visits certain vertices and edges of a network. It contains the Rural Postman Problem, Chinese Postman Problem and Graphical Travelling Salesman Problem as special cases. We describe a cutting plane algorithm for the GRP based on facet-inducing inequalities and show that it is capable of providing very strong lower bounds and, in most cases, optimal solutions. Received: November 1998 / Accepted: September 2000?Published online March 22, 2001