排序方式: 共有6条查询结果,搜索用时 15 毫秒
1
1.
Abdelmoutalib Metrane François Soumis Issmail Elhallaoui 《European Journal of Operational Research》2010
In this paper, we propose a new Dantzig–Wolfe decomposition for degenerate linear programs with the non degenerate constraints in the master problem and the degenerate ones in the subproblem. We propose three algorithms. The first one, where some set of variables of the original problem are added to the master problem, corresponds to the Improved Primal Simplex algorithm (IPS) presented recently by Elhallaoui et al. [7]. In the second one, some extreme points of the subproblem are added as columns in the master problem. The third algorithm is a mixed implementation that adds some original variables and some extreme points of a subproblem to the master problem. Experimental results on some degenerate instances show that the proposed algorithms yield computational times that are reduced by an average factor ranging from 3.32 to 13.16 compared to the primal simplex of CPLEX. 相似文献
2.
Issmail Elhallaoui Abdelmoutalib Metrane François Soumis Guy Desaulniers 《Mathematical Programming》2010,123(2):345-370
Dynamic constraint aggregation is an iterative method that was recently introduced to speed up the linear relaxation solution
process of set partitioning type problems. This speed up is mostly due to the use, at each iteration, of an aggregated problem
defined by aggregating disjoint subsets of constraints from the set partitioning model. This aggregation is updated when needed
to ensure the exactness of the overall approach. In this paper, we propose a new version of this method, called the multi-phase
dynamic constraint aggregation method, which essentially adds to the original method a partial pricing strategy that involves
multiple phases. This strategy helps keeping the size of the aggregated problem as small as possible, yielding a faster average
computation time per iteration and fewer iterations. We also establish theoretical results that provide some insights explaining
the success of the proposed method. Tests on the linear relaxation of simultaneous bus and driver scheduling problems involving
up to 2,000 set partitioning constraints show that the partial pricing strategy speeds up the original method by an average
factor of 4.5. 相似文献
3.
Rosat Samuel Elhallaoui Issmail Soumis François Lodi Andrea 《Mathematical Programming》2017,166(1-2):327-367
Mathematical Programming - This paper concentrates on the addition of cutting planes to the integral simplex using decomposition (ISUD) of Zaghrouti et al. (Oper Res 62(2):435–449,... 相似文献
4.
Er-rajy Mohammed El Fadili Mohamed Hadni Hanine Mrabti Nidal Naceiri Zarougui Sara Elhallaoui Menana 《Structural chemistry》2022,33(3):973-986
Structural Chemistry - In this work, 2D-quantitative structure–activity relationship (QSAR) studies were performed on a set of 40 indolone derivative hybrids; the 40 indolone derivatives were... 相似文献
5.
Mohammed Saddoune Guy Desaulniers Issmail Elhallaoui François Soumis 《European Journal of Operational Research》2011,212(3):445-454
The integrated crew scheduling (ICS) problem consists of determining, for a set of available crew members, least-cost schedules that cover all flights and respect various safety and collective agreement rules. A schedule is a sequence of pairings interspersed by rest periods that may contain days off. A pairing is a sequence of flights, connections, and rests starting and ending at the same crew base. Given its high complexity, the ICS problem has been traditionally tackled using a sequential two-stage approach, where a crew pairing problem is solved in the first stage and a crew assignment problem in the second stage. Recently, Saddoune et al. (2010b) developed a model and a column generation/dynamic constraint aggregation method for solving the ICS problem in one stage. Their computational results showed that the integrated approach can yield significant savings in total cost and number of schedules, but requires much higher computational times than the sequential approach. In this paper, we enhance this method to obtain lower computational times. In fact, we develop a bi-dynamic constraint aggregation method that exploits a neighborhood structure when generating columns (schedules) in the column generation method. On a set of seven instances derived from real-world flight schedules, this method allows to reduce the computational times by an average factor of 2.3, while improving the quality of the computed solutions. 相似文献
6.
El Hachemi Nizar El Hallaoui Issmail Gendreau Michel Rousseau Louis-Martin 《Annals of Operations Research》2015,230(1):87-104
Annals of Operations Research - In this paper we present the solution to a weekly log-truck scheduling problem (LTSP) integrating the routing and scheduling of trucks where all goods are... 相似文献
1