Skip to main content
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 ...
LarrySnyder610's user avatar
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 ...
Matteo Fischetti's user avatar
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 ...
LarrySnyder610's user avatar
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 ...
prubin's user avatar
  • 39.6k
20 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 ...
Mark L. Stone's user avatar
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 ...
Marco Lübbecke's user avatar
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 ...
alerera's user avatar
  • 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 - ...
CMichael's user avatar
  • 1,333
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 ...
prubin's user avatar
  • 39.6k
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 \...
RobPratt's user avatar
  • 32.7k
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, ...
Marco Lübbecke's user avatar
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, ...
Mark L. Stone's user avatar
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 ...
prubin's user avatar
  • 39.6k
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 ...
TheSimpliFire's user avatar
  • 5,432
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 \...
LarrySnyder610's user avatar
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 ...
Johan Löfberg's user avatar
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 ...
Rolf van Lieshout's user avatar
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 ...
LarrySnyder610's user avatar
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....
RobPratt's user avatar
  • 32.7k
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 ...
JakobS's user avatar
  • 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 ...
JakobS's user avatar
  • 2,767
14 votes

How to use the least number of colours to colour different routes of a bus route such that no two intersecting routes will have the same colour

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 ...
Richard's user avatar
  • 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} ...
phil's user avatar
  • 141
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 ...
Hassan's user avatar
  • 300
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 ...
Michael Trick's user avatar
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 ...
CMichael's user avatar
  • 1,333
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 ...
Richard's user avatar
  • 3,459
12 votes

Feeding known lower bounds to solvers

Branch-and-bound solvers often use node lower bounds to select the next node to process, e.g. in a best-first search. An external lower bound can lead to a different search order, and thus you may ...
Marcus Ritt's user avatar
  • 2,725
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 ...
Edward Lam's user avatar
  • 1,235

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