19 votes
Accepted

How to compare two different formulations of a problem?

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 ...
user avatar
18 votes
Accepted

Is This Constraint Convex?

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 ...
user avatar
15 votes

How to compare two different formulations of a problem?

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"...
user avatar
  • 28.9k
15 votes

Efficiency of solving LP relaxation

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 ...
user avatar
13 votes

Is This Constraint Convex?

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)...
user avatar
11 votes
Accepted

Symmetric undirected $p$-median instance with fractional LP solution?

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 ...
user avatar
  • 1,759
11 votes

How to compare two different formulations of a problem?

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 ...
user avatar
9 votes

I ran a relaxed MIP and got some integer results; how can I constrain MIP to match those integers?

It is possible that your model could become infeasible if you fixed the variables with integer values in the LP relaxation. Consider, for example, the problem of minimizing $y$ subject to the single ...
user avatar
  • 28.9k
9 votes

Specific algorithms to compute the LP-relaxation of the Set-Cover problem

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 ...
user avatar
  • 21.8k
8 votes

Cplex 12.10: How can I solve an LP relaxation?

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 ...
user avatar
  • 5,347
8 votes

Efficiency of solving LP relaxation

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 ...
user avatar
6 votes

How to compare two different formulations of a problem?

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, ...
user avatar
  • 2,034
5 votes

Efficiency of solving LP relaxation

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.
user avatar
5 votes

What is a general procedure to prove that the LP relaxation of an IP delivers the optimal IP solution?

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 ...
user avatar
5 votes
Accepted

I ran a relaxed MIP and got some integer results; how can I constrain MIP to match those integers?

It depends. It is true for the weighted node packing problem, where $x_i$ is a binary decision variable for each node and you want to maximize $\sum_i c_i x_i$ subject to $x_i + x_j \le 1$ for all ...
user avatar
  • 21.8k
3 votes

Cplex 12.10: How can I solve an LP relaxation?

I think the standard method is to stop just after the root node has been solved. For example, using the C++ API: ...
user avatar
3 votes

What is a general procedure to prove that the LP relaxation of an IP delivers the optimal IP solution?

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 ...
user avatar
2 votes

Cplex 12.10: How can I solve an LP relaxation?

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 ...
user avatar
  • 21
2 votes

What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?

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 ...
user avatar
2 votes

How to compare two different formulations of a problem?

Generally I see on the papers, at first comparison according to number of variables and equations, after then experimental performance comparison on test problems.
user avatar
  • 746
2 votes

Obtaining linear relaxation objective value from MILP model coded in Pyomo

Can't you add a parameter to your model which defines the nature of your variables ? Something like : ...
user avatar
  • 10.1k
2 votes

KKT conditions analysis for binary constraints

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 ...
user avatar
1 vote

Linear Relaxation of Boolean Constraint for Solving Integer Linear Program Using KKT

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^...
user avatar
1 vote

Is there any academic reference which suggests/uses dual values as initialization of Lagrangian multipliers?

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,...
user avatar

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