The generation expansion planning is one of complex mixed-integer optimization problems, which involves a large number of continuous or discrete decision variables and constraints. In this paper, an interior point wit...The generation expansion planning is one of complex mixed-integer optimization problems, which involves a large number of continuous or discrete decision variables and constraints. In this paper, an interior point with cutting plane （IP/CP） method is proposed to solve the mixed-integer optimization problem of the electrical power generation expansion planning. The IP/CP method could improve the overall efficiency of the solution and reduce the computational time. Proposed method is combined with the Bender＇s decomposition technique in order to decompose the generation expansion problem into a master investment problem and a slave operational problem. The numerical example is presented to compare with the effectiveness of the proposed algorithm.展开更多
In this papert a cutting planelnethod is presented for solving the linear BLPP.An optimality criterion for the linear BLPP is derived from two related linear programsconstructed by using the complementarity conditions...In this papert a cutting planelnethod is presented for solving the linear BLPP.An optimality criterion for the linear BLPP is derived from two related linear programsconstructed by using the complementarity conditions for the second level problem. Twotypes of cutting planes are developed in order to deal with different situations and to obtaina maximal efficiency. The method makes use of the special cuts and the implicit vertexenumeration idea to avoid some drawbacks in some existing cuttillg plane methods. Thealgorithm can be proved to be finitely convergent.展开更多
Although concern has been recently expressed with regard to the solution to the non-convex problem, convex optimization is still important in machine learning, especially when the situation requires an interpretable m...Although concern has been recently expressed with regard to the solution to the non-convex problem, convex optimization is still important in machine learning, especially when the situation requires an interpretable model. Solution to the convex problem is a global minimum, and the final model can be explained mathematically. Typically, the convex problem is re-casted as a regularized risk minimization problem to prevent overfitting. The cutting plane method (CPM) is one of the best solvers for the convex problem, irrespective of whether the objective function is differentiable or not. However, CPM and its variants fail to adequately address large-scale data-intensive cases because these algorithms access the entire dataset in each iteration, which substantially increases the computational burden and memory cost. To alleviate this problem, we propose a novel algorithm named the mini-batch cutting plane method (MBCPM), which iterates with estimated cutting planes calculated on a small batch of sampled data and is capable of handling large-scale problems. Furthermore, the proposed MBCPM adopts a "sink" operation that detects and adjusts noisy estimations to guarantee convergence. Numerical experiments on extensive real-world datasets demonstrate the effectiveness of MBCPM, which is superior to the bundle methods for regularized risk minimization as well as popular stochastic gradient descent methods in terms of convergence speed.展开更多
With the rapid development of artificial intelligence in recent years,applying various learning techniques to solve mixed-integer linear programming(MILP)problems has emerged as a burgeoning research domain.Apart from...With the rapid development of artificial intelligence in recent years,applying various learning techniques to solve mixed-integer linear programming(MILP)problems has emerged as a burgeoning research domain.Apart from constructing end-to-end models directly,integrating learning approaches with some modules in the traditional methods for solving MILPs is also a promising direction.The cutting plane method is one of the fundamental algorithms used in modern MILP solvers,and the selection of appropriate cuts from the candidate cuts subset is crucial for enhancing efficiency.Due to the reliance on expert knowledge and problem-specific heuristics,classical cut selection methods are not always transferable and often limit the scalability and generalizability of the cutting plane method.To provide a more efficient and generalizable strategy,we propose a reinforcement learning(RL)framework to enhance cut selection in the solving process of MILPs.Firstly,we design feature vectors to incorporate the inherent properties of MILP and computational information from the solver and represent MILP instances as bipartite graphs.Secondly,we choose the weighted metrics to approximate the proximity of feasible solutions to the convex hull and utilize the learning method to determine the weights assigned to each metric.Thirdly,a graph convolutional neural network is adopted with a self-attention mechanism to predict the value of weighting factors.Finally,we transform the cut selection process into a Markov decision process and utilize RL method to train the model.Extensive experiments are conducted based on a leading open-source MILP solver SCIP.Results on both general and specific datasets validate the effectiveness and efficiency of our proposed approach.展开更多
文摘The generation expansion planning is one of complex mixed-integer optimization problems, which involves a large number of continuous or discrete decision variables and constraints. In this paper, an interior point with cutting plane （IP/CP） method is proposed to solve the mixed-integer optimization problem of the electrical power generation expansion planning. The IP/CP method could improve the overall efficiency of the solution and reduce the computational time. Proposed method is combined with the Bender＇s decomposition technique in order to decompose the generation expansion problem into a master investment problem and a slave operational problem. The numerical example is presented to compare with the effectiveness of the proposed algorithm.
文摘In this papert a cutting planelnethod is presented for solving the linear BLPP.An optimality criterion for the linear BLPP is derived from two related linear programsconstructed by using the complementarity conditions for the second level problem. Twotypes of cutting planes are developed in order to deal with different situations and to obtaina maximal efficiency. The method makes use of the special cuts and the implicit vertexenumeration idea to avoid some drawbacks in some existing cuttillg plane methods. Thealgorithm can be proved to be finitely convergent.
基金Project supported by the National Key R&D Program of China(No.2018YFB0204300)the National Natural Science Foundation of China(Nos.61872376 and 61806216)。
文摘Although concern has been recently expressed with regard to the solution to the non-convex problem, convex optimization is still important in machine learning, especially when the situation requires an interpretable model. Solution to the convex problem is a global minimum, and the final model can be explained mathematically. Typically, the convex problem is re-casted as a regularized risk minimization problem to prevent overfitting. The cutting plane method (CPM) is one of the best solvers for the convex problem, irrespective of whether the objective function is differentiable or not. However, CPM and its variants fail to adequately address large-scale data-intensive cases because these algorithms access the entire dataset in each iteration, which substantially increases the computational burden and memory cost. To alleviate this problem, we propose a novel algorithm named the mini-batch cutting plane method (MBCPM), which iterates with estimated cutting planes calculated on a small batch of sampled data and is capable of handling large-scale problems. Furthermore, the proposed MBCPM adopts a "sink" operation that detects and adjusts noisy estimations to guarantee convergence. Numerical experiments on extensive real-world datasets demonstrate the effectiveness of MBCPM, which is superior to the bundle methods for regularized risk minimization as well as popular stochastic gradient descent methods in terms of convergence speed.
基金supported by the National Key R&D Program of China(Grant No.2022YFB2403400)National Natural Science Foundation of China(Grant Nos.11991021 and 12021001)。
文摘With the rapid development of artificial intelligence in recent years,applying various learning techniques to solve mixed-integer linear programming(MILP)problems has emerged as a burgeoning research domain.Apart from constructing end-to-end models directly,integrating learning approaches with some modules in the traditional methods for solving MILPs is also a promising direction.The cutting plane method is one of the fundamental algorithms used in modern MILP solvers,and the selection of appropriate cuts from the candidate cuts subset is crucial for enhancing efficiency.Due to the reliance on expert knowledge and problem-specific heuristics,classical cut selection methods are not always transferable and often limit the scalability and generalizability of the cutting plane method.To provide a more efficient and generalizable strategy,we propose a reinforcement learning(RL)framework to enhance cut selection in the solving process of MILPs.Firstly,we design feature vectors to incorporate the inherent properties of MILP and computational information from the solver and represent MILP instances as bipartite graphs.Secondly,we choose the weighted metrics to approximate the proximity of feasible solutions to the convex hull and utilize the learning method to determine the weights assigned to each metric.Thirdly,a graph convolutional neural network is adopted with a self-attention mechanism to predict the value of weighting factors.Finally,we transform the cut selection process into a Markov decision process and utilize RL method to train the model.Extensive experiments are conducted based on a leading open-source MILP solver SCIP.Results on both general and specific datasets validate the effectiveness and efficiency of our proposed approach.
