Tag Info

The logical AND relation can be modeled in one range constraint instead of three constraints (as in the other solution). So instead of the three constraints $$y_1\geq x_1+x_2−1,\qquad y_1\leq x_1,\... 11 votes Accepted Is weighted XOR-SAT NP-hard? A classical result of Berlekamp, McEliece, and van Tilborg shows that the following problem, maximum likelihood decoding, is NP-complete: given a matrix A and a vector b over \mathbb{F}_2, and ... • 270k 10 votes Linear programming with absolute values All constraints in a linear program are convex (if x,y satisfy the constraints, then tx+(1-t)y also does for all 0 \leq t \leq 1). The constraint |a|+b > 3 is not convex, since (4,0) and ... • 270k 10 votes Accepted How to partition a set into a given number of disjoint subsets subject to some conditions? This problem is NP-hard by reduction from Vertex Cover. In the Vertex Cover problem, we are given a graph G = (V, E) and a number r, and our task is to determine whether there is some subset U ... • 5,154 8 votes Accepted Linear programming with absolute values I've found out a very interesting document that answers my question: http://lpsolve.sourceforge.net/5.5/absolute.htm It's about integer programming and it covers all possible cases I think. See ... • 301 8 votes What is the decision version of integer programming? It's the same as for all NP problems; the optimisation problem is Find a valid solution s that minimises¹ f(s)! and the corresponding decision problem is Is there a valid solution s with f(s)... • 70.9k 8 votes Finding all solutions to an integer linear programming (ILP) problem "Linear programming" is an optimisation problem. The problem that you are trying to solve is to count lattice points inside a finite convex rational polytope. This problem has a polynomial-time ... • 18.9k 8 votes Accepted Are there practical methods for solving ILP? Some ILPs can be solved rapidly (to an exact solution) in practice; some cannot. Usually when we are talking about solving an ILP, we are looking for an exact solution, though some ILP solvers can ... • 141k 7 votes Find perfect matching whose weight is minimal, in polynomial time Yes, there is a polynomial-time algorithm for your problem. There's no need to use a LP or ILP; you can solve it directly using combinatorial, graph-based methods. In particular, we can solve your ... • 141k 7 votes Accepted Cast to boolean, for integer linear programming I think I can do it with one extra binary variable \delta \in \{0,1\}:$$ -100y \le x \le 100 y  0.001y-100.001\delta \le x \le -0.001y+100.001 (1-\delta) $$Update This assumes x is a ... 7 votes Why can't we round results of linear programming to get integer programming? In \mathbb R, one can simply round down or round up to obtain an element of \mathbb Z. Only two choices! However, in \mathbb R^n, one has 2^n ways of rounding to obtain an element of the ... 6 votes Accepted Restricted Integer Programming All four problems are NP-complete. Let me start by proving two easy results: Your problem #3 is NP-complete, even when the matrix has only a single row, as explained here: Complexity of a subset sum ... • 141k 6 votes Accepted Efficient algorithm for simple constraint satisfaction problem There is unlikely to be any efficient algorithm. Your first class of constraints are monotone exactly-1 CNF clauses. Your second class of constraints are monotone CNF clauses. The monotone part ... • 141k 6 votes Accepted How to check if a specific ILP problem can be solved in polynomial time or not? First of all, let me start by making clear that the notion of 'solvable in polynomial time' is something defined on a class of problem instances. It makes no sense to speak of polynomial time for a ... • 6,978 5 votes Can you generate random linear programming problems? Sure, of course you can create random linear programming problems. Why not? Yes, in general, you can usually verify the solution to a linear programming problem faster than you can find the solution.... • 141k 5 votes Accepted Are some Integer programming formulations completely useless for relaxation? Yes, some IP formulations are less useful than others. The technique used to show that an LP relaxation can only be so good is showing integrality gaps. For a minimization problem, an integrality gap ... • 270k 5 votes Accepted Why can't we round results of linear programming to get integer programming? If there are only constraints that place a lower bound on the number of trucks, but no constraints that place an upper limit on the number of trucks, then of course you can round up. That will still ... • 141k 5 votes Reducing Zero-One Integer Linear Programming problem to SAT The existence of such a reduction follows immediately from the Cook-Levin theorem, which guarantees that you can reduce any problem in NP to SAT and describes explicitly one way to do it. Just work ... • 141k 5 votes Accepted Boolean variable true iff equation is satisfied in ILP You can do this by introducing the two inequalities$$x_1 \le x_2 + M (1-y)$$and$$x_1 > x_2 - M y.$$The former encodes the requirement y=1 \implies x_1 \le x_2 (you can see that if y=1, ... • 141k 5 votes Accepted Converting If-else condition to Linear Programming This can be expressed with just the equation X=Y. Since X,Y are zero-or-one variables, the only possible assignments that are consistent with your condition are X=Y=0 and X=Y=1. See Express ... • 141k 5 votes Accepted Does integer programming \in NP imply NP=CoNP? The notion of duality suggested by the discrete Farkas lemma found in Lasserre's paper does not correspond to an integer program. There is a notion of duality for integer programs (see for example ... • 270k 5 votes Does integer programming \in NP imply NP=CoNP? The decision problem version of integer linear programming is known to be in NP. In particular, determining whether an integer linear program has a feasible solution is in NP. It is known that if an ... • 141k 5 votes Accepted Are there competitions for integer programming? There are competitions for constraint satisfaction solvers. Some problems there can be readily translated to IP solvers as well. See e.g., MiniZinc challenge which has taken place yearly since 2008 or ... • 22.1k 5 votes Are there competitions for integer programming? There are no competitions targeting general integer programming or mixed integer programming, but there are (or were) benchmarks, such as the MIPLIB (linear) and the MINLPLIB (nonlinear). There are ... 4 votes How to reduce the low-rank matrix completion problem to integer programming? Simplifying the problem: Given a positive integer r positive integers m, n \geq 2 a partial binary matrix \mathrm A \in \{*, 0,1\}^{m \times n} (where * denotes an unknown entry)... 4 votes Accepted Fastest known complexity for combinatorial ILP algorithm? From what I can tell by searching, the definite survey seems to be: Aardal, Karen, Robert Weismantel, and Laurence A. Wolsey. "Non-standard approaches to integer programming." Discrete Applied ... • 22.1k 4 votes Reducing Zero-One Integer Linear Programming problem to SAT There are two variants to perform the encoding. I am assuming that you want the SAT instance in Conjunctive Normal form, as otherwise your ROBDD can be mapped pretty directly to a Boolean formula of ... • 2,682 4 votes Boolean variable true iff equation is satisfied in ILP You could add a constant 0<A<M and then you add this constraint:$$A-y(A+M)\leqslant x_1-x_2\leqslant M(1-y).$$If y=1 then you are left with$$-M\leqslant x_1-x_2\leqslant 0, which ...
Maybe there is something I do not understand in your question, but the way it is formulated it seems that the set of solutions is: set $b_i=1$ if $x_i > 0$ set $b_i=0$ if $x_i < 0$ all others \$...