References of "Leus, Roel"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailRobust optimization for resource-constrained project scheduling with uncertain activity durations
Artigues, Christian; Leus, Roel; Talla Nobibon, Fabrice ULg

in Flexible Services and Manufacturing Journal (2013), 25(1-2),

The purpose of this paper is to propose models for project scheduling when there is considerable uncertainty in the activity durations, to the extent that the decision maker cannot with confidence ... [more ▼]

The purpose of this paper is to propose models for project scheduling when there is considerable uncertainty in the activity durations, to the extent that the decision maker cannot with confidence associate probabilities with the possible scenarios. Our modeling techniques stem from robust optimization, which is a theoretical framework that enables the decision maker to produce solutions that will have a reasonably good objective value under any likely input data scenario. We develop and implement a scenario-relaxation algorithm and a scenario-relaxationbased heuristic. The first algorithm produces optimal solutions but requires excessive running times even for medium-sized instances; the second algorithm produces high-quality solutions for medium-sized instances and outperforms two benchmark heuristics. [less ▲]

Detailed reference viewed: 56 (7 ULg)
Full Text
See detailComplexity results and exact algorithms for robust knapsack problems
Talla Nobibon, Fabrice ULg; Leus, Roel

Scientific conference (2011, March 04)

Detailed reference viewed: 16 (0 ULg)
Full Text
Peer Reviewed
See detailColoring Graphs Using Two Colors while Avoiding Monochromatic Cycles
Talla Nobibon, Fabrice ULg; Hurkens, Cor A. J.; Leus, Roel et al

in INFORMS Journal on Computing (2011)

We consider the problem of deciding whether a given directed graph can be vertex partitioned into two acyclic subgraphs. Applications of this problem include testing rationality of collective consumption ... [more ▼]

We consider the problem of deciding whether a given directed graph can be vertex partitioned into two acyclic subgraphs. Applications of this problem include testing rationality of collective consumption behavior, a subject in microeconomics. We prove that the problem is NP-complete even for oriented graphs and argue that the existence of a constant-factor approximation algorithm is unlikely for an optimization version that maximizes the number of vertices that can be colored using two colors while avoiding monochromatic cycles. We present three exact algorithms—namely, an integer-programming algorithm based on cycle identification, a backtracking algorithm, and a branch-and-check algorithm. We compare these three algorithms both on real-life instances and on randomly generated graphs. We find that for the latter set of graphs, every algorithm solves instances of considerable size within a few seconds; however, the CPU time of the integer-programming algorithm increases with the number of vertices in the graph more clearly than the CPU time of the two other procedures. For real-life instances, the integer-programming algorithm solves the largest instance in about a half hour, whereas the branch-and-check algorithm takes approximately 10 minutes and the backtracking algorithm less than 5 minutes. Finally, for every algorithm, we also study empirically the transition from a high to a low probability of a YES answer as a function of the number of arcs divided by the number of vertices. [less ▲]

Detailed reference viewed: 22 (1 ULg)
Full Text
See detailPROJECT SCHEDULING WITH MODULAR PROJECT COMPLETION ON A BOTTLENECK RESOURCE
Coolen, Kris; Wenchao, Wei; Talla Nobibon, Fabrice ULg et al

Report (2011)

In this paper, we model a research-and-development project as consisting of several modules, with each module containing one or more activities. We examine how to schedule the activities of such a project ... [more ▼]

In this paper, we model a research-and-development project as consisting of several modules, with each module containing one or more activities. We examine how to schedule the activities of such a project in order to maximize the expected profit when the activities have a probability of failure and when an activity’s failure can cause its module and thereby the overall project to fail. A module succeeds when at least one of its constituent activities is successfully executed. All activities are scheduled on a scarce resource that is modeled as a single machine. We describe various policy classes, establish the relationship between the classes, develop exact algorithms to optimize over two different classes (one dynamic program and one branch-and-bound algorithm), and examine the computational performance of the algorithms on two randomly generated instance sets. [less ▲]

Detailed reference viewed: 12 (0 ULg)
Full Text
See detailRobust maximum weighted independent-set problems on interval graphs
Talla Nobibon, Fabrice ULg; Leus, Roel

Report (2011)

We study the maximum weighted independent-set problem on interval graphs with uncertainty on the vertex weights. We use the absolute robustness criterion and the min-max regret criterion to evaluate ... [more ▼]

We study the maximum weighted independent-set problem on interval graphs with uncertainty on the vertex weights. We use the absolute robustness criterion and the min-max regret criterion to evaluate solutions. For a discrete scenario set, we nd that the problem is NP-hard for each of the robustness criteria; we also provide pseudo-polynomial time algorithms when there is a constant number of scenarios and show that the problem is strongly NP-hard when the set of scenarios is unbounded. When the scenario set is a Cartesian product, we prove that the problem is equivalent to a maximum weighted independent-set problem on the same interval graph but without uncertainty for the rst objective function and that the scenario set can be reduced for the second objective function. [less ▲]

Detailed reference viewed: 17 (0 ULg)