References of "INFORMS Journal on Computing"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailScenario Trees and Policy Selection for Multistage Stochastic Programming Using Machine Learning
Defourny, Boris; Ernst, Damien ULg; Wehenkel, Louis ULg

in INFORMS Journal on Computing (2013), 25(3), 488-501

In the context of multistage stochastic optimization problems, we propose a hybrid strategy for generalizing to nonlinear decision rules, using machine learning, a finite data set of constrained vector ... [more ▼]

In the context of multistage stochastic optimization problems, we propose a hybrid strategy for generalizing to nonlinear decision rules, using machine learning, a finite data set of constrained vector-valued recourse decisions optimized using scenario-tree techniques from multistage stochastic programming. The decision rules are based on a statistical model inferred from a given scenario-tree solution and are selected by out-of-sample simulation given the true problem. Because the learned rules depend on the given scenario tree, we repeat the procedure for a large number of randomly generated scenario trees and then select the best solution (policy) found for the true problem. The scheme leads to an ex post selection of the scenario tree itself. Numerical tests evaluate the dependence of the approach on the machine learning aspects and show cases where one can obtain near-optimal solutions, starting with a “weak” scenario-tree generator that randomizes the branching structure of the trees. [less ▲]

Detailed reference viewed: 78 (18 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: 21 (1 ULg)