# Tag Info

Accepted

### In an integer program, how I can force a binary variable to equal 1 if some condition holds?

If $x$ is binary: Then the "if" condition really means either "$x = 0$" or "$x=1$". To enforce "if $x=0$ then $y=1$": use $$y \ge 1-x.$$ To enforce "if $x=1$ then $y=1$": use $$y \ge x.$$ If you ...
• 13.2k

### Feeding known lower bounds to solvers

Interesting topic (the question was raised several times by my students as well). My short answer is that adding the lower bound through a cut seems a good idea at first glance, but it creates a ...
• 1,696

### What are good reference books for introduction to operations research?

For books with a focus on industrial applications, see this other question of this forum As textbooks, I would recommend to have a look at: General Intro to OR: W. Winston. Operations Research: ...
Accepted

### What's the difference between Lagrangian relaxation and Lagrangian decomposition?

They are not the same thing. Lagrangian decomposition is a special case of Lagrangian relaxation. (Note: I'm talking specifically about integer programming problems in this answer, though some of ...
• 13.2k

### Combinatorial Optimization: Metaheuristics, CP, IP -- "versus" or "and"?

Here, in approximate order, are my criteria. Do I need a provably optimal solution (which rules out metaheuristics, other than to generate an initial feasible solution)? Is this something CPLEX can ...
• 40.1k

### When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs

Here is the advice in the IBM CPLEX documentation. So this pertains to CPLEX. I don't know to what extent it applies to other solvers. First of all, indicator constraints may not be available in all ...
• 13.8k
Accepted

### How to choose between high number of binary variables or fewer number of integer (not only 0 and 1) variables in a IP formulation?

I learned very early (this may not be generally true) that I should always prefer binary over integer variables. A reason is that from binary values you can infer logical information, branching on a ...
• 5,949
Accepted

### What is the difference between integer programming and constraint programming?

You have asked a broad question, so I will provide a broad answer. Integer programming typically refers to integer linear programming which is a mathematical modeling and solution paradigm. Decisions ...
• 1,542
Accepted

### When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs

For Gurobi there seems to be a dual advantage of using general constraints (http://www.gurobi.com/documentation/8.1/refman/constraints.html#subsubsection:GeneralConstraints): Benefit number one - ...
• 1,343
Accepted

### Divisibility constraints in integer programming

I going to assume that the ratio $L(x)/Q(x)$ is nonnegative. If it can be negative, I think there may be a workaround, but this will complicated enough without dealing with that. I'm also going to ...
• 40.1k
Accepted

### Expressing a chain of boolean ORs using ILP

Derivation via conjunctive normal form: x_1 \implies \underset{i=2}{\overset n{\lor}} x_i \\ \neg x_1 \bigvee \underset{i=2}{\overset n{\lor}} x_i \\ 1 - x_1 + \sum_{i=2}^n x_i \ge 1 \...
• 33.6k
Accepted

### Duality in mixed integer linear programs

It is a difference whether one can dualize (or not) or that a duality theory holds (or not). Formally, you can formulate a dual of any integer program, e.g., by considering the linear relaxation, ...
• 5,949

### Nonlinear integer (0/1) programming solver

Option 1: Submit as is to a solver which can globally optimize MIQPs having non-convex objective, and which might reformulate to a linearized MILP model under the hood. Such solvers include CPLEX, ...
• 13.8k

### Is Traveling Salesman Problem "Combinatorial Optimization" or "Integer Optimization"?

I'm not sure that the terminology is used consistently enough to give a firm answer. Pretty much everyone would agree (I think) that the TSP is a combinatorial optimization problem. To me, asking ...
• 40.1k

One definition of quadratization (perhaps there is more) is provided in the paper by Boros, 2018. In non-mathematical terms, quadratization is defined as a quadratic reformulation of the ...
• 5,452
Accepted

### In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?

Let $M$ be a new parameter (constant) that equals a large number. Greater-than-or-equal-to constraints: The constraint is $a_1x_1 + \cdots + a_nx_n \ge b$. Rewrite it as a_1x_1 + \cdots + a_nx_n \...
• 13.2k

### Can an integer optimization problem be convex?

Feels like you are asking two things, tractability of convex problems and convexity of integer problems. A first order approximation is that convex programs are tractable, .i.e., most problems you ...
• 1,702
Accepted

### Variable fixing based on a good feasible solution

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 ...
• 2,335

### Variable fixing based on a good feasible solution

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 ...
• 13.2k

• 3,469

### In an integer program, how I can force a binary variable to equal 1 if some condition holds?

Rather than linearising the logical constraint, I would try the logical constraints built in a solver. Gurobi and SCIP both have indicator constraints. My colleague works with these a lot and he’s ...
• 1,245