China
Africa
Explore chapters and articles related to this topic
Nonlinear Programming
Published in Albert G. Holzman, Mathematical Programming, 2020
One clear disadvantage of the cutting plane methods is that the size of the linear programming subproblems increases from iteration to iteration, since cutting plane constraints are always added to the existing set of constraints but are never deleted. Some later works on cutting plane methods center on the question of dropping inactive constraints or, more generally, approximating the feasible set of the nonlinear program by linear constraints without nesting. Topkis [145] has derived such a method and proved convergence under assumptions similar to those stated above. Eaves and Zangwill [146] have studied cutting plane methods in a more general framework which contains the KCG, Veinott, Topkis, and several other versions of cutting plane algorithms as special cases.
Integer linear programming for mining systems
Published in Amit Kumar Gorai, Snehamoy Chatterjee, Optimization Techniques and their Applications to Mine Systems, 2023
Amit Kumar Gorai, Snehamoy Chatterjee
The cutting plane method is one of the optimization methods that iteratively adds valid inequalities to the original problem to narrow down the search area enclosed by the constraints or cuts while retaining the feasible points. The step-wise solution algorithm of the cutting plane method is explained below:
Optimization Techniques
Published in J.C. Das, Power System Analysis, 2017
In the cutting plane method, additional constraints, called cutting planes, are introduced, which create a sequence of continuous problems. The solution of these continuous problems is driven toward the best integer solution.
A multi-road quasi network flow model for the vertical alignment optimization of a road network
Published in Engineering Optimization, 2023
Khandoker Md Ayman, Warren Hare, Yves Lucet
Minimizing construction costs of a single road is challenging, and becomes harder for an entire road network, forcing researchers to resort to heuristics (Jha and Schonfeld 2004; Jong and Schonfeld 2003; Richard, Huang, and Bouazara 2004; Tan 1999) and dynamic programming (Li et al.2013; Tan 2000). Previous research on optimizing road networks is limited and focuses on optimizing earthwork costs and finding the shortest path to move the earthwork materials for a fixed vertical alignment. For example, C. Liu and Lu (2015) proposed a linear programming model with an integrated Floyd–Warshall algorithm to find the shortest path to move earthwork materials. However, the road network's horizontal alignments were predetermined in this model, and the vertical alignment was fixed. Hence, this model only optimized the movement of earthwork materials. Later, Yi and Lu (2016) improved this model and presented a mixed-integer linear programming model with a cutting plane method for generating a continuous road network but for a fixed vertical alignment. Additionally, because it used the cutting plane method iteratively, this model (Yi and Lu 2016) did not guarantee global optimality.
A simple effective heuristic for embedded mixed-integer quadratic programming
Published in International Journal of Control, 2020
Reza Takapoui, Nicholas Moehle, Stephen Boyd, Alberto Bemporad
There are a variety of methods for solving (1) exactly. When all of the nonconvex sets in (1) are finite, the simplest method is brute force; enumerating through all possible combinations of discrete variables, solving a convex optimisation problem for each possible combination, and finding the point with the smallest objective value. Other methods such as branch-and-bound (Lawler & Wood, 1966) and branch-and-cut (Stubbs & Mehrotra, 1999) are guaranteed to find the global solution. Cutting plane methods (Chvátal, Cook, & Hartmann, 1989; Gomory et al., 1958) rely on solving the relaxation and adding a linear constraint to drive the solution towards being integer. Special purpose methods have been introduced for some specific subclasses of (1). Unfortunately, these methods have non-polynomial worst-case runtime, and are often burdensome to use in practice, especially for embedded optimisation, where runtime, memory limits, and code simplicity are prioritised. Also, these methods suffer from a large variance in the algorithm runtime.
Ambulance redeployment and dispatching under uncertainty with personnel workload limitations
Published in IISE Transactions, 2018
Shakiba Enayati, Osman Y. Özaltın, Maria E. Mayorga, Cem Saydam
where set denotes the subdifferential of Dℓ(μℓ), . The cutting plane method, however, converges slowly on practical instances. Therefore, we use a proximal bundle method proposed by Lubin et al. (2013) that adds a weighted quadratic penalty to the objective function (12a): where μ+ i is the current proximity center and τ ⩾ 0 is the weight of the quadratic penalty term. We use a slightly modified version of the updating rules proposed by Lubin et al. (2013). Table 2 summarizes the steps in our implementation of the proximal bundle method.