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
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
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
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
7 votes
1 answer
443 views

How can I strengthen a family of constraints in the presence of a clique constraint?

Suppose $x_i$ are binary variables, $y_j$ are arbitrary variables, $a_j$ and $b$ are constants, and I have the following linear constraints: \begin{align} x_i + \sum_j a_j y_j &\le b &&\...
RobPratt's user avatar
  • 32k
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
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
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
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
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
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
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
7 votes
1 answer
644 views

How to construct my mixed integer programming problem with constraint of minimum consecutive ones

My target is to formulate a binary sequence with fixed size $N$ = 10, such as $[1, 0, 0, 0 ,1, 1, 0, 1, 0, 0]$. However, I want to constrain this sequence so that when 1 appears, it has to appear at ...
shaojie liu's user avatar
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
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
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
8 votes
5 answers
3k views

Algorithms vs LP or MIP

Is there a way of writing an algorithm with if-, while-statements to find an optimal solution without using linear-programming (LP)/MIP? If so, what would the benefits be against the LP/MIP? Is it ...
Georgios's user avatar
  • 1,193
6 votes
1 answer
222 views

TSP subtour elimination by assigning distance traveled

Given a set $S$ which we need to travel following TSP rules. I was wondering if this sub tour elimination method is good enough or not? Let $b_{i,j}$ denote edge from $i$ to $j$ is taken or not and $...
ooo's user avatar
  • 1,589
5 votes
1 answer
250 views

How to set a limit for a switch to 0 of a variable

I would like to know how to define a constraint to set a limit for switching to 0 for a decision variable? So I have a linear variable $x(t)$ which quantifies the modulation degree of a heating device....
PeterBe's user avatar
  • 1,642
1 vote
2 answers
424 views

How to create A, b and c matrices from very large .lp file?

I am working on Scaling MIP. I use Gurobi within Clion. I need to extract the coefficient of Xs (A matrix), right-hand side (B matrix), and an objective function(c matrix) from the .lp file and ...
asdf's user avatar
  • 105
1 vote
2 answers
611 views

How to make the elements of the solution of gurobi belong to the elements of the specified list?

If I want to use the elements of the list as the range of the solution, like list1 = [10,20,50,60,30],and the elements of the solution must belong to the elements of the list The sample example as ...
Zying's user avatar
  • 57
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
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
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
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
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
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
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
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
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
10 votes
2 answers
192 views

Optimal set order to maximize stochastic reward

You have a ticket allowing you to visit up to $n$ of $M$ carnival booths offering games of chance. At each booth you have probability $p_{i}$ of winning a reward with average value $r_{i}$. Each booth ...
sedge's user avatar
  • 103
8 votes
2 answers
1k views

OR-TOOLS : delivery node with multiple possible pickup nodes

I am using ortools to model a VRP with pickup and delivery constraints, where pickups can be done at different nodes. For example, if node A has a demand, it must be picked at node B or C. Here is how ...
Kuifje's user avatar
  • 13.3k
8 votes
1 answer
671 views

Guides for strong MILP Formulations

When developing MILPs, often there are different alternatives possible to express a constraint. The question then arises, which of the alternatives is better, meaning, which alternative is expected to ...
Clement's user avatar
  • 2,252
8 votes
2 answers
171 views

Bounding arrival time at a node in a resource-constrained shortest path problem

Given a city map (a graph) $G$, $b_{i,j}$ is a Boolean variable for whether or not edge $i$,$j$ is allocated, $d_{i,j}$ denotes the distance between $i$,$j$. The objective is to move from $s$ to $e$ ...
ooo's user avatar
  • 1,589
7 votes
2 answers
320 views

Traffic lights optimization

I am interested in the following problem dealing with the optimization of traffic lights on the intersection illustrated below: The goal is maximize the duration during which each movement $m\in M=\{...
Kuifje's user avatar
  • 13.3k
7 votes
3 answers
2k views

Solving Logic puzzles through optimization

I have the following "logic puzzle" (I think this is considered as a "scheduling problem"): In this problem, there are 5 basketball players - provided some clues about their ...
stats_noob's user avatar
  • 1,831
7 votes
2 answers
1k views

Finding an Objective Function for Assigning Employees to Sequence Dates

I am using a mixed-integer-program to schedule employees to projects. These projects can have a time window to get completed from a few weeks to a few months. At the moment I am working in a ...
Georgios's user avatar
  • 1,193
7 votes
2 answers
402 views

Can QUBO solve this inverse Ising problem?

Inverse Ising Problem The inverse ising problem means fitting the coupling $J_{ij}$ and field $h_{i}$ parameters given a sample of configurations of spins. Each spin $s_{i}$ is either +1 or -1. The ...
Qurious Cube's user avatar
6 votes
2 answers
249 views

Good sources on developing mathematical models [closed]

What are good sources (literature, internet, etc) on learning to model real-world problems using mathematical formulations? In particular, I would like to know sources which establish the relationship ...
decision maker's user avatar
6 votes
1 answer
404 views

How to solve this linear program with an exponential number of constraints?

Consider the following convex program: \begin{align*} \min g(x) && \text{such that} \\ f_i(x) &\geq b_1 && \text{ for } i \in 1,\ldots,n; \\ f_i(x)+f_j(x) &\geq b_1+b_2 &&...
Erel Segal-Halevi's user avatar
6 votes
1 answer
381 views

Optimize for bonuses within a group (knapsack)

I am trying to create an LP problem which is like the knapsack problem but with groups of items. Let's say there are 10 groups of items each with up to 5 items. Each group has one special item and you ...
Eddie's user avatar
  • 197
6 votes
3 answers
468 views

How do we formulate a problem where the decision variable has an index that is also a decision variable?

I want to maximize the sum of a nonlinear function $f(.)$ w.r.t. $x$ that is convex in $x$: $$\max \sum_{i=1}^N f(x_i), $$where $x_i$ is a continuous variable and $0 \le x_i < 1$ for $i = 1, 2, \...
Steven01123581321's user avatar
5 votes
2 answers
410 views

Binary variable constraint

The task is to ensure that if $x_i = 1$ for at least $k$ of the possible indices $i$ in $\{1,...,n\}$ then $y = 1$, where $k$ and $n$ are parameters, $x$ is a binary variable vector with $n$ elements, ...
Bohdana Nevierova's user avatar
5 votes
3 answers
3k views

How to represent an integer variable via binary variables?

Suppose we have a model with $N$ integer variables, i.e. $x \in \mathbb{Z}^{N}$ with $L \leq x \leq U$. How can we represent the integer variables via binary variables? Or in other words: how can we ...
Ronaldinho's user avatar
5 votes
2 answers
548 views

How to model If $A \le B$ then $Y = 1$, otherwise $Y = 0$

Somehow I don't get it right. I would like to model the following conditional: If $A\le B$ then $Y=1$ otherwise $Y=0$ where $A, B$ are reals and $Y$ is binary. I can model as follows: $Y \cdot A \le B$...
Clement's user avatar
  • 2,252
4 votes
1 answer
295 views

How to transform a (thermal) range constraint into the objective function

I have an mixed-integer linear optimization problem that includes a energetic difference equation for the temperature of a building for the time $t$: $$T(t) = T(t-1) + \frac{E^{\rm Heating}(t)-E^{\rm ...
PeterBe's user avatar
  • 1,642
4 votes
0 answers
121 views

Modeling question on continuous variable that dependens on binary variables

Given a model with a binary variable $b_s$ that describes whether taking an item $s$ from a set $S$ or not. Consider that some other constraint in the model depends upon whether all items of the set ...
Andreas's user avatar
  • 313
4 votes
1 answer
475 views

Minimum up time for a machine in a linear program?

If we let $x_i$ = 1 if a machine is on during hour $i$, and 0 if the machine is off, how would we enforce a constraint that requires the machine to be “on” for a minimum of at least $M$ hours? For ...
Mason's user avatar
  • 515
4 votes
1 answer
388 views

How to partition a graph with optimal number of groups?

I have a graph with $N=12$ nodes. Some nodes may not have any edge between them. every edge has a weight. How to find the optimal partitioning of the graph so that total weight in the system is ...
KGM's user avatar
  • 2,265