constraint programming

New hybrid optimization algorithms for machine scheduling problems

  • Yunpeng Pan
  • Leyuan Shi
    • Categories Dynamic Programming, Scheduling Tags , ,

    Dynamic programming, branch-and-bound, and constraint programming are the standard solution principles for finding optimal solutions to machine scheduling problems. We propose a new hybrid optimization framework that integrates all three methodologies. The hybrid framework leads to powerful solution procedures. We demonstrate our approach through the optimal solution of the single-machine total weighted completion time scheduling … Read more

    Extending an Algebraic Modeling Language to Support Constraint Programming

  • Robert Fourer
  • David M. Gay
    • Categories Combinatorial Optimization, Modeling Languages and Systems Tags ,

    We describe extensions to algebraic modeling languages and their solver interfaces that will be needed to take advantage of constraint programming solvers, particularly in the area of combinatorial optimization. Citation Technical Report, Department of Industrial Engineering and Management Sciences, Northwestern University (2001); based on a shorter version that appeared in the Proceedings of the Third … Read more

    Facets of the Complementarity Knapsack Polytope

  • Ellis L. Johnson
  • George L. Nemhauser
  • Ismael de Farias
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms Tags , ,

    We present a polyhedral study of the complementarity knapsack problem, in which no auxiliary binary variables are introduced, but rather the inequalities are derived in the space of the continuous variables. Citation School of Industrial and Systems Engineering, GA Tech, under review Article Download View Facets of the Complementarity Knapsack Polytope

    OR Counterparts to AI Planning

  • Robert Fourer
    • Categories Integer Programming, Optimization Software and Modeling Systems Tags , , , ,

    The term Planning is not used in Operations Research in the sense that is most common in Artificial Intelligence. AI Planning does have many features in common with OR scheduling, sequencing, routing, and assignment problems, however. Current approaches to solving such problems can be broadly classified into four areas: Combinatorial Optimization, Integer Programming, Constraint Programming, … Read more