Questions tagged [modeling]

For questions related to the process of converting a real-world problem into a mathematical model. Can include questions related to linearization, logical constraints, tightness of formulations, and so on.

Filter by
Sorted by
Tagged with
33 votes
6 answers
2k views

How to determine the correct level of detail when modelling?

"All models are wrong, but some are useful" - George E. P. Box I usually work on what one could call operational problems. There I usually do not have too much trouble figuring out the level of ...
Renaud M.'s user avatar
  • 2,418
32 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,077
26 votes
1 answer
604 views

The rationale to improve MTZ?

Currently I need to solve a quite specific problem involving symmetric TSP as a sub-problem (i.e., a Hamiltonian cycle is a necessary condition for optimizing some problem-specific variables that ...
Omicron_Persei_11's user avatar
25 votes
5 answers
2k views

Examples of machine learning applied to operations research?

Can someone give me a few examples, if they exist, of problems in operations research that could be solved using machine learning. I am aware that machine learning examples are data-driven and do not ...
klaus's user avatar
  • 353
24 votes
4 answers
731 views

How to determine if a given problem seems to be a good fit to be solved using combinatorial Benders decomposition

Combinatorial Benders decomposition is a mathematical programming technique consisting into dividing a problem into a master problem and a sub problem. The master problem is solved to optimality (or ...
Renaud M.'s user avatar
  • 2,418
24 votes
3 answers
3k views

Combinatorial problem in my daughter’s class

In Denmark, a rather substantial amount of work and effort has gone into reducing bullying in the Danish public schools. Many initiatives, which purposes are to strengthen the unity and solidarity in ...
Sune's user avatar
  • 6,497
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,023
22 votes
5 answers
5k views

Validation and verification of mathematical models

Within the subject of simulation I have found some literature on validation and verification (e.g. Sargent's paper). My question is, what techniques do you use to validate and verify your mathematical ...
Djames's user avatar
  • 1,143
21 votes
5 answers
672 views

Tightness of an LP relaxation without using objective function

How can we measure the tightness of a linear programming relaxation for a mixed integer linear program without using the objective value? I would like to get a measure in terms of the feasible set and ...
Mertcan Yetkin's user avatar
18 votes
6 answers
2k views

Infeasibility in mathematical optimization models

Sometimes, when solving mathematical optimization models (especially MIPs), they may be infeasible. Is there any comprehensive method to deal with the infeasibility conditions? (especially in complex ...
A.Omidi's user avatar
  • 8,882
18 votes
2 answers
325 views

Mathematically creating the 'perfect' permutation for reservations in a hostel

I am working at a hostel which uses a reservation system for each room and the beds in the room (e.g. $14$ beds in one room, bed numbers $1-14$.) When we get bookings for multiple people, we assign ...
JRogers97's user avatar
  • 181
17 votes
5 answers
744 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
17 votes
3 answers
463 views

As an Operations Research professional, how is your time divided when working on an optimization project?

When working on an optimization project, what is the typical time division (in percentage) between the various tasks that you have to work on: Problem understanding/definition (figuring out what is ...
Renaud M.'s user avatar
  • 2,418
16 votes
3 answers
1k views

What is a "hard problem" in the context of Mixed-integer programming?

As a practical (real-world problems) point of view, it's important we could solve optimization problems as quickly as possible (for instance, to release a daily schedule). Maybe a problem with many ...
A.Omidi's user avatar
  • 8,882
16 votes
3 answers
1k views

Bin Packing with Relational Penalization

There are $ N $ bins with equal capacity $ C $. In addition, there are $ N $ objects $x_1, x_2, \dots, x_N $ that need to be accommodated using the least amount of bins. Each object $x_i$ has a volume ...
Duns's user avatar
  • 303
16 votes
4 answers
2k views

Best model for precedence constraints within scheduling problem

Suppose I'm modeling a problem where I want to compute the start time bucket for some jobs. All time buckets have equal duration. There are some additional constraints involved but I also have to ...
JakobS's user avatar
  • 2,757
15 votes
3 answers
14k views

Soft constraints and hard constraints

The terms "soft constraints" and "hard constraints" are used in the context of optimization modeling. Is there any standard way to figure out which is which in some of the complicated models?
A.Omidi's user avatar
  • 8,882
15 votes
2 answers
1k views

Column generation for TSP

For teaching purposes, I would like to solve the Travelling Salesman Problem with a column generation approach. In the academic literature, an approach is proposed (for example here), where columns ...
Kuifje's user avatar
  • 13.3k
14 votes
2 answers
1k views

How to choose between high number of binary variables or fewer number of integer (not only 0 and 1) variables in a IP formulation?

When I have to write the formulation of an IP, I usually have the choice between writing $i\times j$ binary variables with two indices such as $ x_{i,j} $ or, writing $j$ integer variables $x_i$. Is ...
JonathanZ's user avatar
  • 151
14 votes
1 answer
1k views

Comparison of Algebraic modelling languages and general programming languages

Some optimization software/frameworks (commercial or open-source) such as AMPL, GAMS, Cplex, ... have a specific Algebraic modelling language. Some of them have another type of programming that uses ...
A.Omidi's user avatar
  • 8,882
13 votes
6 answers
1k views

Where can I find documentation on good practices for efficient formulations of a problem?

I am sort of new to mathematical optimization and have to build some fairly complicated models for my thesis. I was wondering where I could find literature to help me develop more efficient versions ...
J. Dionisio's user avatar
13 votes
4 answers
2k views

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 ...
fhk's user avatar
  • 1,069
13 votes
6 answers
261 views

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 ...
LarrySnyder610's user avatar
13 votes
3 answers
1k views

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 ...
A.Omidi's user avatar
  • 8,882
13 votes
5 answers
516 views

Connectivity of two nodes in an arbitrary undirected graph

Is there an efficient way to model the connectivity of two nodes in an arbitrary undirected graph? I would like to have a binary variable representing this connectivity: 1 if there exists a path ...
Mertcan Yetkin's user avatar
13 votes
3 answers
771 views

On using correct notation in research papers

This question is about using correct notation while writing a research paper. Say I have a directed graph $G$, partitioned into $T$ layers. Denote the set of nodes in layer $t$ by $V_t$. Suppose, I ...
batwing's user avatar
  • 1,468
13 votes
1 answer
891 views

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\...
Libra's user avatar
  • 937
13 votes
1 answer
269 views

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 ...
Simon's user avatar
  • 1,132
12 votes
5 answers
2k views

Dividing machines into groups of equal sizes so that each group has approximately same productivity

I have set of machines with varying productivity. I want put the machines in different groups so that the groups have approximately equal productivity. Lets say, we have $M$ machines. and we want to ...
KGM's user avatar
  • 2,265
12 votes
2 answers
3k 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
12 votes
3 answers
509 views

How to handle real-world (soft) constraints in an optimization problem?

Cross-posted at Stats.SE (aka Cross Validated) I am working on a problem which involves optimizing for minimum power consumption in a large compressor network interconnected through pipelines (think ...
chupa_kabra's user avatar
  • 1,485
12 votes
2 answers
635 views

Expressing a chain of boolean ORs using ILP

How to express a chain of OR operations in an ILP in which each expression is a less than or equal constraint and the left hand side variable in all inequalities is always the same? All the variables ...
ephemeral's user avatar
  • 897
12 votes
3 answers
1k views

Number of aircraft to operate in an airline company

Suppose that an airline company has X planes, in general the companies keep a number of these aircraft (say 80% of X) in reserve in case of hazards. My question is how the airline companies compute ...
user109284's user avatar
12 votes
1 answer
553 views

How to linearize membership in a finite set

Given finite set $S$ and variable $x$, how do I linearize the set membership constraint $x\in S$?
RobPratt's user avatar
  • 32k
12 votes
1 answer
3k views

An approximate answer to the right question or an exact answer to the wrong question

There is a quote from John Tukey in one of his papers on data analysis Far better an approximate answer to the right question, which is often vague, than an exact answer to the wrong question, ...
user2974951's user avatar
12 votes
2 answers
693 views

Debugging cplex model

I implemented a cplex model and I am convinced that the model should allow a better solution on a specific instance. However, when I impose the variable values of the solution onto the model, it ...
PSLP's user avatar
  • 2,401
12 votes
2 answers
638 views

Expressing an implication as ILP where each implication term comprises a chain of boolean ORs

Consider an implication of the form $A \implies B$ where both $A, B$ comprises a chain of Boolean OR variables. For example, $(a_1 \lor a_2 \lor a_3) \implies (b_1 \lor b_2 \lor b_3)$. How can this ...
ephemeral's user avatar
  • 897
12 votes
2 answers
477 views

Is there a way to proportionalize fixed costs in a MILP?

So assume we have a MILP (e.g. inventory or capacity planning) and the objective is to minimize total costs (inventory costs, set-up costs, backorder costs, production costs etc.). The production of a ...
Paroth's user avatar
  • 343
12 votes
1 answer
1k views

How do we call this problem in literature and how to model it?

I have a set of sources and a set of sinks. Each source $s$ can produce a set of different products $P_s$. The transportation inter-sources and inter-sinks are allowed. The sources do not ...
Antarctica's user avatar
  • 2,917
12 votes
2 answers
166 views

Pricing of blends/mixtures across multiple timesteps

I have a simple blending problem, where each final product is a blend or mixture of several raw materials, and want to calculate the price per unit of weight for each of the products. So for a given ...
TimChippingtonDerrick's user avatar
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,418
11 votes
5 answers
2k views

How to compute all paths between two given nodes in a network?

In this post, Erwin Kalvelagen describes a method to compute all paths between two nodes in a given network, such that: no arc is used more than once a given path does not contain more than $M$ arcs ...
Kuifje's user avatar
  • 13.3k
11 votes
4 answers
941 views

How to linearize a constraint with a maximum of binary variables times some coefficient in the right-hand-side

I have the following constraint that I'd like to linearize: $P$ is a given set $b_p \in \{0,1\} , \forall p \in P$ a binary variable associated with each element of $P$ $c_p \in \mathbb{R}^+$, a ...
Renaud M.'s user avatar
  • 2,418
11 votes
2 answers
1k views

Linear programming: objective function with "buckets"

I had a linear programming problem with the following objective function $$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$ Where $q, p, C, c$ are known. This problem was ...
BarkingCat's user avatar
11 votes
3 answers
865 views

Modeling the Choose function

In statistics, one often encounters the choose function ${x \choose y}$ which encodes the number of ways of choosing $y$ items from a set of $x$ items. How would one go about modeling a choose ...
Josh Allen's user avatar
11 votes
1 answer
623 views

I've formulated my optimization model; now what?

I've formulated my linear/nonlinear/integer/mixed-integer optimization problem in algebraic form (possibly with the help of the folks on this site). Now what? How do I solve it?
LarrySnyder610's user avatar
11 votes
1 answer
497 views

Expressing a chain of boolean ORs using ILP involving different variables

How can I express a chain of OR operations in an ILP, given that each operand is an inequality between two binary variables? I have asked a similar question here: Chain of Boolean ORs. In that ...
ephemeral's user avatar
  • 897
11 votes
2 answers
286 views

partitioning hub assignment models

When solving large-scale hub assignment models (1000+ candidate hubs and 1000+ demand nodes), it is possible that parts of a cost matrix are not connected to one another. A typical workflow would be: ...
fhk's user avatar
  • 1,069
11 votes
1 answer
357 views

Minimize number of pieces required to cover distances, with overlap

The specific optimization problem I'm trying to solve is this: Find the minimum integer number of $2$m pieces required to cover $2$ or $4$ distances of length $D$ given that adjacent pieces must have ...
Martin Stålberg's user avatar
11 votes
2 answers
2k views

Valid Inequalities and Strong Inequalities

Consider the following mixed-integer set: \begin{equation} P(A, b ; S) \stackrel{\text { def }}{=}\left\{x \in \mathbb{R}^{n} : A x \leq b, x_{j} \in \mathbb{Z} \text { for } j \in S\right\} \end{...
A.Omidi's user avatar
  • 8,882

1
2 3 4 5
12