19
Even if the decision variables differ, you may still be able to prove that one of the formulations is stronger than the other by introducing an appropriate mapping.
Take for example a flow formulation and a route formulation for a vehicle routing problem (minimization). Typically, the folllowing argument can be made:
Given (fractional) values for the route ...
18
Arguments 3 and 4 are incorrect. The Right-Hand Side (RHS) is not convex. Even if it were, setting a nonlinear equality with either side non-affine is non-convex. As the final coup de grace, even if the RHS were convex, an inequality, {affine expression} $\le$ {convex RHS}, is going the wrong direction to be convex.
I suggest you study sections 2.3 and ...
15
I'm not sure there is a single, definitive best way to compare models, and if there is I likely have never seen it applied. I lean toward computational comparisons if properly done, but "properly done" is in the eye of the beholder. The most obvious criteria for computational comparisons are that they use the same test problems (not selected because they ...
14
If solving the LP relaxation is taking as much time as solving the corresponding MILP formulation to optimality, I would assume one of two things:
1) Most of the work done by the MILP solver consists of solving the LP relaxation. Solving the LP relaxation is usually a step to solve any MILP with a general-purpose solver. In other words, there is probably no ...
13
Counterexamples to your arguments:
Argument 1:
Only affine equality constraints are convex, $x = y^2$ is not convex.
Argument 3:
Take $f(x) = x^4$ and $g(x) = x$. Both are convex, but the ratio $h(x) = \frac{x^4}{x} $ is not.
Argument 4:
Let $f(x) = x$, and $y \in \mathbb{R}$. $f$ is convex, but $g(x, y) = yf(x) = xy$ is not.
11
I think I've found an instance with four nodes and $p = 2$ via brute force (a lot of randomized instances). I've attached my Python script as well. I relaxed the Daskin and Maass (2015) formulation and assumed $I = J$.
Nodes: $I = J = \{1, 2, 3, 4\}$
Demands: $d = (75, 34, 40, 40)$
Costs (or distances):
$$
c =
\begin{bmatrix}
0 & 39 & ...
11
I agree with most of the comments here; Even if the decision variables are different, you may use proof by construction, for example, with appropriate mapping to prove that a formulation is stronger than another one. When comparing two different (yet equivalent) formulation for the same problem, I often use three criteria: (1) LP relaxation/tightness, (2) ...
9
Not sure about solving the LP relaxation, but you can get a closed-form lower bound from LP duality, without calling any solver. Let $y_j$ be the dual variable for constraint $j\in U$. The dual LP is to maximize $\sum_j y_j$ subject to
\begin{align}
\sum_{j \in s_i} y_j &\le 1 &&\text{for $i\in \{1,\dots,m\}$} \\
y_j &\ge 0 &&\text{...
7
Based on @prubin's instigation, I have turned my comment into an answer:
You can add an IloConversion of each variable to you IloModel object, and then solve the resulting model using a corresponding IloCplex object. In OPL you can run the covertAllIntVars() function on your OPL model and then solve the resulting model. I am almost sure that there is no ...
7
If LP takes a long time to solve, you can check a couple of things:
1) How large is the problem? Large LPs (>1 million variables/constraints on a ballpark) can take a long time.
2) How large is the range of coefficients in the objective function and constraints? Having a large range of the coefficients typically hurts computational performance.
6
I would like to add some criteria for the computational comparison, that I think is appropriate and common. As mentioned, the experiments should be performed on standard benchmarks, and if available, on more than one benchmark. Then, the metrics can be:
Number of feasible solutions,
Number of best found solutions,
Number of optimal solutions,
Gap to the ...
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 ...
4
Highly degenerate LP's can be very hard to solve using the simplex method and much easier to solve using an interior point method. It's possible that your LP relaxation has this issue.
3
I think the standard method is to stop just after the root node has been solved.
For example, using the C++ API:
// Uncomment the following line to disable CPLEX cuts:
// cplex.setParam(IloCplex::NumParam::CutsFactor, 0.0);
cplex.setParam(IloCplex::IntParam::NodeLim, 0);
cplex.solve();
const auto linear_relaxation_obj = cplex.getBestObjValue();
// If you ...
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
I want to expand on @Sunes answer, as I too wanted to solve the LP relaxation of my MIP and thought, there must be another solution than to convert each variable manually (at least this is how I interpreted @Sunes answer and it sounded needlessly complex). Therefore, I unnecessarily used up a lot more time searching through the internet for alternatives (...
2
There are two main reasons to add cuts. First, to tighten the relaxation, i.e., make the domain smaller whilst preserving the global solution. Second, to kick a known (or predicted) solution out of the problem. This is common in e.g. feasibility pumps, where we want to avoid cycling of solutions, or when we want to break symmetry. We can also generate cuts ...
2
Generally I see on the papers, at first comparison according to number of variables and equations, after then experimental performance comparison on test problems.
2
Can't you add a parameter to your model which defines the nature of your variables ?
Something like :
def my_model(model, continuous):
...
if continuous:
model.my_variable = Var(within=NonNegativeReals)
else:
model.my_variable = Var(within=PositiveIntegers)
...
and then model.solve().
I am not so familiar with Pyomo but with PuLP,...
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
Short answer: Here is a paper that uses the dual values
Akbari, V., & Salman, F. S. (2017). Multi-vehicle prize collecting arc routing for connectivity problem. Computers & Operations Research, 82, 52-68. https://doi.org/10.1016/j.cor.2017.01.007
Some additional points:
The sub-gradient method is a heuristic approach to solve the Lagrangian Dual ...
Only top voted, non community-wiki answers of a minimum length are eligible