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