# Questions tagged [linear-programming]

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

354 questions
Filter by
Sorted by
Tagged with
I have a problem as: \begin{align} \begin{array}{cl} \underset{x \in \mathbb{R}^n_+}{\min} & c^\top x \\ \mathrm{s.t.} & Ax \leq \mathbf{1} \cdot b , \end{array} \end{align} where $A \in ... 2answers 42 views ### Write in ILP: If$x$within range then$s=1$, else$0$How can write the following function in LP: $$s= \begin{cases} 1 & 1 \leq x \leq C \\ 0 & \text{otherwise} \end{cases}$$ where$x$takes only non-negative integers and$Cis some large ... 1answer 98 views ### Benders decompositions: Number of iterations does not remain the same I am solving an LP (i.e 118-bus system economic dispatch for 130% loading) using Benders decomposition. The problem takes 26 iterations to converge. This means that the process adds 25 cuts to the ... 0answers 66 views ### Optimisation Multiple Constraints I am trying to solve a linear algebra problem: an optimisation problem and I am using CVXOPT. I've split the problem into 3 components In its simplest form, The general formulation for CVXOPT is \... 1answer 174 views ### Are decomposition methods applicable on large linear programs? Working on a very large Linear Program, we tried out some primitive implementations of decomposition techniques such as Lagrangian relaxation and column generation. However, none of these were able to ... 2answers 153 views ### Are there small LPs out there? A fair share of academic research and software development focuses on solving ever-larger problems, particularly when it comes to LPs. I am however curious to know in what contexts and to what extent ... 1answer 82 views ### Linearly independent rows in simplex I'm having some trouble understanding about the independent rows in a basic solution. In the book Introduction to linear optimization by B&T, the authors give the definition of a basic solution as ... 1answer 93 views ### Upper and lower bounds of a variable equal I'm working on a MILP (Mixed-Integer Linear Programming) problem with the Java API of Cplex. In order to easily exclude some variables from my problem I thought about setting both their lower and ... 1answer 65 views ### Examples of LP problems in irrigate engineering I need examples of linear programming problems applied to irrigation system. My idea is to give students many examples of LP applications in the irrigation engineering. 0answers 74 views ### Minimax problem with a large high dimensional feasible region How to solve minimax mixed integer problem with a large high dimensional feasible region? \begin{aligned} \max_{\vec{x}}\min_{\vec{y}} \quad & \vec{r} \cdot \vec{x} + \vec{s} \cdot \vec{y}\\ \... 1answer 87 views ### KKT conditions analysis for binary constraints I am wondering if boolean constraints in a linear program can be solved (after linear relaxation fromx\in\{0,1\}$to both$x\ge0$and$x\le1$) using KKT analysis. Most of the algorithms that I have ... 1answer 114 views ### Linear Relaxation of Boolean Constraint for Solving Integer Linear Program Using KKT I am trying to convert a boolean LP to LP using LP relaxation by converting$x \in {0,1}$to both$x \ge 0$and$x \le 1. Then to use it in my problem analysis, I am trying to build the KKT ... 1answer 276 views ### Model “if and only if” indicator constraints in Linear programming Apologies if this question has been asked, but I haven't been able to find it. I'm modelling something with Gurobi and want to do the following: \begin{align}\text{cond} < \dfrac{1}{3} &\iff x =... 1answer 228 views ### CPLEX log always the same after hours (“Gap” and “Best Integer” always blanks) I'm using the Java API of CPLEX 12.6.1 (with license) to solve a MILP (Mixed-Integer Linear Programming) maximization problem. The point is that, after 21 hours, CPLEX has consumed 32 GB of RAM and ... 1answer 73 views ### Need help with an appointment scheduling problem I am currently stuck on writing a linear programming model to describe the process of appointment scheduling for an Oncological Center. I wanted to share it with you guys and see if anyone here could ... 1answer 48 views ### Employee allocation based on ranking: Mathematical Model Suppose I have three employees and I have to assign three employees based on their ranks. If an employee has rank 1 that means he is best. Say, I have the following table ... 0answers 191 views ### Simplified risk game: writing a pratical Minimax objective for mixed integer programming Problem To ensure fairness of the game, I am writing a bot that plays against itself. I have trouble rewriting a minimax objective to a practical maximization in mixed integer programming. The amount ... 1answer 71 views ### MODM to create balanced groups of students to maximise diversity I am very new to LP, Goal Seek, Decision Models etc and I have a multiple-objective decision making problem that may or may not require a mix of techniques although I am trying to solve it purely ... 1answer 76 views ### An efficient Integer programming model for the minimum spanning tree problem? LetT=(V, E')$be a spanning tree of a graph$G=(V, E)$. Rather than verifying for any subset of vertices$S\subseteq V$that$|E'(S)|=|S|-1, is there an efficient way to satisfy the spanning tree ... 1answer 114 views ### Best way to add dummy to transportation problem? Zero cost will be always chosen first? I know that an unbalanced transportation problem could be made a balanced transportation problem by adding a dummy node which equals the difference between demand and supply. In literature, dummy ... 1answer 240 views ### What is a good way to penalise LP relaxation? I have a binary integer program. It is of a large size and the solver is taking longer time. I am thinking of relaxing the binary integer variable and making it a continuous variable. How can I ... 0answers 52 views ### How is the dual revised simplex method equivalent to running the RSM on the dual problem? I've seen the claim (in the title) several places, but can't quite understand why it's true. From what I understand so far, the revised simplex method solves an LP in standard computational form, $$\... 2answers 91 views ### Transformations that leave the linear program unchanged A typical linear program is written as$$L_0:\min_{x \geq 0; A^\top x \leq b}c^\top x.Here, x \in \mathbb{R}^n, c \in \mathbb{R}^n, A \in \mathbb{R}^{m \times n}, and b \in \mathbb{R}^m. ... 1answer 85 views ### Objective function with exponential coefficients I have a linear programming problem, with n variables and a\leq x_{i} \leq b for each variable x_{i}, where the objective function is \min \sum\limits_{i=1}^{n}{2^{i} x_{i}} Is it true that, ... 1answer 612 views ### Linear Optimization Library for C++ with GPU Support Does anyone know any linear optimization libraries for C++ supporting GPUs for parallelization? If multiple, which do you recommend? The GPU support is important to me since I am dealing with large ... 1answer 95 views ### Multiple If else constraints in Mixed integer programming How to formulate the following as constraints in MILP? a = y, if x= 0, a = 0, if x != 0, . . . . a[i][j] = b[i][j-1] + y, if x[j]=i, a[i][j] = a[i][j-1], if x[j] != i, ... . . . b... 0answers 46 views ### Specializing Iterations of Dantzig-Wolfe Decomposition with an Oracle This arises from an engineering problem I am working on. Let \mathbf{c}_i,\mathbf{a}_i\in \mathbb{R}^{d} be a given set (collection) of vectors where i\in\{1,\dots,n\}. Define the bounded ... 2answers 159 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 113 views ### Extreme points of a simple polyhedron Consider the polyhedron given by the set of inequalities \begin{align} \mathbf{b}^T\mathbf{x} ~&\leq~ c \\ \mathbf{e}^T\mathbf{x} - 1 ~&\leq~0 \\ \mathbf{x}~&\geq~0 \end{align} where \... 2answers 143 views ### Any Solution for k-means with minimum and maximum cluster size constraint? I am looking for an efficient approach to k-means clustering with minimum cluster size constraints. The clusters are non overlapping, so, one point can belong to only one cluster. N be the number ... 1answer 66 views ### How to linearize inequalities having max or min? I'm modeling an LP problem in which I have to maximize an objective function. Two of the constraints are the following, where k_i are constants and x_i decision variables (continuous). Could ... 4answers 430 views ### How to visit a subset of network nodes in a single trip? I have a connected network where I want to visit a set of destinations which may require visiting intermediate nodes as well because there may be no direct edge between source and destination nodes. I ... 2answers 95 views ### How to deal with a decision variable in the objective function that depends on if-else conditions involving other decision variables? I'm modeling an optimization problem in which a decision variable x_1 in the objective function depends on if-else conditions involving decision variables x_2 and x_3, as the following equation, ... 1answer 311 views ### Is there any automatic way to spot contradictory constraints in linear programming? Let's have the following trivial linear program: \begin{align}\max&\quad z=20A+30B\\\text{s.t.}&\quad A\le60\\&\quad B\le50\\&\quad A+2B\ge220\\&\quad A,B\ge0\end{align} It's easy ... 1answer 60 views ### Name for subclass of ILP without any inequality constraints (including constraints on x) In "Myths and Counterexamples of Mathematical Programming" myth "IP Myth 21" says: The problem of finding x\in \mathbb{Z} such that Ax=b, where A\in\mathbb{Z}^{m\times n} ... 0answers 64 views ### LP instead of IP formulation of assignment problem In the example files of GLPK, the assignment problem is written as a linear program. I don't understand why this isn't an integer programming problem. The problem formulation: ... 3answers 108 views ### warmstarting simplex algorithm- how much can problems differ from each other? I'm working on an implementation of the simplex algorithm. I want to solve problems in real time every 30 minutes. They could be interpreted as a classic transportation problem. I couldn't really say ... 1answer 137 views ### How to linearize the product of a binary and a continuous variable? [duplicate] Suppose we have a binary variable b \in \{0, 1\} and a continuous (possibly negative) variable y \in \mathbb{R}. How can we linearize the product b \cdot y? 2answers 156 views ### Scheduling optimisation constraint on consecutive shifts & consecutive night shifts (python) I am trying to write a program to schedule a team of 8 individuals into shifts. I want to know how to model that every individual must get at least one night shift break, and must not work two ... 3answers 122 views ### Linearizing a Max Function in the constraint - not working I have a minimization function which is in its simplest form looks like below. I am including the index of the variables. ... 1answer 256 views ### How to mathematically formulate the optimization problem? I have a system with S service points. There are also U users in the system. We haveU>S>G$One group can have maximum$M$service points, but there is no restrictions on the number of ... 1answer 90 views ### Mixed Integer Programming - How to model the dependency of two variables in an objective function I have two variables$a$and$b$, in which$a$is the amount of goods and$b$is the amount of boxes of the given sizes. So$b$(box size + number) is dependent on a (goods quantity). If$a$is ... 0answers 76 views ### How to linearize a max min objective function? Let us suppose that I have a$\max \min$objective function that only depends on one set of variables:$\underset{x}\max \underset{y}\min dy$Associated with the linear set of constraints and right ... 1answer 78 views ### Job Shop Scheduling Problem: jobs are scheduled on the same machine at the same time I want to solve a job shop scheduling problem. I got$n$Jobs that have to be scheduled on$k$Machines. A Job$i$has 2 or 3 Tasks$j$, and there is a known sequence of the Tasks of a Job. One ... 0answers 104 views ### 0 1 solution of linear programming problem with only equality constraints I have a linear programming problem$LP$where all the variables$x_{i}$take value in$\left[0, 1\right]$(that is$0\leq x_{i} \leq 1$). All the constraints are as follow:$a_{1}+a_{2}+a_{3}=1$that ... 0answers 37 views ### linear equation with conditions in Java I have the following problem: I want to determine a linear equation for a data table with$x$and$y$value. Point 1 should be the point where the first time$y > 0$and point 2 should be the point ... 1answer 93 views ### complexity order of the interior point method I was wondering why the complexity order of the interior point method is O()^3 or O()^3.5? Much appreciate your time and consideration. 1answer 79 views ### How to linearise this nonlinear constraint? I have a constraint in the form$\sum_{n=1}^{N}x_{m,n}\omega_{m,n}\ge (t_u-1)\beta_u, \forall u, u=1,2,\cdots, U$where$x_{m,n}$is binary variable$t_u$and$\beta_u$are continuous optimization ... 1answer 104 views ### How to transform this problem with logarithmic objective function into an approximated convex optimization problem? I have an objective function as follows$\underset{x_{m,n}}{\max}\hspace{1mm}\hspace{1mm}\sum_{m=1}^{M}\log_2\left(\frac{\sum_{n=1}^{N}(1-x_{m,n})\omega_{m,n}+z}{\sum_{n=1}^{N}x_{m,n}\omega_{m,n}}\...
How can I create a linear equation in Gurobi (Java) from values (x-y value pairs) that also has the following properties: $\forall x \leq 0 \Longrightarrow y = 0$ The linear line/equation should have ...