Integer programming (original) (raw)
برمجة الأعداد الصحيحة هي عبارة عن مسألة أمثَلة رياضية أو برنامج لدراسة الجدوى، الذي فيه بعض أو كل المتغيرات لابد ان تكون أعداد صحيحة. في كثير من الحالات هذا المصطلح يُعبِر عن البرمجة الخطية الصحيحة، التي فيها دالة الهدف والقيود تكون خطية.البرمجة الصحيحة هي مسألة غير حتمية متعددة الحدود مسائل NP صعبة.حالة خاصة: البرمجة الخطية الصحيحة تكون فيها المتغيرات المجهولة رقمية (0-1) هي مسألة حاسوبية وتُعتَبر من المسائل الحتمية متعددة الحدود.
| Property | Value |
|---|---|
| dbo:abstract | برمجة الأعداد الصحيحة هي عبارة عن مسألة أمثَلة رياضية أو برنامج لدراسة الجدوى، الذي فيه بعض أو كل المتغيرات لابد ان تكون أعداد صحيحة. في كثير من الحالات هذا المصطلح يُعبِر عن البرمجة الخطية الصحيحة، التي فيها دالة الهدف والقيود تكون خطية.البرمجة الصحيحة هي مسألة غير حتمية متعددة الحدود مسائل NP صعبة.حالة خاصة: البرمجة الخطية الصحيحة تكون فيها المتغيرات المجهولة رقمية (0-1) هي مسألة حاسوبية وتُعتَبر من المسائل الحتمية متعددة الحدود. (ar) La programació lineal entera serveix per resoldre els problemes de programació lineal en què les variables han de prendre valor enters. Quan representem un problema de programació lineal ens podem trobar que només tenen sentit aquelles solucions de la regió factible, que les seves variables són nombres enters. Llavors estem davant d'un problema de programació lineal entera. Un problema de programació lineal entera es formula de la mateixa manera que un problema de programació lineal convencional, però amb la diferència que el resultat d'aquest es trobarà dins d'una regió factible, en aquesta trobarem diversos punts, però només són vàlids els que tenen unes coordenades enteres. Aquests problemes són a vegades fàcils de resoldre i a vegades impossibles, perquè no trobem cap punt dins de la regió factible que tingui coordenades enteres. Per resoldre aquests problemes s'utilitza el mètode gràfic. Aquest consisteix a representar la regió factible, dibuixar la funció objectiu i buscar en quin punt assoleix el màxim o el mínim. Una vegada buscat el màxim o el mínim, si aquests punts no tenen coordenades enteres s'ha de buscar quins punts amb coordenades enteres són pròxims aquests i en quins d'aquests s'obté el màxim o el mínim. (ca) Celočíselné programování je odvětví optimalizace, první úloha celočíselného programování byla řešena v roce 1958. (cs) Die ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Der Unterschied liegt darin, dass in der ganzzahligen Optimierung einige oder alle Variablen nur ganzzahlige Werte annehmen dürfen und nicht beliebige reelle Werte wie in der linearen Optimierung. Die ganzzahlige Optimierung lässt sich geometrisch als Optimierung über einem konvexen Polyeder (einem höherdimensionalen Vieleck) auffassen und ist damit ein Spezialfall der konvexen Optimierung. Im Unterschied zur linearen Programmierung ist allerdings das zugrundeliegende Polyeder meist nicht genau bekannt, was das Problem aus komplexitätstheoretischer Sicht NP-schwer macht. Da mindestens eine Variable diskret, also nicht kontinuierlich ist, ist auch der Begriff diskrete Optimierung gebräuchlich. Eine weitere häufige Bezeichnung ist ganzzahlige (lineare) Programmierung (von engl. integer (linear) programming), wobei der Begriff Programm im Sinne von Planung zu verstehen ist und nicht im Sinne eines Computerprogramms. Er wurde schon in den 1940er Jahren von George Dantzig geprägt, bevor Computer zur Lösung von Optimierungsproblemen eingesetzt wurden. Noch stärker als die lineare hat sich die ganzzahlige Optimierung seit ihren Anfängen in den 1950er Jahren zu einem Modellierungs- und Optimierungswerkzeug für viele praktische Probleme entwickelt, für die keine speziellen Algorithmen bekannt sind. Durch bedeutende Fortschritte in der Entwicklung der Lösungsverfahren in den 1980er und 1990er Jahren hat die ganzzahlige Optimierung heute viele Anwendungen, beispielsweise in der Produktion, in der Planung von Telekommunikations- und Nahverkehrsnetzen und in der Tourenplanung. Zur Lösung ganzzahliger Optimierungsprobleme gibt es einerseits exakte Lösungsverfahren wie beispielsweise Branch-and-Bound und Schnittebenenverfahren, die auf der Lösung vieler ähnlicher linearer Programme basieren, und andererseits eine Vielzahl von Heuristiken. Trotzdem ist die Lösung ganzzahliger linearer Programme in der Praxis immer noch eine schwere Aufgabe, die je nach Größe und Struktur des zu lösenden Problems eine geschickte Modellierung und mehr oder weniger speziell entwickelte oder angepasste Algorithmen erfordert. Oft werden daher mehrere Lösungsverfahren kombiniert. (de) Un problema de programación en enteros es un programa de optimización o factibilidad matemática en el cual algunas o todas las variables tienen que ser enteras. En muchos escenarios el término se refiere a programación lineal en enteros (PLE), en el cual la función objetivo y las restricciones (aparte de las restricciones enteras) son lineales. La programación en enteros es NP-duro. Un caso especial, la programación lineal en enteros 0-1, en el cual las incógnitas son binarias, es uno de los 21 problemas NP-completo de Karp. (es) An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems. If some decision variables are not discrete, the problem is known as a mixed-integer programming problem. (en) L'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières. La contrainte d'intégralité sur les variables, qui différencie l'OLNE de l'optimisation linéaire classique est nécessaire pour modéliser certains problèmes, en particulier des problèmes algorithmiques. Mais cette contrainte supplémentaire rend le problème plus complexe et demande des techniques particulières. (fr) 整数計画問題（せいすうけいかくもんだい）は、線型計画問題において、解ベクトルxの各要素を整数に限定した問題をいう。これはNP困難な問題に該当する。線型計画問題には多項式時間アルゴリズムが存在するのに対し、整数計画問題には存在しない。 解ベクトルxの各要素を0または1のみに限定したものを、特に0-1整数計画問題という。 (ja) 수학에서 정수 계획법(整數計劃法, 영어: Integer programming 인티저 프로그래밍[*])은 최적화 문제의 일종으로 주어진 정수 조건을 만족시키면서 목적 함수를 최적화하는 문제이다. (ko) Een geheeltallig programmering probleem is een wiskundig optimalisatie- of haalbaarheidsprogramma, waarin sommige of alle van de variabelen zich beperken tot de gehele getallen. In veel settings verwijst de term naar geheeltallige lineaire programmering, dat ook bekendstaat als gemengde geheeltallige programmering. Geheeltallige programmering is NP-moeilijk. Een speciaal geval is de 0-1 geheeltallige lineaire programmering, waarbij de onbekenden binair zijn, is een van de 21 NP-compleet problemen van Karp. (nl) Um Problema de Programação Inteira é um modelo de programação linear no qual algumas ou todas as variáveis do problema pertencem ao conjunto dos números inteiros. Quando todas as variáveis são inteira o modelo é denominado programação inteira pura; caso contrário, é denominado programação inteira mista. A solução de um Problema Linear Inteiro (PLI) aparenta ser fácil, no entanto produzir soluções para programas inteiros é um problema NP-difícil. (pt) Задача целочисленного программирования — это задача математической оптимизации или выполнимости, в которой некоторые или все переменные должны быть целыми числами. Часто термин адресуется к целочисленному линейному программированию (ЦЛП), в котором целевая функция и ограничения (за исключением требования целочисленности) линейны. Целочисленное программирование является NP-трудной задачей. Специальный случай, 0-1 целочисленное линейное программирование, в которой переменные принимают значения 0 или 1, является одной из 21 NP-полных задач Карпа. (ru) Цілочисельне програмування — різновид математичного програмування, що припускає, що шукані значення повинні бути цілими числами. Розділ математичного програмування, у якому вивчаються методи знаходження екстремумів функцій у просторі параметрів, де всі або деякі змінні є цілими числами. Найпростіший метод розв'язання задачі цілочисельного програмування — зведення її до задачі лінійного програмування з перевіркою результату на цілочисельність. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/IP_polytope_with_LP_relaxation.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.iasi.cnr.it/aussois https://mat.tepper.cmu.edu/orclass/integer/integer.html http://www.mathopt.org/%3Fnav=ipco |
| dbo:wikiPageID | 411215 (xsd:integer) |
| dbo:wikiPageLength | 26246 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124847989 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Production_planning dbr:Branch_and_bound dbr:Hopfield_network dbr:Peter_van_Emde_Boas dbr:Cutting-plane_method dbr:Vertex_cover dbc:Combinatorial_optimization dbr:Mathematical_optimization dbr:Geometry_of_numbers dbr:Energy_system dbr:Graph_(discrete_mathematics) dbr:Branch_and_cut dbr:NP-complete dbr:NP-hard dbr:Constrained_least_squares dbr:Constraint_satisfaction_problem dbr:Ant_colony_optimization_algorithms dbr:László_Lovász dbr:Simulated_annealing dbr:Tabu_search dbr:Travelling_salesman_problem dbr:GSM dbr:Karp's_21_NP-complete_problems dbr:Linear_function_(calculus) dbr:Linear_programming dbr:Linear_programming_relaxation dbr:Adjugate_matrix dbr:Hill_climbing dbr:Tree-depth dbr:Hendrik_Lenstra dbr:Herbert_Scarf dbr:Fixed-parameter_tractable dbr:Binary_data dbr:Guidance_system dbr:Integer dbr:Cashflow_matching dbr:Simplex_algorithm dbr:Unimodular_matrix dbr:Unmanned_aerial_vehicle dbr:Strongly_polynomial dbr:File:IP_polytope_with_LP_relaxation.svg |
| dbp:wikiPageUsesTemplate | dbt:Anchor dbt:Cite_book dbt:Reflist dbt:Rp dbt:Short_description dbt:Optimization_algorithms |
| dct:isPartOf | http://zbw.eu/stw/mapping/dbpedia/target |
| dct:subject | dbc:Combinatorial_optimization |
| gold:hypernym | dbr:Optimization |
| rdf:type | dbo:Software |
| rdfs:comment | برمجة الأعداد الصحيحة هي عبارة عن مسألة أمثَلة رياضية أو برنامج لدراسة الجدوى، الذي فيه بعض أو كل المتغيرات لابد ان تكون أعداد صحيحة. في كثير من الحالات هذا المصطلح يُعبِر عن البرمجة الخطية الصحيحة، التي فيها دالة الهدف والقيود تكون خطية.البرمجة الصحيحة هي مسألة غير حتمية متعددة الحدود مسائل NP صعبة.حالة خاصة: البرمجة الخطية الصحيحة تكون فيها المتغيرات المجهولة رقمية (0-1) هي مسألة حاسوبية وتُعتَبر من المسائل الحتمية متعددة الحدود. (ar) Celočíselné programování je odvětví optimalizace, první úloha celočíselného programování byla řešena v roce 1958. (cs) Un problema de programación en enteros es un programa de optimización o factibilidad matemática en el cual algunas o todas las variables tienen que ser enteras. En muchos escenarios el término se refiere a programación lineal en enteros (PLE), en el cual la función objetivo y las restricciones (aparte de las restricciones enteras) son lineales. La programación en enteros es NP-duro. Un caso especial, la programación lineal en enteros 0-1, en el cual las incógnitas son binarias, es uno de los 21 problemas NP-completo de Karp. (es) 整数計画問題（せいすうけいかくもんだい）は、線型計画問題において、解ベクトルxの各要素を整数に限定した問題をいう。これはNP困難な問題に該当する。線型計画問題には多項式時間アルゴリズムが存在するのに対し、整数計画問題には存在しない。 解ベクトルxの各要素を0または1のみに限定したものを、特に0-1整数計画問題という。 (ja) 수학에서 정수 계획법(整數計劃法, 영어: Integer programming 인티저 프로그래밍[*])은 최적화 문제의 일종으로 주어진 정수 조건을 만족시키면서 목적 함수를 최적화하는 문제이다. (ko) Een geheeltallig programmering probleem is een wiskundig optimalisatie- of haalbaarheidsprogramma, waarin sommige of alle van de variabelen zich beperken tot de gehele getallen. In veel settings verwijst de term naar geheeltallige lineaire programmering, dat ook bekendstaat als gemengde geheeltallige programmering. Geheeltallige programmering is NP-moeilijk. Een speciaal geval is de 0-1 geheeltallige lineaire programmering, waarbij de onbekenden binair zijn, is een van de 21 NP-compleet problemen van Karp. (nl) Um Problema de Programação Inteira é um modelo de programação linear no qual algumas ou todas as variáveis do problema pertencem ao conjunto dos números inteiros. Quando todas as variáveis são inteira o modelo é denominado programação inteira pura; caso contrário, é denominado programação inteira mista. A solução de um Problema Linear Inteiro (PLI) aparenta ser fácil, no entanto produzir soluções para programas inteiros é um problema NP-difícil. (pt) Задача целочисленного программирования — это задача математической оптимизации или выполнимости, в которой некоторые или все переменные должны быть целыми числами. Часто термин адресуется к целочисленному линейному программированию (ЦЛП), в котором целевая функция и ограничения (за исключением требования целочисленности) линейны. Целочисленное программирование является NP-трудной задачей. Специальный случай, 0-1 целочисленное линейное программирование, в которой переменные принимают значения 0 или 1, является одной из 21 NP-полных задач Карпа. (ru) Цілочисельне програмування — різновид математичного програмування, що припускає, що шукані значення повинні бути цілими числами. Розділ математичного програмування, у якому вивчаються методи знаходження екстремумів функцій у просторі параметрів, де всі або деякі змінні є цілими числами. Найпростіший метод розв'язання задачі цілочисельного програмування — зведення її до задачі лінійного програмування з перевіркою результату на цілочисельність. (uk) La programació lineal entera serveix per resoldre els problemes de programació lineal en què les variables han de prendre valor enters. Quan representem un problema de programació lineal ens podem trobar que només tenen sentit aquelles solucions de la regió factible, que les seves variables són nombres enters. Llavors estem davant d'un problema de programació lineal entera. Per resoldre aquests problemes s'utilitza el mètode gràfic. Aquest consisteix a representar la regió factible, dibuixar la funció objectiu i buscar en quin punt assoleix el màxim o el mínim. (ca) Die ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Der Unterschied liegt darin, dass in der ganzzahligen Optimierung einige oder alle Variablen nur ganzzahlige Werte annehmen dürfen und nicht beliebige reelle Werte wie in der linearen Optimierung. Die ganzzahlige Optimierung lässt sich geometrisch als Optimierung über einem konvexen Polyeder (einem höherdimensionalen Vieleck) auffassen und ist damit ein Spezialfall der konvexen Optimierung. Im Unterschied zur linearen Programmierung ist allerdings das zugrundeliegende Polyeder meist nicht genau bekannt, (de) An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems. (en) L'optimisation linéaire en nombres entiers (OLNE) (ou programmation linéaire en nombres entiers (PLNE) ou integer programming (IP) ou Integer Linear Programming (ILP)) est un domaine des mathématiques et de l'informatique théorique dans lequel on considère des problèmes d'optimisation d'une forme particulière. Ces problèmes sont décrits par une fonction de coût et des contraintes linéaires, et par des variables entières. (fr) |
| rdfs:label | برمجة الأعداد الصحيحة (ar) Programació lineal entera (ca) Celočíselné programování (cs) Ganzzahlige lineare Optimierung (de) Programación en enteros (es) Optimisation linéaire en nombres entiers (fr) Integer programming (en) 整数計画問題 (ja) 정수 계획법 (ko) Geheeltallige programmering (nl) Целочисленное программирование (ru) Programação inteira (pt) Цілочисельне програмування (uk) 整数规划 (zh) |
| owl:sameAs | freebase:Integer programming yago-res:Integer programming wikidata:Integer programming dbpedia-ar:Integer programming dbpedia-ca:Integer programming dbpedia-cs:Integer programming dbpedia-da:Integer programming dbpedia-de:Integer programming dbpedia-es:Integer programming dbpedia-fa:Integer programming dbpedia-fr:Integer programming dbpedia-ja:Integer programming dbpedia-ko:Integer programming dbpedia-nl:Integer programming dbpedia-pt:Integer programming dbpedia-ru:Integer programming dbpedia-sk:Integer programming dbpedia-sr:Integer programming dbpedia-uk:Integer programming dbpedia-vi:Integer programming dbpedia-zh:Integer programming https://global.dbpedia.org/id/4nJUC |
| skos:closeMatch | http://zbw.eu/stw/descriptor/15535-0 |
| prov:wasDerivedFrom | wikipedia-en:Integer_programming?oldid=1124847989&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/IP_polytope_with_LP_relaxation.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Integer_programming |
| is dbo:knownFor of | dbr:Ellis_L._Johnson |
| is dbo:wikiPageRedirects of | dbr:Applications_of_integer_programming dbr:Integer_linear_programming dbr:Algorithms_for_integer_programming dbr:Integer_Programming dbr:Integer_linear_program dbr:INteger_programming dbr:Lenstra's_algorithm dbr:Discrete_linear_optimization dbr:Mixed-integer_programming dbr:Mixed_integer_linear_optimization dbr:Integer_Programming_Problem dbr:Integer_constraint dbr:Integer_linear_optimization dbr:Integer_program |
| is dbo:wikiPageWikiLink of | dbr:Bend_minimization dbr:Rekha_R._Thomas dbr:Bayesian_network dbr:Branch_and_bound dbr:Algorithm dbr:Arc_routing dbr:Relaxation_(approximation) dbr:Cutting-plane_method dbr:Vehicle_routing_problem dbr:Decoding_methods dbr:Integral_polytope dbr:Intersection_number_(graph_theory) dbr:Register_allocation dbr:List_of_optimization_software dbr:Presburger_arithmetic dbr:Condorcet_method dbr:Cramer's_rule dbr:Mathematical_optimization dbr:Mathematics dbr:Generalized_assignment_problem dbr:NEOS_Server dbr:Operations_management dbr:Vehicle_rescheduling_problem dbr:Social_cognitive_optimization dbr:Egon_Balas dbr:Ellis_L._Johnson dbr:Möbius_ladder dbr:Constrained_least_squares dbr:Constrained_optimization dbr:Constraint_(mathematics) dbr:Continuous_or_discrete_variable dbr:LINDO dbr:Underdetermined_system dbr:MINTO dbr:Combinatorial_optimization dbr:Computational_complexity_theory dbr:Feasible_region dbr:Lester_G._Telser dbr:PLS_(complexity) dbr:Proportional_approval_voting dbr:Sridhar_Tayur dbr:Total_dual_integrality dbr:Softree_Technical_Systems dbr:COIN-OR dbr:Travelling_salesman_problem dbr:Gérard_Cornuéjols dbr:Held–Karp_algorithm dbr:Lattice_reduction dbr:Laurence_Wolsey dbr:Layered_graph_drawing dbr:Linear_programming dbr:APMonitor dbr:Algebraic_geometry dbr:Banner_blindness dbr:Center_for_Operations_Research_and_Econometrics dbr:Discrete_optimization dbr:Frameworks_supporting_the_polyhedral_model dbr:Graver_basis dbr:Kakuro dbr:Kemeny–Young_method dbr:List_of_NP-complete_problems dbr:Quadratic_programming dbr:Hendrik_Lenstra dbr:Hydrological_optimization dbr:Hypohamiltonian_graph dbr:Karen_Aardal dbr:Karmarkar-Karp_bin_packing_algorithms dbr:LINGO_(mathematical_modeling_language) dbr:Bin_packing_problem dbr:TOMNET dbr:Coffman–Graham_algorithm dbr:Efficient_approximately-fair_item_allocation dbr:Hermite_normal_form dbr:HiGHS_optimization_solver dbr:Automatic_label_placement dbr:Applications_of_integer_programming dbr:CPLEX dbr:Polyhedral_combinatorics dbr:Grothendieck_inequality dbr:Integer_linear_programming dbr:Integer_set_library dbr:Algorithms_for_integer_programming dbr:Operations_research dbr:Optimization_Toolbox dbr:RAPTOR_(software) dbr:Ralph_E._Gomory dbr:Ravindran_Kannan dbr:Chaotic_hysteresis dbr:Manufacturing_resource_planning dbr:Mathematical_Optimization_Society dbr:Satisfiability dbr:Special_ordered_set dbr:Shmuel_Onn dbr:Weapon_target_assignment_problem dbr:Facility_location_problem dbr:Social_learning_theory dbr:Theory_of_equations dbr:River_crossing_puzzle dbr:TOMLAB dbr:Integer_Programming dbr:Integer_linear_program dbr:P_versus_NP_problem dbr:Talent_scheduling dbr:INteger_programming dbr:Lenstra's_algorithm dbr:Discrete_linear_optimization dbr:Mixed-integer_programming dbr:Mixed_integer_linear_optimization dbr:Integer_Programming_Problem dbr:Integer_constraint dbr:Integer_linear_optimization dbr:Integer_program |
| is dbp:knownFor of | dbr:Ellis_L._Johnson |
| is foaf:primaryTopic of | wikipedia-en:Integer_programming |
