Operations Research Stack Exchange
Operations Research Stack Exchange

Most Popular

more tags
1500 questions
13
votes
1 answer

Categorization of optimization models

For many families of optimization problems there is some sort of classification scheme. I am thinking about the triple notation for machine scheduling introduced in "Optimization and approximation in deterministic sequencing and scheduling: a…
PSLP
  • 2,401
  • 9
  • 33
13
votes
6 answers

How to formulate: each pair of elements in $A$ has one common unit in $B$

We have two sets, $A$ and $B$. Some elements of $A$ must be connected to some elements of $B$, but no element of a given set is connected to another element of the same set. (Think of a bipartite graph, and we are trying to establish the edges…
LarrySnyder610
  • 13,141
  • 3
  • 41
  • 105
13
votes
2 answers

Is This Constraint Convex?

I have a constraint that I believe to be convex and not affine which I think means that I can implement a relaxation. I will first define the full constraint, and then build up my (informal) reasoning as to why I think it's convex. Hopefully the…
GrayLiterature
  • 2,309
  • 7
  • 27
13
votes
3 answers

How could we simplify solving the large scale MIPs without using any advanced methods like decompositions?

Many practical optimization models (specially MIPs) are NP-Hard and solving them need much time even with the modern solvers like CPLEX or GUROBI. One of the best way (but not easy) is using decomposition techniques (at least for mathematician :) ).…
A.Omidi
  • 8,832
  • 2
  • 13
  • 49
13
votes
3 answers

Allocating credit card points

I’m interested in the idea behind this in general, so I thought this would be the best place to post, though I have a practical and semi-urgent need of allocating the points on my credit card towards purchases. Each purchase I make can be paid for…
Dave
  • 233
  • 2
  • 9
13
votes
1 answer

Symmetry-breaking ILP constraints for square binary matrix

Setup I have a binary $N \times N$ matrix. The objective is to minimize the number of ones in the matrix, subject to various constraints. This leads to symmetries by rotating 90 degrees and/or mirroring (along the axis and diagonals). Here's an…
Simon
  • 1,132
  • 8
  • 16
13
votes
1 answer

How to formulate a problem to prove/disprove convexity?

Given a general non-linear problem: \begin{align}P:\qquad&\min_{x\in X} f(x)\\\text{s.t.}\qquad&g(x)\leq 0\end{align} where $f$ is a non-linear function, $g$ is a vector of non-linear constraints, and $X$ is a box-constrained domain, is there a way…
Nikos Kazazakis
  • 12,121
  • 17
  • 59
13
votes
1 answer

Representing an indicator function: binary variables and "indicator constraints"

I want to represent the indicator function: $$ \mathbb{1}_{(y=j)}$$ where $y$ is a non negative, integer variable. My attempt is as follows: define a binary variable: $$ z_j =\begin{cases} 1 \qquad\text{if $y=j$} \\ 0…
Libra
  • 937
  • 5
  • 14
13
votes
2 answers

Simulation optimisation: Monte carlo simulation, regression, optimise within regression model?

Can you help me identify if this technique has a standard name to help me explore the literature? Suppose I have a black-box stochastic simulation parameterised by $X=[x_1,...,x_p]$ with some single output measure $y$ and wish to minimize $E[y]$…
Brendan Hill
  • 636
  • 3
  • 11
13
votes
4 answers

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 of the (e.g.) MIP we are solving. I am looking…
Albert Schrotenboer
  • 1,859
  • 12
  • 27
13
votes
4 answers

Is there a SQL/English like language that lets you define formulations given some data?

It would be very useful for beginning and non technical users to be able to define models in a way that was natural for them. Further this could perhaps assist generating some kind of generic modelling language which could be used in…
fhk
  • 1,069
  • 6
  • 14
13
votes
4 answers

What global MINLP solvers support trigonometric functions?

What (deterministic) global optimization packages support trigonometric functions such as $\sin, \cos, \tan$ in the constraints or objective function? What limitations do they have? I am not asking about heuristic or metaheuristic algorithms.
Michael Feldmeier
  • 2,856
  • 14
  • 40
13
votes
7 answers

What are the examples (applications) of the MIPs in which the objective function has nonzero coefficients for only continuous variables?

I'm specifically looking for real applications of the following form of MIP: $$\max\,Cx$$ subject to: \begin{align}Ax +By &= D\\Ax &= E\\By &= F\\ x &\ge 0\\ y &\in \mathbb{Z}^{+}\end{align} Part of these constraints can be excluded. The…
Junior MIP
  • 400
  • 1
  • 10
13
votes
1 answer

In Local Search, which reheating techniques have a good track record?

Given a fast-stepping Local Search (such as Simulated Annealing or Late Acceptance), which reheating approach is proven to work well? Generally speaking, reheating works like this: if [a condition is met] then we [take action] to increase the chance…
Geoffrey De Smet
  • 4,851
  • 10
  • 34
13
votes
2 answers

Querying attributes of LP relaxation at MIP-optimality in Gurobi

Is there a way to configure Gurobi to allow the LP relaxation associated with the optimal solution leaf of a MIP branch-and-bound tree to be queried for shadow prices & other general LP properties--understanding that there may be serious…
Colin M
  • 133
  • 3
1 2 3
…
99 100