Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
152 views

Range limits on terms in the objective function of an LP

I have a linear maximization problem with an objective as follows: $$\sum c_i\cdot\text{exp}_i$$ where $c_i$ are constants (positive or negative) and $\text{exp}_i$ are linear expressions of the free ...
-1
votes
0answers
76 views

How to solve this linear programming minimization problem with the BigM method

Given this minimization problem: $$z=100x_1+77x_2+80x_3\\10x_1+7x_2+2x_3 \geq 12\\2x_1+3x_2+4x_3 \geq 3\\x_1+2x_2+x_3 \geq 1\\x_1,x_2,x_3 \geq 0$$ After adding artificial variables: $$z-100x_1-77x_2-...
5
votes
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 ...
1
vote
1answer
57 views

Check if there exists a vector that satisfies a set of inequalities but violates another set of inequalities

Problem Given rectangular matrices $A$, $B$ and vectors $\vec{a}$, $\vec{b}$, how to check if there exists an $\vec{x}$ that satisfies the following conditions? $\vec{x} \succcurlyeq \vec{0}$ is true....
3
votes
1answer
151 views

If variable falls below a certain value, include difference to set value in objective

I think its easiest to describe my goal first and continue with my implementation and the resulting problems! My goal: Using Pyomo as interface and Gurobi as solver, if a variable $x_{i,t}$ falls ...
3
votes
1answer
77 views

How to formulate this optimisation problem that has time varying components?

I've been working on a optimisation problem at work regarding blending. Essentially we have different types of grain stock with different properties and we bought them for different amounts. We then ...
5
votes
1answer
300 views

How to optimize on a fixed-cost based on number of results?

I am trying to create an LP problem which is like the knapsack problem but where there is a fixed bonus/penalty based on the number of items chosen. There are 20 items to choose from with some weight ...
0
votes
1answer
70 views

How to solve the following linear programming problem using Gurobi (or at least python)?

For an optional ungraded assignment (see it as a complex problem that won't be graded, more to test our skills and knowledge) I was given the following problem. It is not as straightforward as all the ...
5
votes
1answer
122 views

Interpretation of Reduced Costs

I am looking for an answer to a question I can't quite get behind. (continuation of Linear Programming: Integer and non-integer decision variables) I am given the following mathematical optimization ...
6
votes
1answer
567 views

Linear Programming: Integer and non-integer decision variables

I am looking for an answer to a question I can't quite get behind. I am given the following mathematical optimization problem: \begin{align}\min&\quad\sum_{t\in T}s_t\cdot z_t+h_t\cdot i_t+p_t\...
1
vote
1answer
49 views

Convex Optimization with Variable Dependency / no unmet demand carry forward

I'm running into an issue with a Linear Optimization Problem. The ultimate goal is to come back with an optimal production quantity (prod_qty) across several items ...
1
vote
1answer
62 views

Formulating a linear programming problem, with indicator variables. (Solution verification)

A factory creates different types of oils and mixes them together. There exists two types of vegetarian oils (veg1,veg2) and three types of non-vegetarian oils (oil1,oil2,oil3), the price of each oil (...
3
votes
1answer
87 views

Linearization of problem with affine linear functions

Problem: Write the following task as a linear program: $\min f(x),x\in[-2,5]$ where \begin{align}f(x) := \begin{cases} -2x+2,&\quad-2\le x<-1\\ -x+3,&\quad-1\le x < 1\\ 2,&\...
1
vote
2answers
119 views

How can I formulate an objective function that minimises the number of items required to solve a problem

I am currently trying to solve a problem where I need to minimise transport cost through the choice of vehicle (and how many of each choice) subject to a given demand. The problem: There are currently ...
4
votes
2answers
307 views

How can I move from an optimal feasible solution to an optimal basic feasible solution?

I have the following problem: \begin{align}\max&\quad c^T x\\\text{s.t.}&\quad Ax=b\\&\quad x\ge0\end{align} The matrix $A$ is $m\times n$, where $m<n$. I have an optimal solution $x^*$ ...
4
votes
0answers
61 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 ...
4
votes
2answers
607 views

Should all decision variables be present in Objective function?

This might be a very basic question for this community. I am reading an article and I think I have some confusion about formulating a problem. My understanding is that all decision variables should ...
2
votes
3answers
142 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, ...
0
votes
0answers
23 views

Add bunch of constraints using IRange and add to Model in Cplex C#

I am new in C#-CPLEX. In public samples, the constraints are added one by one as follows: ...
3
votes
0answers
48 views

Polynomial Time Solution For a Mixed-Integer Linear Programming Specific Case

Consider the following mixed-integer linear programming (MILP): \begin{equation*} \begin{array}{ll@{}ll} \text{maximize} & 1 & \\ \text{subject to}& x_{i} \geq 0, &i=1 ,\dots, m\\ ...
7
votes
1answer
167 views

How to enforce a relation between two variables

I am having trouble formulating the following constraint: I am looking to formulate a constraint that if a facility was opened at some point in time, then $Y[j,t]$ does always have to be $1$ from that ...
5
votes
1answer
113 views

Practical open source LP solvers for large linear programming problem with $10^7$ parameters

I have an LP problem of the form $\min\ c^Tx$ subject to $Ax\leq b$ where $x$ consists of 30 million parameters and $A$ is a very very sparse matrix of size 30M by 30M (with only 3 ones per row). I ...
5
votes
1answer
296 views

If continuous variable < constant then same variable = 0

When I come across with a situation needs an if-then constraints I visit Larry's post. I am a bit confused with the titled constraint this time because I am not trying to set $y$ based on $x$ but ...
2
votes
1answer
80 views

Linearization of constraints in a ILP

I have been working on a Graph Theory problem for my thesis and got stuck about the linearization of some constraints. I am hiding everything, constraints, variables and so on, of my problem not ...
5
votes
1answer
514 views

Boolean constraining another boolean

like the title suggest, I am trying to constraint a boolean with another boolean, if that makes sense. x and y are both booleans, where y=1 when ...
3
votes
1answer
90 views

How to compare the optimality gaps between a commercial solver and Benders

Suppose I have a mixed-integer-linear programming model where the objective is maximization. I solve my model in two different ways. First, I call CPLEX (a commercial solver), and then implement ...
8
votes
2answers
323 views

Mixed-Integer Linear Programming With Free Variables

In the classic Mixed-Integer Linear Programming (MILP), the variables are fixed to be either integer or real. I am interested in the following MILP variant, where only one thing different from the ...
2
votes
2answers
84 views

Best way to solve a optimization problem with no objective function?

I have a MILP but fixed the objective function, so at each iteration is constant.Therefore, I solve a constraint satisfaction problem. Is there an algorithm to solve this kind of problem fast? I have ...
4
votes
1answer
122 views

Bi-Objective MILP with two conflicting (and linear dependent) objectives

I have a bi-objective MILP (Mixed Integer Linear Programming) problem, where I call the two objective functions as Obj1 and Obj2....
2
votes
2answers
69 views

How to use `cplexAPI` to solve quadratic programs/quadratically constrained linear programs?

I am trying to use cplexAPI to solve quadratic programs or quadratically constrained linear program. While it seems to be pretty straightforward to use ...
3
votes
0answers
99 views

Harvest planning problem

I need to model the following problem: For a planning horizon of $P$ equal periods, one has $N$ harvesting locations and $K$ contractors who can harvest at those locations ($K < N$). Each ...
5
votes
2answers
143 views

In a MIP, how to force a decision variable to be zero unless the sum of specific other decision variables is equal to a certain number?

In an MIP, how can I formulate a constraint such that a decision variable is only greater (or equal to) zero if (and only if) the sum of different decision variables is equal to something. I'm working ...
4
votes
2answers
195 views

Multi-product distribution modeling : too many constraints

I have received many helps to model the problem, thank's for that ! I just edited the post to make clear what my actuel problem is. The following model is giving me amazing results with few products (...
1
vote
1answer
83 views

Resource Optimization For Cargo Handling

I have to work on some real world data and come up with an optimization technique to handle cargo. To make thing simpler let's assume that there are 2 types of resources Manpower (150 ton / 8 hour) ...
4
votes
1answer
129 views

Alternate formulation for modeling inventory constraints

I'm working on a inventory optimization problem where inventory used at a time-period is computed based on price-bucket that is selected for an item. Problem contains multiple items (around 10K), 15-...
8
votes
4answers
782 views

What is the best open source solver for large scale LP optimization in pyomo?

I have used Gurobi and cplex for solving large scale LP problems with Pyomo. However, I do need to use open source solver. Any advise? glpk and cbc seems to be very slow in solving the problem (with ...
2
votes
0answers
57 views

How to write the constraint matrix for this blending problem?

Below is a model for maximizing a utility function, a blending of, 3 ingredients $(A, B,C)$ to obtain 3 mixes of fertilizer, with the recipe given as proportions. Ingredients cost $A=130,\ B=150,\ C=...
6
votes
2answers
343 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 ...
4
votes
1answer
119 views

LP solver CPLEX is 'optimal with unscaled infeasabilities'?

The problem being solved is finding the truss with the least weight, exactly done as on this website: https://www.layopt.com/truss/. This method is also called the ground structure method. I am aiming ...
2
votes
1answer
67 views

Optimization Problem: Recommending Service Providers to Clients

I am new to optimization, not sure if the problem described below is trivial. Any guidance on solution or nudge in the right direction would be very helpful. Problem: There are two groups – clients ...
2
votes
1answer
74 views

Suggestions how to get access to MINTO MILP solver?

I came across the MINTO MILP solver today. A solver i wasn't aware of or at least had not paid attention too. While development seem to have stopped two decades ago however i still wouldn't mind ...
2
votes
1answer
126 views

Tuning the coefficients of an objective function of LP

I want to solve a problem that results in this general objective function which I want to maximize: $$a\cdot x_1+b\cdot x_2-c\cdot x_3-d\cdot x_4+e\cdot x_5$$ When I write out in full this objective ...
2
votes
0answers
74 views

What if anything do linear relaxations of "nearby" MILP nodes tell us about other MILP nodes

Assume we are given MILP where $y \in (\mathbb{R}^+)^n$, $x_1, x_2 \in \{0, 1\}$ are the integer variables. It is obvious that this problem when solved via branch and bound has a 2 deep b&b-tree. ...
4
votes
1answer
102 views

Why does setting up a problem using Excel's OpenSolver slows down after 24,000 variables?

I am modeling a big linear programming problem size with about 50,000 variables using OpenSolver. Open Solver starts setting up the problem at a constant pace of about 100 variables per second, which ...
4
votes
1answer
89 views

Maximizing sum of step functions under single linear constraint

I am trying to efficiently solve the following optimization problem: \begin{align}\max_{b \in \mathbb{R}_+^D}&\quad\sum_{n=1}^{N}\operatorname H(b^T w^{(n)} - c^{(n)}) \\\text{s.t.}&\quad\sum_{...
1
vote
1answer
151 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 ...
6
votes
2answers
360 views

How to model this expression?

Suppose $0\le x \le 1$ is a decision variable and $\gamma(x)$ is defined as follows: $$ \gamma(x)= \begin{cases} \theta & x>0\\ 0 & x=0 \end{cases} $$ where $0\le \theta\le 1$. In my model, ...
3
votes
1answer
57 views

How to specify an objective function that prohibits trading in both directions linearly

I am building a small model that trades water and buys water. For simplicity reasons, I am only discussing the relevant constraints: $\sf varWaterIn_h$ is the amount in litres of water bought per hour,...
12
votes
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 ...
5
votes
1answer
130 views

Do you know of any formula to calculate the difficulty score of Sudoku?

I am looking for a formula to measure the difficulty level of a Sudoku solution.

1
2 3 4 5
9