37
votes
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
29
votes
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
25
votes
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: ...
25
votes
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
23
votes
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
21
votes
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
20
votes
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
19
votes
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
17
votes
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
17
votes
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
16
votes
Accepted
Expressing a chain of boolean ORs using ILP
Derivation via conjunctive normal form:
\begin{equation}
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
16
votes
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
16
votes
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
16
votes
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
15
votes
What is quadratization?
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
15
votes
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
15
votes
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
15
votes
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
15
votes
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
15
votes
How can we write a binary variable as a power to a constant number?
If you check the two cases for $x_{i,j}$, you will see that you can rewrite the expression as a linear function of $x_{i,j}$:
$x_{i,j}=0$ yields $1-0.3^0=0$
$x_{i,j}=1$ yields $1-0.3^1=0.7$
So $1-0....
- 33.6k
14
votes
When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs
To the best of my knowledge the indicator constraints are just syntactic sugar for the user. Internally these indicator constraints are reformulated using computed big-M formulations or SOS ...
- 2,767
14
votes
Does this $0-1$ integer program have any speciality?
In general no, these problems are hard. BUT: You might want to look into totally unimodular matrices and total dual integrality but this requires additional assumptions on the matrix or the problem ...
- 2,767
14
votes
How to use the least number of colors to color different routes of a bus route such that no two intersecting routes will have the same color?
Recognize that each route can be viewed as being a node on a graph. Edges connect nodes if the routes the nodes represent intersect. This is the canonical graph coloring problem for which there are a ...
- 543
14
votes
Nonlinear integer (0/1) programming solver
Maybe I am missing something but it looks like there is no need for a library:
\begin{align}
\sum_i \sum_j \sum_k x_{ji} y_{kj} cost(i,k)&=\sum_i \sum_j x_{ji} \sum_k y_{kj} cost(i,k)
\end{align}
...
- 141
13
votes
Accepted
How to reduce recursion when using Gomory cutting planes to solve an integer program?
The slow convergence of the Gomory cuts was well-known and source of frustration for the field up until the 90s. It seemed that Gomory cuts would be a cute idea, but not one that would lead to any ...
- 2,362
13
votes
In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?
These are know as "indicator constraints" or "on/off" constraints. The best formulation is the convex-hull one, it includes the optimal big-M value plus additional non-redundant constraints, here's a ...
- 300
13
votes
Accepted
Why is there not a feasible solution for a MIP?
Yes - such a question can be answered by looking at the irreducible inconsistent subsystem (IIS).
From the Gurobi documentation:
An IIS is a subset of the constraints and variable bounds with the ...
- 1,343
13
votes
Can an integer optimization problem be convex?
Mathematically, mixed-integer programs (MIPs) are non-convex, for the very reason you stated: the set $x \in \{0,1\}$ is inherently non-convex. In fact, for a convex optimization problem (e.g. linear ...
- 3,469
12
votes
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
12
votes
Accepted
How to get bounds on ILP optimal solution quality
I cannot speak for Gurobi, but CPLEX definitely has this capability, and my guess is that any solver library does. For a standalone solver (as opposed to one with an API), you might have to look for ...
- 40.1k
Only top scored, non community-wiki answers of a minimum length are eligible