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

Let's say I have a set of items {e1, e2, ..., en}, and I also have a set of constraints {c1, c2, ..., cm}, with ci := ej appears before ek, 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.

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.

• I probably shouldn't have used the word 'constraints', since not all of them actually need to be met. I don't really see how to translate the problem of ordering the elements into a linear program... Apr 28 '13 at 23:20
• +1 for a pretty good summary (and identifying that it is often an NP-hard problem). A couple of comments - in general, it may be necessary to exhaustively search for all combinations / permutations in order to arrive at the best possible answer (OP may not realise this). In general AI terms, the problem is referred to as multi-objective optimisation (constraints are typically unbreakable rules, such as boundary constraints, as Bwmat points out). Apr 29 '13 at 5:58

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.)