# Tag Info

## Hot answers tagged integer-programming

26

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 want to require that $y=1$ if and only if the condition holds, then replace the $\ge$s above with $=$s. If $x$ is continuous: In this case, numerical inaccuracy ...

26

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 very large “unnatural” face where your search is trapped for a long while. Essentially you lose the objective function grip, and do not gain anything. Let me ...

20

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: Applications and Algorithms (4th Ed.). Brooks/Cole. 2004. Modeling: H.P. Williams. Model building in mathematical programming. John Wiley & Sons, 2013. D. Chen, R....

20

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 this answer applies to continuous optimization as well.) Lagrangian relaxation involves removing (relaxing) one or more constraints and penalizing violations of ...

20

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 handle (since I have a license for CPLEX and I'm familiar with it)? If CPLEX can handle it, should I consider a heuristic, metaheuristic or constraint solver to ...

18

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 situations: Indicator Constraints in Optimization The constraint must be linear; a quadratic constraint is not allowed to have an indicator constraint. ...

17

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 binary variable fixes its value (=reduces the model) etc. I would go even further. It may be better to have more variables. Why? Of course, this depends on the ...

16

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 are modeled as a vector of real numbers, some of which are further constrained to take only integer values. The decision vector is constrained to satisfy a ...

16

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 \\ x_1 \le \sum_{i=2}^n x_i$$

16

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, Gurobi 9.x, and BARON, among others. Option 2: Step 1 Linearize the products of binary variables, per How to linearize the product of two binary variables? . <...

15

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 - models are easier to create and can be interpreted easily: If a model contains general constraints, then Gurobi adds the respective MIP formulations for those ...

15

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 assume that $Q(x)$ and $L(x)/Q(x)$ have a priori upper and lower bounds, say $\underline{Q} \le Q(x) \le \overline{Q}$ and $L(x)/Q(x) \in \{1,\dots,N\}$. You can ...

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 ...

14

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 can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you would be told that in an introductory course on convex ...

14

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, dualizing it, and then enforcing integrality again on the dual variables. It is already trickier which variables to consider as integer in the dual when you dualize ...

14

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 number of exact and approximate algorithms. Specifically, you're trying to find a constructive algorithm for determining the chromatic number. For 10 routes ...

13

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 real computational success. Then work by Balas, Ceria, Cornuejols, and Natraj rekindled interest in the area, and Gomory cuts became very important in real ...

13

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 constraints (special ordered set constraints). It might be that you are better at computing the value of the big-M using additional knowledge that the solver does not ...

13

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 following properties: the subsystem represented by the IIS is infeasible, and if any of the constraints or bounds of the IIS is removed, the subsystem ...

13

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 respectively. If you are lucky, then your problem has these properties and you can solve it efficiently. Totally Unimodular Matrices A totally unimodular ...

13

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} Now since $\sum_k y_{kj}=1$, exactly one row is 1, the others zero. We pick the best one: $$=\sum_i \sum_j x_{ji} \max_k cost(i,k)$$ Since $\sum_j x_{ji}=1$ we ...

12

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 finding the indicator constraints in Gurobi perform worse than big-M. He’s in contact with the Gurobi developers so I might be able to get more info if there’s ...

12

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 note characterizing this formulation. There's also a generalization for convex nonlinear "on/off" constraints here and recent extensions here.

12

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 \ge b - M(1-y).$$ Then, if $y = 1$, the constraint is active, and if $y=0$, it has no effect since the right-hand side is very negative. (If all of the $a_i$ ...

12

This is quite a broad question, and I'm not sure you'll get the answers you need here. To learn how to formulate mathematical optimization problems takes learning and practice, and there's no concrete answer that we can provide on a Q&A site like this. Your best bet is to take a class that teaches or uses optimization modeling, or to learn from a good ...

11

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 the best bound in the output log and do some text scraping to get it. For the Java API to CPLEX, the function you want is IloCplex.getBestObjValue(), which ...

11

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 nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques. Rewriting this in ...

11

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 have to explore a different number nodes until finding an optimal solution, and proving its optimality. For concreteness imagine a simple depth $4$ binary search ...

11

Since you mentioned videos, I would suggest checking Coursera and edX for free MOOCs (such as the Deterministic Optimization course on edX or the Discrete Optimization course on Coursera). The Coursera site in particular has a nice search engine that makes finding courses easy. I have not done any of the optimization courses there, but I have done a couple ...

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