Skip to main content

Questions tagged [mixed-integer-programming]

For questions about mathematical optimization problems involving both continuous and binary or general integer variables.

Filter by
Sorted by
Tagged with
5 votes
1 answer
323 views

What is the impact of making flow fractional rather than integer?

When creating a network flow formulation you can set up sinks with integer flow requirement $\ge 1$. This yields solutions with the total amount of flow along an edge. I have also seen this as a ...
fhk's user avatar
  • 1,069
33 votes
8 answers
2k views

Modeling floor function exactly

Suppose we want to enforce a constraint $$ y=\lfloor{x}\rfloor $$ where $x$ is some continuous variable. One option is to use $$ x-1\leq{y}\leq{x},\quad y\in\mathbb{Z}, $$ which fails on the edge case ...
David M.'s user avatar
  • 2,117
10 votes
1 answer
218 views

Conditional Controls in MIP Models

Innocently cross-posted at Mathematics SE I am developing a model that operates in the realm of mixed integer programming, although I am fairly unfamiliar with this area of mathematics at the moment. ...
GrayLiterature's user avatar
31 votes
3 answers
2k views

Feeding known lower bounds to solvers

Given an optimization problem that aims at minimizing some objective function, a lower bound that is valid for all feasible solutions, and your solver of choice: For what theoretical and/or practical ...
fbahr's user avatar
  • 1,026
13 votes
2 answers
129 views

Sensible and realistic way to model truck based transport costs depending on amount

Different kinds of problems involve transporting an amount $x$ from A to B which results in a cost $c(x)$ in the objective function. Traditionally, often linearized costs are used to get an easy, ...
J Fabian Meier's user avatar
3 votes
1 answer
229 views

On what kind of problems a local search may perform better than MIP / CP techniques? [closed]

In combinatorial optimization, on what type of problem a local search may lead to better & quicker solutions than usual mixed-integer programming and constraint programming techniques ? By type ...
Aral's user avatar
  • 63
13 votes
1 answer
2k views

Difference between lazy callbacks and using lazy constraints directly

I'm trying to use lazy constraints to solve an optimization problem. In some software such as CPLEX or GUROBI, they have some tools to handle them directly (in the original model) or using callback ...
A.Omidi's user avatar
  • 9,046
23 votes
10 answers
819 views

Reference for column generation applications

When talking about column generation algorithms, the main example is the cutting stock problem. I'm aware that variations of vehicle routing problem (VRP) can be solved using a column generation ...
EhsanK's user avatar
  • 5,874
14 votes
3 answers
5k views

When should I use dual Simplex over primal Simplex?

In Gurobi the user can change the method parameter in order to force Gurobi to use a particular method for solving MIPs. The user can, amongst others, choose ...
YukiJ's user avatar
  • 2,033
11 votes
5 answers
1k views

Dealing with non-overlapping constraints

Let us consider the following problem: Let $T$ be a set of tasks. Each task $t \in T$ has a duration $d_t$ and a target start time $s_t$. No two tasks can be executed in parallel. The objective is to ...
Renaud M.'s user avatar
  • 2,428
51 votes
8 answers
3k views

Optimization Problem Libraries

Can someone please make a list of optimization problem libraries so that the community can add to and refine it? I know a few off the top of my head.
Mark L. Stone's user avatar
25 votes
2 answers
6k views

Why is it important to choose big-M carefully and what are the consequences of doing it badly?

The question here discusses the two different use of "big-M method", where one of them is the big-M in logical constraints and linearization in (mixed-)integer programming problems (that's what I'm ...
EhsanK's user avatar
  • 5,874
19 votes
6 answers
8k views

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

Various optimization modeling languages and solvers allow for both indicator constraints (see for example here, here and here) and traditional binary variable and big-M approaches can be used to model ...
AndyT's user avatar
  • 193
24 votes
4 answers
1k views

What are the tradeoffs between "exact" and Reinforcement Learning methods for solving optimization problems

Exact methods, e.g., models that utilize an MIP approach with a specified objective and constraints, have advantages like the following: Using off the shelf solvers Optimality gap provability ...
fhk's user avatar
  • 1,069
14 votes
3 answers
1k views

Using CPLEX "solution pool" to count feasible points

Some problems call for a count of the number of integer "lattice" points contained in a feasible region (rather than for locating the minimum or maximum objective function value in that region). See ...
hardmath's user avatar
  • 247
17 votes
1 answer
5k views

What is the "big-M" method? And are there two of them?

I’ve seen the "big-$M$ method" referred to in different ways. What is the "big-$M$ method" and why does it seem to mean two different things?
LarrySnyder610's user avatar
13 votes
4 answers
792 views

The effect of choosing big M properly

I have a set of linearized constraints that are modelled using big-Ms. Now, it is, of course, common knowledge to make the value of M and small as possible in order to provide tighter LP relaxations ...
Albert Schrotenboer's user avatar
12 votes
2 answers
4k views

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

Suppose we have the constraint $$a_1x_1 + \cdots + a_nx_n \gtreqless b,$$ where $a_i$ and $b$ are constants and $x_i$ are decision variables. Suppose also that we want the constraint to hold if $y=1$ (...
LarrySnyder610's user avatar
15 votes
4 answers
2k views

Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?

Is there a single crisp and accessible reference which covers how to generate Mixed Integer Programming formulations to linearize products, handle logical constraints and disjunctive constraints, do ...
Mark L. Stone's user avatar
16 votes
2 answers
710 views

Branching rules in commercial MIP solvers

I am working on a branch-and-cut algorithm, and I have spent quite some effort into improving the branching decisions that are made by commercial solvers, such as CPLEX and Gurobi. However, it was ...
Albert Schrotenboer's user avatar
17 votes
1 answer
5k views

The difference between max-min and min-max

I am solving two-stage optimization problems in the form of $$\max_{x \in X}\min_{y \in Y} f(x,y),$$ where $f(x,y)$ is the solution of a mixed integer linear program (MIP). As the constraints of the ...
Albert Schrotenboer's user avatar
32 votes
3 answers
19k views

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

Suppose we have a binary or continuous variable $x$, a binary variable $y$, and a constant $b$, and we want to enforce a relationship like If $x \gtreqless b$, then $y = 1$. How can we write this ...
LarrySnyder610's user avatar
22 votes
5 answers
2k views

How can I best handle symmetries in my MIP?

When dealing with mixed-integer-programs with many symmetric solutions it can take very long until the branch-and-bound-tree search is finished because symmetric optimal solutions cannot be pruned. ...
YukiJ's user avatar
  • 2,033
17 votes
5 answers
773 views

Presolve is cutting down a lot of binary variables. Should I rethink my formulation?

I built my model on Python and am passing it to Gurobi to solve the problem. The presolve phase of Gurobi cuts down ~80% of the integer/binary variables and I am wondering if I should rethink my ...
Abhishiekh Ramesh's user avatar
26 votes
4 answers
2k views

Stochastic programming MIP solvers

I am aware that Benders Decomposition is readily available in CPLEX and in SCIP; but are there any (free) solvers that provide off the shelf stochastic programming MIP algorithms or a nice to work ...
Albert Schrotenboer's user avatar
18 votes
1 answer
3k views

Working with absolute values in constraint in a LP or MILP

Having all the approaches explained in the blog called "OR in an OB World" (this address) in my mind, I would like to ask the following question: What is the best practice to make a constraint linear ...
Oguz Toragay's user avatar
  • 8,677

1
17 18 19 20
21