11

If the integer feasible set is finite and the LP polyhedron is bounded (a polytope), you could compare the volumes of the integer hull and this polytope.


9

Using the max operator, your objective function has directional derivatives but is not smoothly differentiable. For instance, if $x$ is scalar and $g(x) = x-2$, then at $x=2$ the max term has directional derivative 0 in the direction of decreasing $x$ and $c$ in the direction of increasing $x$. For a gradient-based algorithm, this makes the value of the ...


7

The McCormick envelope is one possible approach. Another, if the domain of $y$ is not too large, is to use a type 1 Special Ordered Set. Assume that $y\in\lbrace 1,\dots,N\rbrace$. Replace $y$ with$$\sum_{j=1}^N j\cdot z_j$$where the $z_j$ are binary variables, and replace the equation $xy=q$ with$$x=\sum_{j=1}^N\frac{q}{j}z_j.$$Add the constraint$$\sum_{j=1}...


6

Sometimes cuts from Boolean Quadric Polytope can help: https://link.springer.com/article/10.1007/s12532-018-0133-x


6

If (for small dimensions) it is feasible to enumerate the vertices of the polyhedron of the relaxation, as well as the actual feasible set, one could try to find a vertex with the highest distance to the feasible set. I guess this is equivalent to finding the "worst" objective function and could probably be posed as a bilevel problem with LP subproblem.


5

You are looking for a proof for Total Unimodularity (TU). TU is a property by which a linear program will always have an integral solution. All you need to prove is that in your LP $A$ matrix is TU and $b$ column has only integers. What is TU A matrix $A$ is unimodular if $\det(A) = 1$ or $-1$. A matrix $A$ is Totally Unimodular (TU) if each square ...


5

Another way of looking at this is to construct randomized-rounding algorithms from both relaxations, and select the relaxation which yields a randomized rounding algorithm with the best approximation guarantee. For instance, in max-cut we can construct an LP relaxation which provides a $0.5$ approximation ratio, or an SDP relaxation which provides a $0.878$...


4

Why it is recommended to compare the relaxed versions of each formulation to deduce the running time (and more precisely about the B&B tree size)? Generally, better (= tighter) is the relaxation of an integer optimization model, better should work a brand-and-bound tree solution approach to this model. Nevertheless, there exist some NP-hard problems for ...


4

Let us say that we have two MILP formulations $A$ and $B$ on the same variables, each with the corresponding LP relaxations defining polyhedra $P_A$ and $P_B$, respectively. We say that $A$ is stronger than $B$ if every point of $P_A$ is also contained in $P_B$ whereas some points of $P_B$ are not contained in $P_A$. For example, you may prove the first ...


4

To my knowledge, the term relaxation is used to indicate that a constraint (or a group of constraints) is removed from the model, rendering a model that is more loose, less constrained. In the context of Lagrangian relaxation, a constraint (or group of constraints) is removed from the model, and added to the objective function with a coefficient (or more ...


4

Rank-one constraints are unfortunately not mixed-integer convex representable, as shown in this paper: https://arxiv.org/abs/1706.05135, although they are quadratically-constrained quadratic representable. If the problem size is not too large, you can try solving it using Gurobi, either directly (for n<=10) or via branch-and-cut (for say n<=50; see ...


3

The initial gap can be an indicator but not a very good one. I have seen many problems start with a tight bound and then never improve, and I have also seen many problems start with a horrendous gap that improves very quickly. Honestly, there is no way to know in advance, we just have to try solving all formulations we can come up with, until we find one ...


3

If I'm understanding your question properly, this is not true in general. What you can prove is that this can be solved to integrality algorithmically, by adding Gomory cuts. Once enough cuts are added, the optimal vertex of the LP has to give an integer solution. This is known as the cutting plane method. In your case, you can use this to show that once no ...


2

Gurobi has some slides on what they did in the recent 9.0 version, which added the support for qcqp. It is not much and highlevel, but it might be still beneficial. https://pages.gurobi.com/rs/181-ZYS-005/images/2020-01-14_Non%20Convex%20Quadratic%20Optimization%20in%20Gurobi%209.0%20Webinar.pdf There is even a video for the slides: https://www.gurobi.com/...


2

Have you tried using SOCP relaxation instead of RLT?


2

Binary (Boolean) values are integer values. Therefore, optimization problems with boolean constraints are either integer programming or mixed integer programing (MIP). Generally, there is no easy algorithm that is guaranteed to find the optimal solution of MIP problems quickly. My reason to believe that is: I can implement a boolean satisfiability (b-sat) ...


1

Minimize $x^2$ where $1 \le x \le 2$. \begin{aligned} \min_{x} \quad & f(x)\\ \textrm{s.t.} \quad & h_{1}(x) \le 0\\ &h_{2}(x) \le 0 \\ \end{aligned} where \begin{align} f(x) &= x^2 \\ h_{1}(x) &= 1 - x \\ h_{2}(x) &= x - 2 \end{align} KKT conditions: \begin{align} 0 &= \nabla f(x) + \mu_{1}\nabla h_{1}(x) + \mu_{2} \nabla h_{...


1

In optimisation theory, creating a relaxation refers to an operation which: Creates a superset of an underlying set, if the operation is done on a set Produces a new set of functions that define a superset of a set associated with some original function (usually the feasible region). For instance, if I have a nonconvex function/set, I can create a convex ...


1

Assuming you have two closed polytopes, we can compare the volumes of the two polytopes as Rob Pratt mentioned. Unfortunately this is NP-hard as we need to identify all the vertices. A more tractable (heuristic) metric would be to measure the distance between every constraint and its relaxation (e.g. at the midpoints or some arbitrary vertex) and get a ...


Only top voted, non community-wiki answers of a minimum length are eligible