（运筹学与控制论专业论文）哈明距离下的逆优化问题及多物品的制造与分配问题.pdf

望望生! 翌塑! 望! 塑皇塑堡丝望丝丝绝盟! 堡塑堕! 竺竺堡! 塑 v 摘要 本文主要研究两大类问题：哈明距离下的逆优化问题和多物品的生产与分配问题 对一个给定的( 组合) 优化问题，逆优化问题研究如何尽可能少地改变原问题中的 权参数，使得某些给定的解是问题在新的权参数下的最优解由于该类问题不仅有很 重要的理论研究价值，而且有很大的实际应用价值，因此引起了许多学者的重视许 多文章研究了在f 1 ，k 和1 2 范数下的逆优化问题尽管哈明距离下的逆优化问题在实 际生活中有许多应用，但很少有文章讨论该类问题本文我们研究哈明距离下的逆优 化问题 由于物品的制造与分配问题有很重要的理论研究与实际应用价值，因此引起了许 多学者的注意该问题可以描述为：有一些客户，他们需要一定数量的产品，这些产 品是通过一些工厂加工制造生产出来的，并通过一些分配中心运送到每个客户如何 安排原材料购置、产品的生产与分配，使得总的费用最小本文我们也将研究多物品 的制造与分配问题 在第二章，我们研究以下的求和型哈明距离下的赋权逆最小支撑树问题：对给定 的一个连通无向图g ，每条边都有一个权和改造费用令严为图g 的一个支撑树如 何改变图的边权向量使得t o 为图g 在新的权向量下的一个最小支撑树，且在哈明距 离下的总的改造费用最小我们讨论了三种模型：无界情形，带禁忌边的无界情形和 有界情形应用求二分图的赋权顶点覆盖方法以及求最小割的算法等求解所建立的数 学模型，从而得出这三类问题都是强多项式时间可解的 在第三章，我们研究如下的约束瓶颈型哈明距离下的逆最小支撑树问题：对给定 的一个连通无向图g ，每条边都有一个权和改造费用，t o 为图g 的一个支撑树如何 改变图的边权向量使得：( 1 ) t o 为图g 在新的权向量下的一个最小支撑树，( 2 ) 在哈 明距离下的总的改造费用不超过给定的值，( 3 ) 改变的边的改造费用的最大值尽可能 地小我们讨论了三种模型：无界情形，标准情形和约束情形应用二分图的瓶颈型 赋权顶点覆盖方法及二分法等得出这三类问题都是强多项式时间可解的 在第四章，我们首先讨论了求和型哈明距离下的中心选址改造问题，该问题可以 描述为：对给定的一个连通无向图g ，每条边都有一个长度和改造费用，如何改变图 的边长度向量使得在新的长度向量下从给定的顶点8 到网络的其它顶点的距离不超过 给定的上界，且在哈明距离下的总的改造费用最小我们利用把集覆盖问题的实例l 一 归约到该问题的实例，证明了对该问题构造一个近似性能比为o ( 1 0 9l v t ) 的近似算法 是p 困难的接着我们研究了如下的瓶颈型哈明距离下的中心选址改造问题：如何 改变图的边长度向量使得在新的长度向量下从给定的顶点s 到网络的其它顶点的距离 不超过给定的上界，且改变的边的改造费用的最大值尽可能地小我们给出了该问题 的一个强多项式算法 在第五章，我们研究了如下的求和型哈明距离下的最短路改造问题：对给定的一 个连通无向图g ，每条边都有一个长度和改造费用，我们要求改变图的边长度向量使 得在新的长度向量下从给定的顶点8 t 到顶点t i ( i = 1 ，2 ，r ) 的距离不超过给定的上 界也，且在哈明距离下的总的改造费用最小我们利用把3 - s a t 问题的实例多项式时 间归约到该问题的实例，证明了该问题是强j v p 困难的对该问题的一类特殊问题： 链网络下的单发点、单收点的求和型哈明距离下的最短路改造问题，我们利用把背包 问题的实例多项式时间归约到该问题的实例，证明了该问题是n p 困难的同时对该 问题给出了一个伪多项式时间的动态规划算法 在第六章，我们研究了如下的多物品的生产与分配问题：有多个客户，他们需要 不同的物品，这些物品是由工厂生产或通过物品供应商直接提供并运送到一些分配中 心( d c ) ，并统一由分配中心供给如果某类物品是由工厂生产，则该类物品及某些物 品是由原材料供应商提供给该工厂的原材料按某种比例加工生产得到的一个客户由 一个分配中心服务如何安排工厂的生产，如何从物品( 原材料) 供应商进货，哪些分 配中心投入使用，如何决定分配中心服务客户的方式以及如何安排运货等使得总的费 用最小我们把该问题转化为混合整数规划问题，利用b e n d e r s 分解方法给出了求解 该问题的算法另外，我们还考虑了一类广义的多物品的生产与分配问题 在第七章，我们研究了如下的最小分配费用流问题：有多个客户，只有一个物品 供应商每个客户需要一定数量的物品，该物品是通过一些分配工厂或一些物品中间 商提供给客户某客户或中间商按一定的比例从某分配工厂得到的货物如何从物品 供应商处进货，如何安排运货等使得总的费用( 运输费用，储存费用) 最小我们讨论 了该问题的基本可行图的性质并给出了一个求解该问题的原始基本可行解的算法利 用网络单纯型法，我们解决了该类最小分配费用流问题本章我们还研究了如何得到 增广网络问题的一个可行基 最后，我们总结了该论文的研究成果，并对这两个领域中的研究问题给出了一些 初步的探讨 关键词：逆优化问题；网络改进问题；哈明距离；计算复杂性；多物品的生产与 分配；最小分配费用流 d o c t o r a f d i s s e r t a t i o no fz h e j i a n gu n i v e r s i t y a b s tr a c t v l l t h i sd i s s e r t a t i o ns t u d i e st w ok i n d so fp r o b l e m s ，n a m e l y ，t h ei n v e r s eo p t i m i z a t i o n p r o b l e m su n d e rh a m m i n gd i s t a n c ea n dm u l t i c o m m o d i t yp r o d u c t i o na n dd i s t r i b u t i o n p r o b l e m s f o ra g i v e n ( c o m b i n a t o r i a l ) o p t i m i z a t i o np r o b l e m ，t h ei n v e r s eo p t i m i z a t i o np r o b l e m i st of i n dam i n i m a la d j u s t m e n to ft h ep a r a m e t e r s ( c o s t s ，c a p a c i t i e s ，e t c ) o ft h ep r o b - l e ms u c ht h a tt h eg i v e ns o l u t i o n sb e c o m eo p t i m u m d u et ot h e i rt h e o r e t i c a li m p o r t a n c e a n dw i d er a n g eo fa p p l i c a t i o n s ，t h ei n v e r s eo p t i mi z a t i o np r o b l e m sh a v ea t t r a c t e dm u c h a t t e n t i o n t h e r ea r em a n yp a p e r sd i s c u s s i n gi n v e r s eo p t i m i z a t i o np r o b l e m su n d e r1 1 ， l o oa n d1 2n o r m b u tl i t t l ei sk n o w na b o u ti n v e r s eo p t i m i z a t i o np r o b l e m su n d e rh a m m i n gd i s t a n c e w em a yf i n da p p l i c a t i o n so ft h ei n v e r s eo p t i m i z a t i o np r o b l e m su n d e r h a m m i n gd i s t a n c ei n r e a lw o r l d i nt h i sd i s s e r t a t i o n ，w es t u d yi n v e r s eo p t i m i z a t i o n p r o b l e m su n d e rh a m m i n gd i s t a n c e d u et oi t st h e o r e t i c a la n dp r a c t i c a li m p o r t a n c e ，m u l t i c o m m o d i t yp r o d u c t i o na n d d i s t r i b u t i o np r o b l e mh a sa t t r a c t e dav a s ta m o u n to fa t t e n t i o no fa c a d e m i cr e s e a r c h e r s t h ep r o b l e mc a nb ed e s c r i b e da sf o l l o w s ：t h e r ea r es e v e r a lp r o d u c t sp r o d u c e da t s e v e r a lp l a n t s t h e r ei sad e t e r m i n a t ed e m a n df o re a c h p r o d u c ta te a c hc u s t o m e rl o c a - t i o n t h ec u s t o m e rd e m a n di ss a t i s f i e db yt r a n s i t i n gp r o d u c t sv i as o m eo fd i s t r i b u t i o n c e n t e r s ( d c s ) t h ep r o b l e mi sh o wt oa r r a n g ep r o d u c t i o na n dd i s t r i b u t i o ns o a st o m i n i m i z et h et o t a lc o s t s i nt h i sd i s s e r t a t i o n ，w ea l s oc o n s i d e rt h ep r o b l e m s i nc h a p t e r2 ，w ec o n s i d e rt h ef o l l o w i n gw e i g h t e di n v e r s em i n i m u ms p a n n i n gt r e e p r o b l e mu n d e rt h es u m t y p eh a m m i n gd i s t a n c e ：w ea r eg i v e nac o n n e c t e du n d i r e c t e d n e t w o r kg ，e a c he d g eh a sam o d i f i c a t i o nc o s ta n dan o n n e g a t i v ew e i g h t l e tt ob e as p a n n i n gt r e eo fg w ea r ea s k e dt om o d i f yt h ee d g ew e i g h t ss u c ht h a tt oi st h e m i n i m u mw e i g h ts p a n n i n gt r e ea n dt h et o t a lm o d i f i c a t i o nc o s to fm o d i f i e de d g e si s m i n i m i z e du n d e rt h eh a m m i n gd i s t a n c e t h r e em o d e l sa r ec o n s i d e r e d ：u n b o u n d e d c a s e ，u n b o u n d e dc a s ew i t hf o r b i d d e ne d g e sa n db o u n d e dc a s e i nt e r m so ft h em e t h o d f o rm i n i m u m w e i g h tn o d ec o v e rp r o b l e mo nb i p a r t i t eg r a p ha n dt h ea l g o r i t h mo fs o l v i n g i n t r e ep r o b l e mu n d e rt h eb o t t l e n e c k t y p eh a m m i n gd i s t a n c e ：w ea r eg i v e nac o n n e c t e d u n d i r e c t e dn e t w o r kg ，e a c he d g eh a sam o d i f i c a t i o nc o s ta n dan o n n e g a t i v ew e i g h t l e tt ob eas p a n n i n gt r e eo fg w ea r ea s k e dt om o d i f yt h ee d g ew e i g h t ss u c ht h a t t oi st h em i n i m u mw e i g h ts p a n n i n gt r e ea n dt h em a x i m u me d g em o d i f i c a t i o nc o s to f m o d i f i e de d g e si sm i n i m i z e du n d e rt h eh a m m i n gd i s t a n c e w ea r ef u r t h e rr e q u i r e dt h a t t h et o t a lm o d i f i c a t i o nc o s to fm o d i f i e de d g e sc a nn o te x c e e dt h eg i v e nu p p e rb o u n d w ec o n s i d e rt h r e em o d e l s ：u n b o u n d e dc a s e ，s t a n d a r dc a s ea n dc o n s t r a i n e dc a s e i n t e r m so ft h em e t h o df o rn o d ec o v e rp r o b l e mo nb i p a r t i t eg r a p ha n db i s e c t i o nm e t h o d ， w es h o wt h a tt h et h r e ep r o b l e m sc a nb es o l v e db ys t r o n g l yp o l y n o m i a lt i m ea l g o r i t h m s i nc h a p t e r4 ，w ef i r s tc o n s i d e rt h ef o l l o w i n gc e n t e rl o c a t i o ni m p r o v e m e n tp r o b l e m u n d e rt h es u m t y p eh a m m i n gd i s t a n c e ：l e tgb eag i v e nc o n n e c t e du n d i r e c t e dn e t w o r k ，w ea r ea s k e dt oi m p r o v et h en e t w o r ks u c ht h a tt h ed i s t a n c e sb e t w e e nt h ev e r t e x sa n do t h e rv e r t i c e so ft h en e t w o r kc a n n o te x c e e dt h eg i v e nu p p e rb o u n d sa n dt h et o t a l m o d i f i c a t i o nc o s to fm o d i f i e de d g e si sm i n i m i z e du n d e rt h eh a m m i n gd i s t a n c e f o rt h e p r o b l e m ，w es h o wt h a ta c h i e v i n ga na p p r o x i m a t i o na l g o r i t h mw i t haw o r s t c a s er a t i o o ( 1 0 9i y l ) i sn p - h a r db yu s i n gt h el r e d u c t i o nf r o ma ni n s t a n c eo fs e t c o v e rp r o b l e m t oa ni n s t a n c eo ft h ep r o b l e m w et h e nc o n s i d e rt h ef o l l o w i n gc e n t e rl o c a t i o ni m p r o v e - m e n tp r o b l e mu n d e rt h eb o t t l e n e c k t y p eh a m m i n gd i s t a n c e ：w ea r ea s k e dt oi m p r o v e t h en e t w o r ks u c ht h a tt h ed i s t a n c e sb e t w e e nsa n do t h e rv e r t i c e so f t h en e t w o r kc a n n o t e x c e e dt h eg i v e nu p p e rb o u n d sa n dt h em a x i m u me d g em o d i f i c a t i o nc o s to fm o d i f i e d e d g e si sm i n i m i z e d f o rt h i sp r o b l e m ，w ep r e s e n tas t r o n g l yp o l y n o m i a lt i m ea l g o r i t h m i nc h a p t e r5 ，w ec o n s i d e rt h ef o l l o w i n gs h o r t e s tp a t hi m p r o v e m e n tp r o b l e mu n d e r h a m m i n gd i s t a n c e ：l e tgb eag i v e nc o n n e c t e du n d i r e c t e dn e t w o r k ，w ea r ea s k e dt o i m p r o v et h en e t w o r ks u c h t h a tt h ed i s t a n c e sb e t w e e nt h ev e r t e x8 i a n dv e r t e xt io f t h en e t w o r kc a n n o te x c e e dt h eg i v e nu p p e rb o u n d sb i ( i = 1 ，2 ，r ) a n dt h et o t a l m o d i f i c a t i o nc o s to fm o d i f i e de d g e si sm i n i m i z e du n d e rt h eh a m m i n gd i s t a n c e f o rt h e p r o b l e m w es h o wt h a ti t i ss t r o n g l ynp h a r db yu s i n gt h er e d u c t i o nf r o ma ni n s t a n c e d o c t o r a ld i s s e r t a t i o no fz h e j i a n gu n i v e r s i t y1 x o f3 - s a tp r o b l e mt oa ni n s t a n c eo ft h ep r o b l e m f o ras p e c i a lc a s eo ft h ep r o b l e m ， n a m e l y ，t h es h o r t e s tp a t hi m p r o v e m e n tp r o b l e mu n d e rh a m m i n gd i s t a n c eo i lc h a i n n e t w o r kw i t has i n g l es o u r c ea n das i n g l et e r m i n a l ，w es h o wt h a ti t i sn p - h a r db yu s i n g t h er e d u c t i o nf r o ma ni n s t a n c eo fk n a p s a c kp r o b l e mt oa ni n s t a n c eo ft h ep r o b l e m a n dp r e s e n tap s e u d o - p o l y n o m i a lt i m ea l g o r i t h mb a s e do nad y n a m i cp r o g r a m m i n g m e t h o d i nc h a p t e r6 ，w ec o n s i d e rt h ef o l l o w i n gm u l t i c o m m o d i t yp r o d u c t i o na n dd i s t r i b u t i o np r o b l e m ：t h e r ea r es e v e r a lc u s t o m e r s ，t h e yd e m a n ds o m ed i f f e r e n tp r o d u c t sw h i c h c a nb ep r o v i d e db ye i t h e rp l a n t so rp r o d u c ts u p p l i e sv i as o m ed c s i fap r o d u c ti s p r o v i d e db yap l a n t ，t h e ni ta n ds o m eo t h e rp r o d u c t sm u s tb ep r o d u c e di nt h ep l a n t b yu s i n gt h er a wm a t e r i a ls u p p l i e db yr a wm a t e r i a ls u p p l i e r s o n ec u s t o m e ri ss e r v e d e x c l u s i v e l yb yo n ed c t h e nt h ep r o b l e mi st od e t e r m i n eh o wt oa r r a n g ep l a n t sp r o d u c t i o n ，w h i c hd cs i t e st ob eu s e dt os e r v ew h i c hc u s t o m e r s ，a n dw h a tt h ep a t t e r no f t r a n s p o r t a t i o nf l o w si sf o rt h er a wm a t e r i a la n da l lp r o d u c t ss ot h a tt h et o t a lc o s t sa r e a sl o wa sp o s s i b l e w ef o r m u l a t et h ep r o b l e ma sam i x e di n t e g e rl i n e a rp r o g r a m m i n g p r o b l e ma n ds o l v et h ep r o b l e mb yu s i n gt h eb e n d e r sd e c o m p o s i t i o nm e t h o d w ea l s o c o n s i d e rag e n e r a l i z e dm u l t i c o m m o d i t yp r o d u c t i o na n dd i s t r i b u t i o np r o b l e m i nc h a p t e r7 ，w ec o n s i d e rt h ef o l l o w i n gm i n i m u md i s t r i b u t i o nc o s tf l o wp r o b l e m t h e r ea r es e v e r a lc u s t o m e ra n do n l yo n ep r o d u c ts u p p l i e r ，t h e r ei saf i x e dd e m a n d f o rt h ep r o d u c ti ne a c hc u s t o m e r t h ep r o d u c tc a nb ep r o v i d e db ye i t h e rd i s t r i b u t i o n p l a n t so rp r o d u c ts u p p l i e rv i as o m et r a d e s m e n ad i s t r i b u t i o np l a n tp r o v i d e st h e p r o d u c tf o re a c ht r a d e s m a no rc u s t o m e ra c c o r d in gt os p e c i a lr u l e t h e nt h ep r o b l e m i st od e t e r m i n eh o wt oa r r a n g ep r o d u c tb u y i n ga n dd i s t r i b u t i o ns u c h t h a tt h et o t a l c o s t s ( t r a n s i t i n g ，i n v e n t o r yc o s t s ) a r ea sl o wa sp o s s i b l e w ed i s c u s st h ep r o p e r t i e so f t h eb a s i cf e a s i b l eg r a p ho f t h ep r o b l e ma n dg i v ea na l g o r i t h mt os o l v et h ep r i m a lb a s i c f e a s i b l es o h l t i o no ft h em i n i m u md i s t r i b u t i o nc o s tf l o wp r o b l e m b yu s i n gt h en e t w o r k s i m p l e xm e t h o d ：w es o l v et h em i n i m u md i s t r i b u t i o nc o s tf l o wp r o b l e m w ea l s og e t , a n a l g o r i t h mt og i v eab a s i cf e a s i b l es o l u t i o no ft h ep r o b l e mo fa u g m e n t e dn e t w o r k f i n a l l y ，w ep r e s e n tas u m m a r yo fo u rr e s u l t s ，a n dd i s c u s ss o m ei n t e r e s t i n gp r o b l e m s i nt h e s ea r e a s xd o c t o r a ld i s s e r t a t i o no fz h e j i a n gu n i v e r s i t y k e y w o r d s ：i n v e r s eo p t i m i z a t i o np r o b l e m ；n e t w o r ki m p r o v e m e n tp r o b l e m ；h a m m i n gd i s t a n c e ；c o m p u t a t i o n a c o m p l e x i t y ；m u l t i c o m m o d i t yp r o d u c t i o na n dd i s t r i b u t i o n ；m i n i m u md i s t r i b u t i o nc o s tf l o w d o c t o r a ld i s s e r t a t i o no fz h e j i a n gu n i v e r s i t y a c k n o w l e d g e m e n t s f i r s to fa l l ，1w o u l dl i k et o e x p r e s sm ys i n c e r et h a n k st om ys u p e r v i s o r s ，p r o f y a oe n y u ，p r o f h ey o n ga n dp r o f q il i q u n w i t h o u tt h e i rp a t i e n tg u i d a n c e ， i n v a l u a b l et i m es p e n t ，d e t a i l e dd i s c u s s i o n sa n da d v i c e ，ic o u l dn o th a v ef i n i s h e dm y s t u d i e sa n dt h i sd i s s e r t a t i o n p r o f y a oa n dp r o f q ig a v em et h eo p p o r t u n i t yt os t u d y i np o l y t e c h n i cu n i v e r s i t yo fh o n gk o n g p r o f h er e c o m m e n d e dm et os t u d yi nc i t y u n i v e r s i t yo fh o n gk o n g io w et h e mm yd e e p e s tg r a t i t u d e s p e c i a lt h a n k sa r eg i v e nt op r o f j a s o nz h a n gj i a n z h o n g h i sa d v i c e ，i d e a sa n d g u i d a n c eh a v eb e e ni n v a l u a b l et om e h es p e n tal o to fi n v a l u a b l et i m ei nd i s c u s s i n g a n dr e v i s i n go u rp a p e r s ，a n dh ea l s op r o v i d e dm et h eo p p o r t u n i t yt os t u d yi n c i t y u n i v e r s i t yo fh o n gk o n g 1w o u l dl i k et ot h a n km ya l lc l a s s m a t e si no u rg r o u pf o rg i v i n gm em a n yu s e f u ls u g - g e s t i o n s e s p e c i a l l y ，ia mg r a t e f u lt op r o f y a n gq i f a n ，p r o f z h a n gg u o c h u a n ，p r o f t a nz h i y i ，p r o f l ux i n j i a n g ，p r o f z h uj i a n x i na n dm s h a nd o n gi nd e p a r t m e n to f m a t h e m a t i c s ，z h e j i a n gu n i v e r s i t yf o rt h e i rh e l pa n de n c o u r a g e m e n t m yf r i e n d sh e r e i nz h a n gu n i v e r s i t y ，n a m e l yd r h a ng u a n g g u o ，d r x ug a n g ，d r x i n gh u a n p i n g ， p r o f c h e np e i x i n ga n dd r x ux i a n g h u a ，p l a yi m p o r t a n tr o l e si nm a k i n gm yl i f em o r e e n j o y a b l e 1w a n tt ot h a n kt h es t a f fa n df a c u l t yo ft h ed e p a r t m e n to fs c i e n c ea n dp h y s i c sa t h o h a iu n i v e r s i t y ，c h a n g z h o uc a m p u sf o rp r o v i d i n gm es u c han i c ea c a d e m i ce n v i r o n m e n t a l s o ，1w i s ht ot h a n km yc o l l e a g u e si nh o h a iu n i v e r s i t y ，c h a n g z h o uc a m p u s ， p r o f z h o uj i a n f a n g ，z h o uz i q i a n g ，c h e nz h e n g m i n g ，y a n gq i w e na n dx u ey u n c a n f o rg i v i n gm em u c hh e l pi nm yl i f ea n ds t u d y m a n yt h a n k st op r o f f a n gs h u c h e r n g ，p r o f h u a n gx u e x i a n g ，p r o f l i uy a n q u n ， p r o f l i n gc h e n ，p r o f l is h e n g j i e ，p r o f n iq i n g ，p r o f q ih o u d u o ，p r o f s u n w e n y u ，p r o f w a n gy i j u ，p r o f x i un a i h u a ，p r o f y a n g l f e i ，p r o f y a n gx i n m i n g ， p r o f y i nh o n g x i a ，p r o f z h a n gy u z h o n g ，d r y u a nx i a o m i n g ，d r g u a nx i u c u i ， d r w a n gq i nf o rt h e i rw a r m h e a r t e dh e l pd u r i n gm yv i s i t i n gt oc i t yu n i v e r s i t ya n d p o l y t e c h n i cu n i v e r s i t yo fh o n gk o n g 1 vd o c t o r a ld i s s e r t a t i o no fz h e j i a n gu n i v e r s i t y f i n a l l y ，1w o u l dl i k et oe x p r e s sm yt h a n k st om yw i f e n i uc h u n l ia n dm ys o n z h a n gp e n x i a n g ，t h e yh a v eb e e nt h eb e s tp a r to fm yl i f e ，a n dw o r d s c a n n o te x p r e s sm y a p p r e c i a t i o nf o rt h es u p p o r ta n de n c o u r a g e m e n tt h e yh a v eg i v e nm ea n dt h es a c r if i c e s t h e yh a v em a d eo nm yb e h a l f 1a l s og i v em yt h a n k st om yp a r e n t sa n dm ym o t h e 卜 i n l a wf o rg i v i n gm ec o n s t a n te n c o u r a g e m e n t t h i sd i s s e r t a t i o ni sd e d i c a t e dt oa l lp e r s o n sw h os u p p o r ta n dh e l pm e j a n u a r y2 0 0 5 f i n i s h e da tz h e j i a n gu n i v e r s i t y d o c t o r a ld i s s e r t a t i o no fz h e j i a n gu n i v e r s i t y c h a p t e r1 i n t r o d u c t i o n 1 1 i n v e r s eo p t i m i z a t i o np r o b l e m s i n t h i ss e c t i o n ，w ef i r s ti n t r o d u c et h ei n v e r s eo p t i m i z a t i o np r o b l e m sa n dg i v es o m e a p p l i c a t i o ne x a m p l e so ft h ep r o b l e m s ，t h e nw eg i v eas h o r ts u r v e yo fi n v e r s eo p t i m i z a - t i o np r o b l e m sa n ds o m em e t h o d su s e di ns t u d y i n gt h ep r o b l e m s 1 1 1 i n v e r s eo p t i m i z a t i o np r o b l e m sa n dt h e i ra p p l i c a t i o n s w h e ns o l v i n ga ( p o s s i b l yc o m b i n a t o r i a l ) o p t i m i z a t i o np r o b l e m ，w eu s u a l l ya s s u m e t h a tt h ep a r a m e t e r ss u c ha sc o s t s ，c a p a c i t i e s ，e t c ，a r ek n o w na n dt h a tw ea r ei n t e r e s t e d i