# Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

63 questions
Filter by
Sorted by
Tagged with
7k 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 ...
6k views

### How to linearize the product of two binary variables?

Suppose we have two binary variables $x$ and $y$. How can we linearize the product $xy$?
1k views

### What are good reference books for introduction to operations research?

The reference books should cover the wide range of problem-solving techniques and methods.
4k views

### How to linearize the product of a binary and a non-negative continuous variable?

Suppose we have a binary variable $x$ and a non-negative continuous variable $y$. How can we linearize the product $x y$?
2k 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 ...
1k 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.
4k views

### How does a warm start work in LP/MIP?

Can someone explain how warm starts/ MIP starts work? How do solvers like CPLEX/GUROBI use warm start with the Simplex algorithm? I am interested in understanding how the entire warm start ...
436 views

### Linear and Integer programming materials

I was wondering if you could refer me to some online video/text resources to learn linear and integer programming. I am intending to work in the field of data science. I greatly appreciate your kind ...
1k views

### Where can I find open source LP solvers?

I'm familiar with COIN-OR and have also used a couple packages in R to solve LPs. Today I found out Google has their own open source optimization software, and it got me wondering what other open ...
1k views

### State-of-the-art algorithms for solving linear programs

Průša and Werner (2019) show that the general linear programming problem reduces in nearly linear time to the LP relaxations of many classical NP-hard problems (assuming sparse encoding of instances)....
3k views

### Linear Programming with additional "if-then"/"Default to zero" constraints?

What approaches can I use for a Linear Programming problem with the additional constraint that if a decision variable falls below a certain threshold, then it should just be forced to 0. I'm ...
3k views

### How to linearize the product of two continuous variables?

Suppose we have two variables $x, y \in \mathbb R$. How can we linearize the product $xy$? If this cannot be done exactly, is there a way to get an approximate result?
443 views

### How to linearize a constraint with a maximum or minimum in the right-hand-side?

Suppose we have three variables, $x, y, z \in \mathbb R$. How can we linearize constraints with the following structure? $$z \geq \min(x, y)$$ $$z \leq \max(x, y)$$
2k views

### Linearize or approximate a square root constraint

I encounter a nonlinear constraint that contains the square root of a sum of integer variables. Of course one could use nonlinear solvers and techniques; but I like linear programming. Are there any ...
675 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 optimal solutions, and your solver of choice: For what theoretical and/or practical (...
3k views

### Find feasible point in polynomial time in linear programming

Background A while ago my team was implementing an interior point LP solver and we came across the following conundrum: Is there a polynomial-time algorithm to find a feasible starting point in ...
3k views

### How to evaluate the performance of open source solver?

I am looking for a reliable open source solver to solve LP and MILP (with a few thousand variables). How can I evaluate the performance of a given solver for a particular use case?
736 views

### Linear optimization problem with user-defined cost function

I have a linear optimization problem for which I am looking for a suitable optimization solution that can fulfill my requirements. Here is an explanation of the optimization problem: There are a ...
584 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 ...
1k views

### Is there a heuristic approach to the MILP problem?

I have the following optimization problem which is a MILP. I can solve it with a MILP solver. \begin{align}\min_t&\quad t\\\text{s.t.}&\quad d_{c}-t\le \sum_{n=1}^{N} B_{n,c}x_{n}\le d_{c}+t,...
162 views

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 $... 2answers 327 views ### If-then constraint with continuous variables I was usually using if-then constraints with integer variables but ended up using continuous variables and got confused. I have variables$x_{ij}\in\mathbb{R}_{\geq 0}$, and would like to force the ... 4answers 2k views ### "Best practices" for formulating MIPs Often there are many alternatives ways for formulating a MIP. For example: The model contains inequality constraints that must hold with equality in an optimal solution. The model contains ... 4answers 940 views ### How can I remember the rules for taking the dual of a linear program (LP)? When taking the dual of a linear program (LP), is there a trick/easy way to remember the rules for the directions of the inequalities, signs of the variables, etc.? A trick with a catchy name, perhaps?... 1answer 1k 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? 2answers 586 views ### Generating all extreme rays I am trying to understand a problem and would like to generate all extreme rays for a given set of linear constraints. With the Python interface of CPLEX, I was able to generate a single ray (not sure ... 2answers 386 views ### Simplex-Implementations in professional Solvers Which non-textbook variants (primal/dual, revised) and techniques (e.g. steepest-edge) do professional solvers like Xpress, CPLEX, CLP use, to get the best out of the simplex algorithm? This ... 2answers 495 views ### Where can I find resources to learn mathematical modelling for real life operation research problems like combinatorial optimization? I find it hard to form math models for real life operations research problems, how can I learn this? Any books, tutorials available? 3answers 1k views ### TSP with revenue maximization How to approach a travelling salesman problem with an aim to maximize revenue at each town visited in a certain number of days (total number of towns is greater than what can be visited in the given ... 2answers 422 views ### Black-box optimization with linear programming? In my research, I do a black-box optimization based on a simulation model with nonlinear properties. The simulation model gets an operation plan for a time period and then returns a time series, which ... 2answers 485 views ### Application of complex numbers in Linear Programming? The theory surrounding Linear Programming is based on variables, bounds and coefficients that take on values in$\mathbb R$, the set of real numbers. I have long wondered whether there might be ... 2answers 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, care known. This problem was ... 3answers 3k views ### Google - OR tools for workforce scheduling problems Has anyone used the google OR tools in python to solve the workforce scheduling problem. Can you please let me know Advantages and Disadvantages Any issues faced during usage and implementation 3answers 395 views ### LP dependent on the ordering of the data This is a rather simple question. Can a solution to a linear programming problem be dependent on the order in which the data is read/presented/stored? I know, that the time it takes to solve the ... 1answer 810 views ### How to linearize the multiplication of an integer and a binary integer variable? I have the following constraints \begin{align}\sum_{i=1}^{N}{x_it_i}&= M\\\sum_{i=1}^{N}{t_i}&\le S\end{align} wherex_i\ge 0$is an integer variable,$t_i\in\{0,1\}$is a binary variable ... 2answers 174 views ### Asymmetric time-constrained capacitated vehicle routing problem I am trying to add some more constraints to the flow-based ADVRP model in Almoustafa et al. (2013)1 (pp.4). The mentioned model caps the travel distance, while I cap the travel time. Let$U$represent ... 1answer 314 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 ... 1answer 175 views ### Pulp Python: How to formulate a time-based variable for shipping demurrage I am working on a shipping optimisation problem that aims to minimise demurrage charges as a result of low/insufficient inventory. I have daily vessel requirement (sales) data in the format ... 5answers 343 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 ... 2answers 276 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 ... 4answers 319 views ### Does this$0-1$integer program have any speciality? Given matrix$A \in \{0,1\}^{m \times n}$and vector$b \in (\mathbb{Z^+})^m$, where$\mathbb{Z^+}$is the set of positive integers, $$\begin{array}{ll} \text{maximize} & c^\top x\\ \text{subject ... 2answers 687 views ### Can presolve reductions change the value of the linear programming relaxation? For integer programs solvers (like Gurobi, Cplex, ...) report the value of the linear programming relaxation for integer programs, i.e. ... 3answers 2k views ### How to find all vertices of a polyhedron I have a convex polyhedron given by a set of linear inequalities, for example:$$ x_1 \geq 0,~~ x_2 \geq 0, ~~x_3\geq 0 \\ x_1+x_2\leq 1,~~ x_2+x_3\leq 1,~~ x_3+x_1\leq 1$$I want to list all the ... 2answers 137 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$... 2answers 2k views ### Complexity of LP and MILP Problems? My original problem is an MILP. I make it an LP by relaxing the integer variables. Can someone please comment on the complexity, solvability and optimality of MILP and LP problems, in general? Is ... 1answer 743 views ### Why is the Ellipsoid Method of polynomial complexity? We know that the ellipsoid method is proven to be of polynomial complexity. However, as far as I can tell we may need to add exponentially many feasibility cuts in order to solve the LP (or prove no ... 3answers 189 views ### Reducing number of suppliers for product portfolio I have the following matrix of suppliers who are able to make a certain product, against all products in my portfolio. What is the best way of finding the solution to "the least suppliers necessary ... 2answers 251 views ### Formulation of a constraint in a MIP for an element in different Sets I have an element e$\in E$with$E$the set containing all elements e and$e \in Y_i$with$Y_i \subseteq E$. Each set$Y_i$has different attributes.$G_j$is a set of sets and the following holds:$...
I am trying to linearize the constraint set (2) in the following simplified program. The parameters: $A,C,D,T\in\mathbb{R}^+$. The set $\mathcal{J}$ is polynomially-sized. \begin{alignat}2\min &\...