Ibaraki

General Problem Solversfor Combinatorial Optimization Problemsby Metaheuristics: 

General Problem Solvers for Combinatorial Optimization Problems by Metaheuristics Toshihide Ibaraki (with M. Yagiura and K. Nonobe) Kyoto University SIAM Conference on Optimization, Toronto, May 22, 2002

Slide2: 

Outline of the talk Combinatorial optimization problems Standard problems and general problem solvers Metaheuristics Implementations and computational results for some applications Future directions

Slide3: 

Combinatorial optimization problems minimize (maximize) f (x) subject to x∈F where feasible region F is combinatorial (discrete); e.g., a subset of , a subset of , edge set E of a graph G= (V, E ), vertex set of G, the set of all permutations of n elements, a family of subsets of an n-set, the set of mappings from an n-set to an m-set, etc. These are abundant in real world applications.

Slide4: 

General problem solvers?  Many combinatorial problems are difficult to solve (e.g., NP-hard) and need time to develop effective 　　　 　 algorithms. ⇒ General problem solvers are necessary.  In this direction, theory tells that all problems in NP 　　　　　can be reduced to an NP-hard problem A. ⇒ An algorithm for A can be used as a general problem solver.  The NP-hard problem A is difficult to solve exactly. ⇒ Approximate algorithm for A.

Slide5: 

The reductions between NP problems may blow up the sizes. The reductions may not preserve the metric of objective functions. (A good solution of A may not be a good solution of the target problem. ) ⇒ Natural reductions are desirable.

Slide6: 

 Different types of standard problems A1, A2, …, Ak must be prepared. ⇒ The problem instance at hand is formulated as an instance of an appropriate standard problem Ai, and is then solved by an algorithm for Ai..

Slide7: 

Our list of standard problems  Integer programming problem (IP); Commercially available.  (Weighted) constraint satisfaction problem (CSP, WCSP)  Maximum satisfiability problem (MAX SAT)  Set covering problem (SCP) Generalized assignment problem (GAP)  Generalized quadratic assignment problem (GQAP)  Resource constrained project scheduling problem (RCPSP)  Vehicle routing problem (VRP)  Cutting stock problem (CSTP)  2-Dimensional Packing Problem (2PP)  …

Slide8: 

● Each standard problem Ai must be as general as possible, while maintaining its special structure that allows a specialized solution strategy.

Slide9: 

● Algorithms for standard problems must be -- efficient in the practical sense, -- robust against small structural changes in the problems, -- easy to apply. Metaheuristics -- simulated annealing, -- genetic algorithms, -- iterated local search, -- tabu search, -- others

Slide10: 

Local search（LS） repeats replacing with a better solution in its neighborhood

Slide11: 

General framework of metaheuristics Repeat the following steps until a convergence criterion is satisfied. Step 1: Generate an initial solution (based on the compu- tational history so far). Step 2: Apply (generalized) local search to find a good locally optimal solution. Step 1 -- random generation, mutation, cross-over operation, path relinking, …, from population of good solutions obtained so far. Step 2 -- simple local search, random moves with controlled probability, best moves with a tabu list, local search with modified objective functions (e.g., with penalty of infeasibility), ...

Slide12: 

Our list of standard problems  Integer programming problem (IP); Commercially available.  (Weighted) constraint satisfaction problem (CSP, WCSP)  Maximum satisfiability problem (MAX SAT)  Set covering problem (SCP) Generalized assignment problem (GAP)  Generalized quadratic assignment problem (GQAP)  Resource constrained project scheduling problem (RCPSP)  Vehicle routing problem (VRP)  Cutting stock problem (CSTP)  2-Dimensional Packing Problem (2PP)  …

Slide13: 

Resource constrained project scheduling problem (RCPSP)  Activities j = 1,2, …, n.  Resources r =1, 2, …, R and s =1, 2, …, S. -- renewable resources (machine, manpower, etc.): Kr, t available in each period t, -- nonrenewable resources (budget, raw materials, etc.): Ks available in total.  Process mode m of each activity can be chosen. -- processing time pm, -- renewable resources kr,m,t in the t-th period after start, -- nonrenewable resources ks,m .

Slide14: 

a1 a3 a4 a2 a5 Resource 1 Resource 2 Time Available amount Available amount Consumed amount RCPSP Activities

Slide15: 

 Precedence constraints between activities.  Objective functions to minimize -- makespan, weighted sum of delays, …  Setup activities. Other constraints on modes, start times, completion 　 times and/or processing times.  Schedules to minimize the weighted sum of 　　　　　　　 penalties on constraints, -- hard and soft constraints. Constraints and objectives to be included

Slide16: 

Implementation of RCPSP  Tabu search.  Solutions are encoded as (m, ), where m is the modes of activities and  is a permutation of all activities.  Heuristic algorithm to construct a schedule from (m, ), which satisfies all hard constraints.  Reduced neighborhood obtained from the critical path analysis of the current schedule.  Automatic control of the tabu tenure.

Slide17: 

Computational experiment  Job shop scheduling  Benchmark problems in PSPLIB  Problems from real applications. 　・・・

Slide18: 

Ship scheduling  Transportation of natural resources; e.g., oil, iron ore, etc.  Activities: trips of given origins, destinations, and amounts of resources.  Two types of ships: proprietary and chartered.  Constraint on the storage level at the yard (tank).  Objective: Minimization of the number of chartered trips.

Slide19: 

Ship Scheduling

Slide20: 

Schedule table Proprietary ship 1 … Chartered ships Proprietary ship 2 Proprietary ship n

Slide21: 

Constraint on the levels of tanks (yards) Given: Consumption rate from each tank (yard). Capacities of tanks (yards): upper and lower bounds. level time upper bound lower bound unloading finished unloading started small ship large ship

Slide22: 

Typical instances  # activities: about 100.  Scheduling horizon: 1 year  # proprietary ships: 4  # chartered ships: 5  # destinations: 4 Computation time  Succeeded to obtain practically useful schedules in about 10 minutes on SUN SPARC ULTRA 2.

Slide23: 

Work space scheduling of large construction parts --- 2-dimensional packing of activities --- Large construction parts (ships, bridges, etc.) in a narrow factory. Each part occupies some area, and stays in the same place until completion. (Then it is removed by a crane.) Each part has its ready time, deadline, and processing time. Required resources change with time. ◆ ◆ ◆ Length L

Slide24: 

Solution strategy 1st stage: After discounting L to σL (e.g., σ = 0.9), apply RCPSP in the direction of t under the resource amount of σL.. 2nd stage: Apply RCPSP in the direction of L, assuming that each day has unit amount of its own resource (each activity consumes the resources of the scheduled days). ◆ ◆ 2nd １ｓｔ

Slide25: 

Our list of standard problems  Integer programming problem (IP); Commercially available.  (Weighted) constraint satisfaction problem (CSP, WCSP)  Maximum satisfiability problem (MAX SAT)  Set covering problem (SCP) Generalized assignment problem (GAP)  Generalized quadratic assignment problem (GQAP)  Resource constrained project scheduling problem (RCPSP)  Vehicle routing problem (VRP)  Cutting stock problem (CSTP)  2-Dimensional Packing Problem (2PP)  …

2-Dimensional packing problem: 

2-Dimensional packing problem Input: A set of rectangles I = {1,2,…,n}; each i has several modes. mode: (width, height, spatial cost functions) Output: Modes and x, y coordinates of all rectangles. It is asked to place all rectangles in the plane without overlap so that the objective function is minimized.

Mathematical formulation: 

pmax(π) = max i pi(μi (π))(xi(π)) (ｓimilarly, qmax(π) ) minimize　　g( pmax(π), qmax(π)) + c(μ(π)) subject to : no overlapping Mathematical formulation Input: Modes (wi(k), hi(k), pi(k)(xi), qi(k)(yi)) for i∈{1,2,…,n} and k∈Mi , objective functions : g and c. Output : A solution π, i.e., packing (xi(π), yi(π)) (lower left corner), mode μi(π), for all i∈{1,2,…,n}.

Slide28: 

Functions pi(k)(xi) and qi(k)(yi) can be very general: These can be nonconvex, noncontinuous as long as piecewise linear. Objective function g( pmax(π), qmax(π)) is nondecreasing in pmax(π) and qmax(π) .

Example１: 

Example１ -- smallest area packing -- 0 x y

Example 2 -- scheduling problem --: 

Building block i ∈{ 1, 2, …, n }: length hi , processing time wi , ready time si , due date di hi Work space　L Example 2 -- scheduling problem -- bring in carry out Determine the place and the start time of each block.

Slide31: 

Rectangle: (processing time) × (length) block i 0 place yi L wi due date 　di ready time 　　　 si hi start time xi x pi(xi) 0 si di - wi y 0 L - hi cost function objective function 　g(p, q) = p + q qi(yi) work space

Slide32: 

Representation of solutions Direct search of rectangle locations is not appropriate, 　 because there are uncountably many solutions. Sequence pair (Murata, Nakatake, Fujiyoshi and Kajitani（1995）): Relative nonoverlapping positions are specified by a sequence pair of rectangles.

Search strategy of solutions: 

Search strategy of solutions Local search is applied to search good sequence pairs and modes of rectangles. Shift, swap and change mode neighborhoodｓ reduced by critical path ideas. 2. Given a sequence pair, exact optimal locations 　 are computed by dynamic programming algorithm in polynomial time.

Slide34: 

Packing rectangles into a small area

Conclusion and discussion: 

Conclusion and discussion Further improvement of metaheuristic algorithms. Increasing the formulation power of standard problems. Other standard problems. User interfaces. Supports for modeling the problems in applications.