What kind of algorithm could be used to produce an ordering which maximizes # of satisfied 'less than' constraints?

Question

Let's say I have a set of items {e₁, e₂, ..., e_n}, and I also have a set of constraints {c₁, c₂, ..., c_m}, with c_i := e_j appears before e_k, for some j and k.

I want to produce an ordering of my items which maximizes the number of satisfied constraints, with the possibility that some of the constraints are contradictory. I'm not sure how to search for this, but I hope there is some known efficient algorithm for this.

It might also be helpful if, given weights for the constraints, I could instead maximize the total weight of the satisfied constraints, rather than just the number.

Answer 1

You can do this with Linear Programming and Constraint Programming. It's helpful since many of the problems in this domain are NP-Hard. The specific algorithm in this case is typically known as the "Simplex Algorithm".

Some quick summaries:

Of Linear Programming:

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.

and Constraint Programming:

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.

Answer 2

I am uncertain as to whether you have any additional information that could allow you to optimize the problem. In general, I agree with World Engineer, that it is NP-complete if presented in this general case.

In general, what you can do if you truly have the NP-complete version of the problem to solve is encode it into any other NP-complete problem, with which you are more familiar with / have better solvers available for. Below is an example of how to do this. In general, if you want to solve larger instances of this problem as fast as possible it might be worthwhile to encode them into SAT problems, as there are blazing fast solvers available for these.

Example encoding as feedback arc set problem

Consider your elements as a graph and the set of lower-than-constraints as edges, hence, you have an edge between two nodes iff there exists a constraint c_i stating that the source node needs to be less than the target node (or vice versa, as long as it is consistent).

You can then search this graph for cycles. A cycle in the graph corresponds to a set of constraints that are inconsistent (smallest possible cycle would be A <-> B, meaning A < B and B < A). The problem can then be reformulated as follows: remove the minimal number of edges required to make the graph acyclic. What you need to find therefore is the minimal feedback arc set (which of course is NP-complete again).

(I will leave it as an exercise to the reader to prove that this is indeed a polynomial-time reduction.)

Answer 3

To add a bit more information to the comment I left on World Engineer's answer:

This is generally referred to as multi-objective optimisation. Wikipedia has a pretty good summary of the topic, I recommend you go through it. The good news is that it's a very well researched area, with plenty of ideas and algorithms available. The bad news is that it is a difficult area of optimisation, except in the most basic cases (which can often be solved with basic maths, e.g. with Linear Programming).

If your set of constraints is pretty fixed (or generally follows some simple pattern), I'd recommend attempting to solve the problem in a mathematical fashion. These solutions are almost always more efficient than the alternatives, which would be some kind of exhaustive search, or if the search space is too big, a randomised search with some kind of heuristic / intelligence built into it.

A word on weighting: there typically exist a whole number of solutions which are "pareto optimal", which means that you can no longer improve any of the objectives without causing impairment to the others (this is akin to "local minimum / minima" in standard optimisation). Together, these pareto-optimal solutions form the pareto front, which often forms a visually continuous shape. Mathematically, these solutions are considered equivalent, and it is up to you to provide extra information in order to choose between them, i.e. which trade-offs you consider more important. Sometimes, these decisions are left up to the user, and the role of the software is to provide them with the various pareto-optimal solutions (e.g. an investment professional choosing risk profile for a portfolio). This could be an option to consider in your case, too.