15

As far as I know, it is not possible to fix any variables solely based on a feasible solution without compromising the exactness of your solution method. However, variable fixing is possible when you have both an upper bound and a lower bound on the optimal objective value, using a method called reduced cost fixing (see e.g. Atamtürk, Nemhauser & ...


15

A similar idea as suggested by @ RolfvanLieshout uses Lagrangian duals instead of LP duals, in a Lagrangian-based branch-and-bound scheme. For example, in the uncapacitated fixed-charge location problem (UFLP), the most common Lagrangian approach relaxes the assignment constraints ($\sum_j y_{ij} = 1 \ \forall i$), uses the Lagrangian subproblem to calculate ...


11

No, state of the art LP solvers do not do that. They do bring the problem into a computational form that suits the algorithm used. Note that in the case of simplex algorithms, modern solvers use the revised simplex method with lower and upper bounds that does not require standard form. You can get an idea of the computation forms used from "...


7

I am not familiar with objective integrality cuts, but I know that CPLEX has the option to set the parameter absolute objective difference cutoff. If you set this parameter to 1, CPLEX will terminate the search if the difference between the best integer solution and the best bound is strictly less than 1.


5

I am not aware of anything in the Coin-OR or AMPL ecosystem that does that as i am not familiar with those ecosystems. However one can convince the open source modeling language JuMP to do what you want with a few lines of Julia. I assume you have a Julia installed and JuMP installed into your working (or global) environment. Let's first create a model: ...


4

AFAIK Lindo have implemented objective integrality cuts, but I don't know the details of the implementation. It's always a trade-off that depends on what type of problems a solver's users solve more frequently. We don't use them in our solver because the slowdown we experience from the sheer number of constraints that must be added to impose integrality ...


4

I recommend you to try very powerful utility LRS, http://cgm.cs.mcgill.ca/~avis/C/lrs.html. It is an open source application (a set of applications) to handle polyhedrals. B.t.w. one of LRS applications, called redund "removes redundant inequalities from an H-representation" (from description) - seems that what you need. There are parallel (MPI-...


3

Based on their manual, as I understood, Gurobi does not reformat the equality constraint because the equality expression can immediately be added to the list of constraints. They use more clever ways to handle these situations but as a black-box commercial solver, they don't share these approaches with the public and you would never know those techniques. ...


3

You could try loading the problem through AMPL. AMPL is blazing fast so size won't be an issue, and it has its own presolve, which is very good. I've seen it reduce problems from 100Kx100K to 5Kx5K. The way you would use this would be to use AMPL to produce an .nl file which is a dense format to describe the presolved model. You can then load that .nl file ...


2

Here some quick thoughts for linear programs. Lets assume $v_1,\ldots,v_n$ are unbounded variables in your problem and we are maximizing. Then look if there are only constraints (where $v_i$ is separable) of the form $... \leq v_i$ If $v_i$ has only a positive linear coefficient. Dominating columns with the right objective coefficients Of course for all ...


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