This work presents the two-stage stochastic red-blue set covering problem (2S-SRBSC). The red-blue set covering problem (RBSC) selects a subcollection of sets to cover all the blue elements while minimizing the number...
详细信息
This work presents the two-stage stochastic red-blue set covering problem (2S-SRBSC). The red-blue set covering problem (RBSC) selects a subcollection of sets to cover all the blue elements while minimizing the number of red elements covered. Although RBSC has many application areas, such as classification and fraud detection, it does not capture randomness related to set membership and color uncertainty or any sense of recourse in response to the uncertainty. This work motivates these considerations via a fraud-prevention problem mortgage lenders face in practice. 2S-SRBSC is introduced to address this. In the proposed problem, uncertainty is represented via scenarios, and the decision-maker pays for sets in the first stage and has recourse to cover blue elements in the second stage that remain uncovered post-uncertainty. Different variants of 2S-SRBSC are considered, highlighting how they can model the real-life problem mortgage lenders face. In the case of 2S-SRBSC with simple recourse, a Benders decomposition (BD) and Benders dual decomposition (BDD) are presented and implemented in a commercial branch-and-cut solver. The resulting BDD subproblems yield cuts that are significantly tighter than those BD produces. The decompositions are tested and offer improvements in terms of solution quality and time for large-scale instances relative to the extensive form. Furthermore, the BDD exhibits desirable performance for instances where the commercial solver can quickly solve the mixed-binary subproblems. This work presents the first computational experience with decomposition algorithms applied to 2S-SRBSC problems.
A greedy randomized adaptive search procedure (GRASP) is proposed for the approximate solution of general mixed binary programming problems (MBP). Examples are provided of practical applications that can be formulated...
详细信息
A greedy randomized adaptive search procedure (GRASP) is proposed for the approximate solution of general mixed binary programming problems (MBP). Examples are provided of practical applications that can be formulated as MBP requiring the solution of a large number of problem instances. This justifies, from both a practical and a theoretical perspective, the development of stopping rules aimed at controlling the number of iterations in a GRASP. To this end, a bayesian framework is laid down, two different prior distributions are proposed and stopping conditions are explicitly derived in analytical form. Numerical evidence shows that the stopping rules lead to an optimal trade-off between accuracy and computational effort, saving from unneeded iterations and still achieving good approximations.
When optimizing traffic systems using time-expanded network flow models, traffic congestion is an important consideration because it can decrease both the discharge traffic flow rate and speed. One widely used modelin...
详细信息
When optimizing traffic systems using time-expanded network flow models, traffic congestion is an important consideration because it can decrease both the discharge traffic flow rate and speed. One widely used modeling framework is the Cell Transmission Model (CTM) (see Daganzo, Transp Res-B 28(4):269-287, 1994, Transp Res-B 29(2):79-93, 1995), which is implemented in a linear program (LP) in Ziliaskopoulos (Transp Sci 34(1):37-49, 2000). While the CTM models the reduction in speed associated with congestion and the backward propagation of congestion, it does not properly model the reduction in discharge flow from a bottleneck after the onset of congestion. This paper discusses this issue and proposes a generalization of the CTM that takes into account this important phenomena. Plainly, an optimization that does not consider this important negative result of congestion can be problematic, e.g., in an evacuation setting such an optimization would assume that congestion does not impact network clearance time, which can result in poor evacuation strategies. In generalizing the CTM, a fairly simple modification is made, yet it can have significant impacts on the results. For instance, we show that for the generalized CTM the traffic holding (a result of the linearization of the CTM flow constraints) plays a more harmful role, which thus requires a scheme to eliminate traffic holding. In this paper, we propose a mixedbinary program to eliminate traffic holding, along with methods to improve solvability.
During the last decades, research in multi-objective optimisation has seen considerable growth. However, this activity has been focused on linear, non-linear, and combinatorial optimisation with multiple objectives. M...
详细信息
During the last decades, research in multi-objective optimisation has seen considerable growth. However, this activity has been focused on linear, non-linear, and combinatorial optimisation with multiple objectives. Multi-objective mixed integer (linear or non-linear) programming has received considerably less attention. In this paper we propose an algorithm to compute a finite set of non-dominated points/efficient solutions of a bi-objective mixedbinary optimisation problems for which the sub-problems obtained when fixing the binary variables are convex, and there is a finite set of feasible binary variable vectors. Our method uses bound sets and exploits the convexity property of the sub-problems to find a set of efficient solutions for the main problem. Our algorithm creates and iteratively updates bounds for each vector in the set of feasible binary variable vectors, and uses these bounds to guarantee that a set of exact non-dominated points is generated. For instances where the set of feasible binary variable vectors is too large to generate such provably optimal solutions within a reasonable time, our approach can be used as a matheuristic by heuristically selecting a promising subset of binary variable vectors to explore. This investigation is motivated by the problem of beam angle optimisation arising in radiation therapy planning, which we solve heuristically to provide numerical results.
The most efficient state-of-the-art methods to build classification trees are greedy heuristics (e.g. CART) that may fail to find underlying characteristics in datasets. Recently, exact linear formulations that have s...
详细信息
The most efficient state-of-the-art methods to build classification trees are greedy heuristics (e.g. CART) that may fail to find underlying characteristics in datasets. Recently, exact linear formulations that have shown better accuracy were introduced. However they do not scale up to datasets with more than a few thousands data points. In this paper, we introduce four new formulations for building optimal trees. The first one is a quadratic model based on the well-known formulation of Bertsimas et al. We then propose two different linearizations of this new quadratic model. The last model is an extension to real -valued datasets of a flowformulation limited to binary datasets (Aghaei et al.). Each model is introduced for both axis -aligned and oblique splits. We further prove that our new formulations have stronger continuous relaxations than existing models. Finally, we present computational results on 22 standard datasets with up to thousands of data points. Our exact models have reduced solution times with learning performances as strong or significantly better than state of the art exact approaches.
暂无评论