Quale tipo di algoritmo può essere usato per produrre un ordinamento che massimizza il # di vincoli "meno di" soddisfatti?

Puoi farlo con Programmazione lineare e Constraint Programming . È utile poiché molti dei problemi in questo dominio sono NP-Hard. L'algoritmo specifico in questo caso è in genere noto come " Algoritmo Simplex ".

Alcuni riepiloghi rapidi:

Di Programmazione lineare:

Linear programming (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships. Linear programming is a specific case of mathematical programming (mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polyhedron, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued affine function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such a point exists.

e Programmazione vincoli:

In computer science, constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. This makes constraint programming a form of declarative programming. The constraints used in constraint programming are of various kinds: those used in constraint satisfaction problems (e.g. "A or B is true"), those solved by the simplex algorithm (e.g. "x ≤ 5"), and others. Constraints are usually embedded within a programming language or provided via separate software libraries.

Non sono sicuro che tu abbia ulteriori informazioni che potrebbero permetterti di ottimizzare il problema. In generale, sono d'accordo con World Engineer, che è NP-completo se presentato in questo caso generale.

In generale, ciò che puoi fare se davvero hai la versione completa del problema NP da risolvere è codificarlo in qualsiasi altro problema NP-completo, con il quale hai più familiarità con / avere migliori risolutori disponibili. Di seguito è riportato un esempio di come farlo. In generale, se vuoi risolvere istanze più grandi di questo problema il più velocemente possibile, potrebbe essere utile codificarle in SAT problemi, in quanto vi sono dei risolutori veloci per questi.

Esempio di codifica come problema dell'arco di feedback

Considera i tuoi elementi come un grafico e l'insieme di limiti inferiori ai limiti, quindi, hai un margine tra due nodi se esiste un vincolo c_i che afferma che il nodo di origine deve essere inferiore alla destinazione nodo (o viceversa, purché sia coerente).

Puoi quindi cercare questo grafico per i cicli. Un ciclo nel grafico corrisponde a un insieme di vincoli che sono incoerenti (il ciclo più piccolo possibile sarebbe A < - > B, che significa A < B e B < A). Il problema può quindi essere riformulato come segue: rimuovere il numero minimo di spigoli necessari per rendere il grafico aciclico. Quello che devi trovare è quindi il set di arco di feedback minimo (che naturalmente è di nuovo NP-completo)

(Lascerò come esercizio al lettore per dimostrare che questa è davvero una riduzione del tempo polinomiale ).

Per aggiungere un po 'più di informazioni al commento che ho lasciato sulla risposta di World Engineer:

Questo è generalmente definito ottimizzazione multiobiettivo. Wikipedia ha un sommario piuttosto buono dell'argomento, ti consiglio di esaminarlo. La buona notizia è che si tratta di un'area molto ben studiata, con molte idee e algoritmi disponibili. La cattiva notizia è che si tratta di un'area di ottimizzazione difficile, tranne che nei casi più basilari (che possono spesso essere risolti con matematica di base, ad esempio con Programmazione lineare).

Se la serie di vincoli è piuttosto fissa (o generalmente segue un semplice schema), consiglierei di provare a risolvere il problema in modo matematico. Queste soluzioni sono quasi sempre più efficienti delle alternative, che sarebbero una sorta di ricerca esauriente, o se lo spazio di ricerca è troppo grande, una ricerca randomizzata con una sorta di euristica / intelligenza integrata in esso.

Una parola sulla ponderazione: esiste tipicamente un numero intero di soluzioni che sono "pareto ottimali", il che significa che non puoi più migliorare nessuno degli obiettivi senza causare danni agli altri (questo è simile al "minimo locale / minimi "nell'ottimizzazione standard). Insieme, queste soluzioni pareto-ottimali formano il fronte paretiano, che spesso forma una forma visivamente continua. Matematicamente, queste soluzioni sono considerate equivalenti, e spetta a te fornire ulteriori informazioni al fine di scegliere tra loro, cioè quali trade-off consideri più importanti. Talvolta queste decisioni sono lasciate all'utente e il ruolo del software è quello di fornire loro le varie soluzioni pareto-ottimali (ad esempio un professionista degli investimenti che sceglie il profilo di rischio per un portafoglio). Questa potrebbe essere un'opzione da prendere in considerazione anche nel tuo caso.