394:
The first property states that the original problem's feasible domain is a subset of the relaxed problem's feasible domain. The second property states that the original problem's objective-function is greater than or equal to the relaxed problem's objective-function.
271:
992:
Murty, Katta G. (1983). "16 Iterative methods for linear inequalities and linear programs (especially 16.2 Relaxation methods, and 16.4 Sparsity-preserving iterative SOR algorithms for linear programming)".
173:
558:
58:
of a complicated problem in combinatorial optimization penalizes violations of some constraints, allowing an easier relaxed problem to be solved. Relaxation techniques complement or supplement
474:
362:
310:
708:
598:
679:
62:
algorithms of combinatorial optimization; linear programming and
Lagrangian relaxations are used to obtain bounds in branch-and-bound algorithms for integer programming.
388:
625:
428:
710:, the following holds: If an optimal solution for the relaxed problem is feasible for the original problem, then it is optimal for the original problem.
43:
of a difficult problem by a nearby problem that is easier to solve. A solution of the relaxed problem provides information about the original problem.
184:
1095:
1076:
1032:
1002:
959:
757:
Relaxation methods for finding feasible solutions to linear inequality systems arise in linear programming and in
Lagrangian relaxation.
1114:
1119:
913:
82:
107:
479:
719:
78:
74:
28:
1027:. Handbooks in Operations Research and Management Science. Vol. 1. Amsterdam: North-Holland Publishing Co.
433:
890:
Geoffrion, A. M. (1971). "Duality in
Nonlinear Programming: A Simplified Applications-Oriented Development".
729:
1124:
734:
724:
55:
738:
316:
282:
1058:
684:
563:
1020:
633:
51:
17:
930:
899:
86:
47:
36:
1091:
1072:
1049:
1028:
998:
955:
70:
922:
855:
851:
367:
66:
59:
54:
problem removes the integrality constraint and so allows non-integer rational solutions. A
1042:
1012:
984:
969:
942:
603:
406:
89:. However, iterative methods of relaxation have been used to solve Lagrangian relaxations.
1038:
1008:
980:
965:
938:
911:
Goffin, J.-L. (1980). "The relaxation method for solving systems of linear inequalities".
1108:
40:
883:
Semicontinuity, Relaxation and
Integral Representation in the Calculus of Variations
1055:
George L. Nemhauser and
Laurence A. Wolsey, Integer programming (pp. 447–527);
839:
266:{\displaystyle z_{R}=\min\{c_{R}(x):x\in X_{R}\subseteq \mathbf {R} ^{n}\}}
926:
954:. Chichester: A Wiley-Interscience Publication. John Wiley & Sons.
934:
903:
77:(SOR); iterative methods of relaxation are used in solving problems in
65:
The modeling strategy of relaxation should not be confused with
168:{\displaystyle z=\min\{c(x):x\in X\subseteq \mathbf {R} ^{n}\}}
1088:
687:
636:
606:
566:
553:{\displaystyle z=c(x^{*})\geq c_{R}(x^{*})\geq z_{R}}
482:
436:
430:
is an optimal solution of the original problem, then
409:
370:
319:
285:
187:
110:
1061:, Nondifferentiable optimization (pp. 529–572);
787:
785:
1023:; Rinnooy Kan, A. H. G.; Todd, M. J., eds. (1989).
885:. Pitman Res. Notes in Math. 207. Harlow: Longmann.
867:
L. T. Gubin, Boris T. Polyak, and E. V. Raik (1969)
977:Programmation mathématique: Théorie et algorithmes
702:
673:
619:
592:
552:
468:
422:
382:
356:
304:
265:
167:
201:
117:
952:Mathematical programming: Theory and algorithms
1052:, Polyhedral combinatorics (pp. 371–446);
8:
630:If in addition to the previous assumptions,
260:
204:
178:is another minimization problem of the form
162:
120:
777:
686:
641:
635:
611:
605:
584:
571:
565:
544:
528:
515:
499:
481:
469:{\displaystyle x^{*}\in X\subseteq X_{R}}
460:
441:
435:
414:
408:
369:
324:
318:
290:
284:
254:
249:
239:
211:
192:
186:
156:
151:
109:
773:
771:
769:
765:
750:
827:
815:
791:
803:
7:
1069:Optimization in operations research
997:. New York: John Wiley & Sons.
914:Mathematics of Operations Research
688:
25:
18:Relaxation technique (mathematics)
357:{\displaystyle c_{R}(x)\leq c(x)}
974:Translated by Steven Vajda from
305:{\displaystyle X_{R}\supseteq X}
250:
152:
703:{\displaystyle \forall x\in X}
668:
662:
653:
647:
593:{\displaystyle x^{*}\in X_{R}}
534:
521:
505:
492:
351:
345:
336:
330:
223:
217:
132:
126:
1:
1090:. Berlin: Walter de Gruyter.
830:, Section 4.3.7, pp. 120–123.
720:Linear programming relaxation
674:{\displaystyle c_{R}(x)=c(x)}
101:of the minimization problem
600:provides an upper bound on
1141:
1115:Relaxation (approximation)
1067:Rardin, Ronald L. (1998).
714:Some relaxation techniques
276:with these two properties
75:successive over-relaxation
1120:Mathematical optimization
29:mathematical optimization
730:Semidefinite relaxation
979:. Paris: Dunod. 1983.
704:
675:
621:
594:
554:
470:
424:
384:
383:{\displaystyle x\in X}
358:
306:
267:
169:
79:differential equations
39:. A relaxation is an
1086:RoubĂÄŤek, T. (1997).
881:Buttazzo, G. (1989).
725:Lagrangian relaxation
705:
676:
622:
620:{\displaystyle z_{R}}
595:
555:
471:
425:
423:{\displaystyle x^{*}}
385:
359:
307:
268:
170:
56:Lagrangian relaxation
927:10.1287/moor.5.3.388
735:Surrogate relaxation
685:
634:
604:
564:
480:
434:
407:
368:
317:
283:
185:
108:
83:linear least-squares
31:and related fields,
950:Minoux, M. (1986).
806:, pp. 453–464.
52:integer programming
995:Linear programming
700:
671:
617:
590:
550:
466:
420:
380:
354:
302:
263:
165:
87:linear programming
48:linear programming
1097:978-3-11-014542-7
1078:978-0-02-398415-0
1071:. Prentice Hall.
1059:Claude Lemaréchal
1050:W. R. Pulleyblank
1034:978-0-444-87284-5
1004:978-0-471-09725-9
961:978-0-471-90170-9
67:iterative methods
50:relaxation of an
37:modeling strategy
16:(Redirected from
1132:
1101:
1082:
1046:
1021:Nemhauser, G. L.
1016:
988:
973:
946:
907:
886:
868:
865:
859:
856:Isaac Schoenberg
852:Theodore Motzkin
849:
843:
837:
831:
825:
819:
813:
807:
801:
795:
789:
780:
778:Geoffrion (1971)
775:
758:
755:
709:
707:
706:
701:
680:
678:
677:
672:
646:
645:
626:
624:
623:
618:
616:
615:
599:
597:
596:
591:
589:
588:
576:
575:
559:
557:
556:
551:
549:
548:
533:
532:
520:
519:
504:
503:
475:
473:
472:
467:
465:
464:
446:
445:
429:
427:
426:
421:
419:
418:
389:
387:
386:
381:
363:
361:
360:
355:
329:
328:
311:
309:
308:
303:
295:
294:
272:
270:
269:
264:
259:
258:
253:
244:
243:
216:
215:
197:
196:
174:
172:
171:
166:
161:
160:
155:
60:branch and bound
21:
1140:
1139:
1135:
1134:
1133:
1131:
1130:
1129:
1105:
1104:
1098:
1085:
1079:
1066:
1035:
1019:
1005:
991:
975:
962:
949:
910:
889:
880:
877:
872:
871:
866:
862:
850:
846:
838:
834:
826:
822:
814:
810:
802:
798:
790:
783:
776:
767:
762:
761:
756:
752:
747:
716:
683:
682:
637:
632:
631:
607:
602:
601:
580:
567:
562:
561:
540:
524:
511:
495:
478:
477:
456:
437:
432:
431:
410:
405:
404:
401:
366:
365:
320:
315:
314:
286:
281:
280:
248:
235:
207:
188:
183:
182:
150:
106:
105:
95:
46:For example, a
23:
22:
15:
12:
11:
5:
1138:
1136:
1128:
1127:
1125:Approximations
1122:
1117:
1107:
1106:
1103:
1102:
1096:
1083:
1077:
1064:
1063:
1062:
1056:
1053:
1033:
1017:
1003:
989:
960:
947:
921:(3): 388–414.
908:
887:
876:
873:
870:
869:
860:
844:
832:
820:
808:
796:
781:
764:
763:
760:
759:
749:
748:
746:
743:
742:
741:
732:
727:
722:
715:
712:
699:
696:
693:
690:
670:
667:
664:
661:
658:
655:
652:
649:
644:
640:
614:
610:
587:
583:
579:
574:
570:
547:
543:
539:
536:
531:
527:
523:
518:
514:
510:
507:
502:
498:
494:
491:
488:
485:
463:
459:
455:
452:
449:
444:
440:
417:
413:
400:
397:
392:
391:
379:
376:
373:
353:
350:
347:
344:
341:
338:
335:
332:
327:
323:
312:
301:
298:
293:
289:
274:
273:
262:
257:
252:
247:
242:
238:
234:
231:
228:
225:
222:
219:
214:
210:
206:
203:
200:
195:
191:
176:
175:
164:
159:
154:
149:
146:
143:
140:
137:
134:
131:
128:
125:
122:
119:
116:
113:
94:
91:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1137:
1126:
1123:
1121:
1118:
1116:
1113:
1112:
1110:
1099:
1093:
1089:
1084:
1080:
1074:
1070:
1065:
1060:
1057:
1054:
1051:
1048:
1047:
1044:
1040:
1036:
1030:
1026:
1022:
1018:
1014:
1010:
1006:
1000:
996:
990:
986:
982:
978:
971:
967:
963:
957:
953:
948:
944:
940:
936:
932:
928:
924:
920:
916:
915:
909:
905:
901:
897:
893:
888:
884:
879:
878:
874:
864:
861:
857:
853:
848:
845:
841:
836:
833:
829:
828:Minoux (1986)
824:
821:
817:
816:Minoux (1986)
812:
809:
805:
800:
797:
793:
792:Goffin (1980)
788:
786:
782:
779:
774:
772:
770:
766:
754:
751:
744:
740:
736:
733:
731:
728:
726:
723:
721:
718:
717:
713:
711:
697:
694:
691:
665:
659:
656:
650:
642:
638:
628:
612:
608:
585:
581:
577:
572:
568:
560:. Therefore,
545:
541:
537:
529:
525:
516:
512:
508:
500:
496:
489:
486:
483:
461:
457:
453:
450:
447:
442:
438:
415:
411:
398:
396:
377:
374:
371:
348:
342:
339:
333:
325:
321:
313:
299:
296:
291:
287:
279:
278:
277:
255:
245:
240:
236:
232:
229:
226:
220:
212:
208:
198:
193:
189:
181:
180:
179:
157:
147:
144:
141:
138:
135:
129:
123:
114:
111:
104:
103:
102:
100:
92:
90:
88:
84:
80:
76:
72:
68:
63:
61:
57:
53:
49:
44:
42:
41:approximation
38:
34:
30:
19:
1087:
1068:
1025:Optimization
1024:
994:
976:
951:
918:
912:
895:
891:
882:
863:
847:
840:Shmuel Agmon
835:
823:
811:
804:Murty (1983)
799:
753:
629:
402:
393:
275:
177:
98:
96:
64:
45:
32:
26:
898:(1): 1–37.
892:SIAM Review
73:, such as
1109:Categories
875:References
399:Properties
99:relaxation
93:Definition
71:relaxation
33:relaxation
695:∈
689:∀
578:∈
573:∗
538:≥
530:∗
509:≥
501:∗
454:⊆
448:∈
443:∗
416:∗
375:∈
340:≤
297:⊇
246:⊆
233:∈
148:⊆
142:∈
364:for all
1043:1105099
1013:0720547
985:2571910
970:0868279
943:0594854
935:3689446
904:2028848
739:duality
1094:
1075:
1041:
1031:
1011:
1001:
983:
968:
958:
941:
933:
902:
858:(1954)
842:(1954)
85:, and
931:JSTOR
900:JSTOR
745:Notes
35:is a
1092:ISBN
1073:ISBN
1029:ISBN
999:ISBN
956:ISBN
854:and
737:and
476:and
923:doi
403:If
202:min
118:min
69:of
27:In
1111::
1039:MR
1037:.
1009:MR
1007:.
981:MR
966:MR
964:.
939:MR
937:.
929:.
917:.
896:13
894:.
784:^
768:^
681:,
627:.
97:A
81:,
1100:.
1081:.
1045:.
1015:.
987:.
972:.
945:.
925::
919:5
906:.
818:.
794:.
698:X
692:x
669:)
666:x
663:(
660:c
657:=
654:)
651:x
648:(
643:R
639:c
613:R
609:z
586:R
582:X
569:x
546:R
542:z
535:)
526:x
522:(
517:R
513:c
506:)
497:x
493:(
490:c
487:=
484:z
462:R
458:X
451:X
439:x
412:x
390:.
378:X
372:x
352:)
349:x
346:(
343:c
337:)
334:x
331:(
326:R
322:c
300:X
292:R
288:X
261:}
256:n
251:R
241:R
237:X
230:x
227::
224:)
221:x
218:(
213:R
209:c
205:{
199:=
194:R
190:z
163:}
158:n
153:R
145:X
139:x
136::
133:)
130:x
127:(
124:c
121:{
115:=
112:z
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.